package DataStructures.Graphs;

import java.util.ArrayList;

class AdjacencyListGraph<E extends Comparable<E>> {

 ArrayList<Vertex> verticies;

 public AdjacencyListGraph() {
 verticies = new ArrayList<>();
 }

 private class Vertex {
 E data;
 ArrayList<Vertex> adjacentVerticies;

 public Vertex(E data) {
 adjacentVerticies = new ArrayList<>();
 this.data = data;
 }

 public boolean addAdjacentVertex(Vertex to) {
 for (Vertex v : adjacentVerticies) {
 if (v.data.compareTo(to.data) == 0) {
 return false; // the edge already exists
 }
 }
 return adjacentVerticies.add(to); // this will return true;
 }

 public boolean removeAdjacentVertex(E to) {
 // use indexes here so it is possible to
 // remove easily without implementing
 // equals method that ArrayList.remove(Object o) uses
 for (int i = 0; i < adjacentVerticies.size(); i++) {
 if (adjacentVerticies.get(i).data.compareTo(to) == 0) {
 adjacentVerticies.remove(i);
 return true;
 }
 }
 return false;
 }
 }

 /**
 * this method removes an edge from the graph between two specified verticies
 *
 * @param from the data of the vertex the edge is from
 * @param to the data of the vertex the edge is going to
 * @return returns false if the edge doesn't exist, returns true if the edge exists and is removed
 */
 public boolean removeEdge(E from, E to) {
 Vertex fromV = null;
 for (Vertex v : verticies) {
 if (from.compareTo(v.data) == 0) {
 fromV = v;
 break;
 }
 }
 if (fromV == null) return false;
 return fromV.removeAdjacentVertex(to);
 }

 /**
 * this method adds an edge to the graph between two specified verticies
 *
 * @param from the data of the vertex the edge is from
 * @param to the data of the vertex the edge is going to
 * @return returns true if the edge did not exist, return false if it already did
 */
 public boolean addEdge(E from, E to) {
 Vertex fromV = null, toV = null;
 for (Vertex v : verticies) {
 if (from.compareTo(v.data) == 0) { // see if from vertex already exists
 fromV = v;
 } else if (to.compareTo(v.data) == 0) { // see if to vertex already exists
 toV = v;
 }
 if (fromV != null && toV != null) break; // both nodes exist so stop searching
 }
 if (fromV == null) {
 fromV = new Vertex(from);
 verticies.add(fromV);
 }
 if (toV == null) {
 toV = new Vertex(to);
 verticies.add(toV);
 }
 return fromV.addAdjacentVertex(toV);
 }

 /**
 * this gives a list of verticies in the graph and their adjacencies
 *
 * @return returns a string describing this graph
 */
 @Override
 public String toString() {
 StringBuilder sb = new StringBuilder();
 for (Vertex v : verticies) {
 sb.append("Vertex: ");
 sb.append(v.data);
 sb.append("\n");
 sb.append("Adjacent verticies: ");
 for (Vertex v2 : v.adjacentVerticies) {
 sb.append(v2.data);
 sb.append(" ");
 }
 sb.append("\n");
 }
 return sb.toString();
 }
}

public class Graphs {

 public static void main(String args[]) {
 AdjacencyListGraph<Integer> graph = new AdjacencyListGraph<>();
 assert graph.addEdge(1, 2);
 assert graph.addEdge(1, 5);
 assert graph.addEdge(2, 5);
 assert !graph.addEdge(1, 2);
 assert graph.addEdge(2, 3);
 assert graph.addEdge(3, 4);
 assert graph.addEdge(4, 1);
 assert !graph.addEdge(2, 3);
 System.out.println(graph);
 }
}