package DataStructures.Graphs;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

/**
 * A class that counts the number of different connected components in a graph
 *
 * @author Lukas Keul, Florian Mercks
 */
class Graph<E extends Comparable<E>> {

 class Node {
 E name;

 public Node(E name) {
 this.name = name;
 }
 }

 class Edge {
 Node startNode, endNode;

 public Edge(Node startNode, Node endNode) {
 this.startNode = startNode;
 this.endNode = endNode;
 }
 }

 ArrayList<Edge> edgeList;
 ArrayList<Node> nodeList;

 public Graph() {
 edgeList = new ArrayList<Edge>();
 nodeList = new ArrayList<Node>();
 }

 /**
 * Adds a new Edge to the graph. If the nodes aren't yet in nodeList, they will be added to it.
 *
 * @param startNode the starting Node from the edge
 * @param endNode the ending Node from the edge
 */
 public void addEdge(E startNode, E endNode) {
 Node start = null, end = null;
 for (Node node : nodeList) {
 if (startNode.compareTo(node.name) == 0) {
 start = node;
 } else if (endNode.compareTo(node.name) == 0) {
 end = node;
 }
 }
 if (start == null) {
 start = new Node(startNode);
 nodeList.add(start);
 }
 if (end == null) {
 end = new Node(endNode);
 nodeList.add(end);
 }

 edgeList.add(new Edge(start, end));
 }

 /**
 * Main method used for counting the connected components. Iterates through the array of nodes to
 * do a depth first search to get all nodes of the graph from the actual node. These nodes are
 * added to the array markedNodes and will be ignored if they are chosen in the nodeList.
 *
 * @return returns the amount of unconnected graphs
 */
 public int countGraphs() {
 int count = 0;
 Set<Node> markedNodes = new HashSet<Node>();

 for (Node n : nodeList) {
 if (!markedNodes.contains(n)) {
 markedNodes.add(n);
 markedNodes.addAll(depthFirstSearch(n, new ArrayList<Node>()));
 count++;
 }
 }

 return count;
 }

 /**
 * Implementation of depth first search.
 *
 * @param n the actual visiting node
 * @param visited A list of already visited nodes in the depth first search
 * @return returns a set of visited nodes
 */
 public ArrayList<Node> depthFirstSearch(Node n, ArrayList<Node> visited) {
 visited.add(n);
 for (Edge e : edgeList) {
 if (e.startNode.equals(n) && !visited.contains(e.endNode)) {
 depthFirstSearch(e.endNode, visited);
 }
 }
 return visited;
 }
}

public class ConnectedComponent {

 public static void main(String[] args) {
 Graph<Character> graphChars = new Graph<>();

 // Graph 1
 graphChars.addEdge('a', 'b');
 graphChars.addEdge('a', 'e');
 graphChars.addEdge('b', 'e');
 graphChars.addEdge('b', 'c');
 graphChars.addEdge('c', 'd');
 graphChars.addEdge('d', 'a');

 graphChars.addEdge('x', 'y');
 graphChars.addEdge('x', 'z');

 graphChars.addEdge('w', 'w');

 Graph<Integer> graphInts = new Graph<>();

 // Graph 2
 graphInts.addEdge(1, 2);
 graphInts.addEdge(2, 3);
 graphInts.addEdge(2, 4);
 graphInts.addEdge(3, 5);

 graphInts.addEdge(7, 8);
 graphInts.addEdge(8, 10);
 graphInts.addEdge(10, 8);

 System.out.println("Amount of different char-graphs: " + graphChars.countGraphs());
 System.out.println("Amount of different int-graphs: " + graphInts.countGraphs());
 }
}