package graphs;

import java.util.*;

public class CloneDirectedGraph {


    /*
     * Given root node of a directed graph, clone this graph by creating its deep copy such that
     * cloned graph has same vertices and edges as original graph.
     *
     *
     * If input graph is G = (V, E) where V is set of vertices and E is set of edges,
     * then output graph (cloned graph) G' = (V', E') such that V = V' and E = E'.
     *
     * Runtime Complexity:
     * Linear, O(n)
     *
     * Memory Complexity:
     * Logarithmic, O(n). 'n' is number of vertices in graph.
     *
     * Use depth first traversal and create a copy of each node while traversing the graph.
     * To avoid getting stuck in cycles, use a hashtable to store each completed node and will not revisit
     * nodes that exist in the hashtable.
     * Hashtable key will be a node in the original graph, and its value will be the corresponding node
     * in cloned graph.
     *
     * */

    // if there is an edge from x to y
    // that means there must be an edge from y to x
    // and there is no edge from a node to itself
    // hence there can maximim of (nodes * nodes - nodes) / 2 edges in this graph
    static ArrayList<Node> createTestGraphUndirected(int nodes_count, int edges_count) {
        ArrayList<Node> vertices = new ArrayList<Node>();
        for (int i = 0; i < nodes_count; ++i) {
            vertices.add(new Node(i));
        }

        List<Pair<Integer, Integer>> all_edges = new ArrayList<Pair<Integer, Integer>>();
        for (int i = 0; i < vertices.size(); ++i) {
            for (int j = i + 1; j < vertices.size(); ++j) {
                all_edges.add(new Pair<>(i, j));
            }
        }

        Collections.shuffle(all_edges);

        for (int i = 0; i < edges_count && i < all_edges.size(); ++i) {
            Pair<Integer, Integer> edge = all_edges.get(i);
            vertices.get(edge.first).neighbors.add(vertices.get(edge.second));
            vertices.get(edge.second).neighbors.add(vertices.get(edge.first));
        }

        return vertices;
    }

    static void printGraph(List<Node> vertices) {
        for (Node n : vertices) {
            System.out.print(n.data + ": {");
            for (Node t : n.neighbors) {
                System.out.print(t.data + " ");
            }
            System.out.println();
        }
    }

    static void printGraph(Node root,
                           HashSet<Node> visited_nodes) {

        if (root == null || visited_nodes.contains(root)) {
            return;
        }

        visited_nodes.add(root);

        System.out.print(root.data + ": {");
        for (Node n : root.neighbors) {
            System.out.print(n.data + " ");
        }
        System.out.println("}");

        for (Node n : root.neighbors) {
            printGraph(n, visited_nodes);
        }
    }

    static void printGraph(Node root) {
        HashSet<Node> visited_nodes = new HashSet<Node>();
        printGraph(root, visited_nodes);
    }

    static boolean areGraphsEqualRec(Node root1,
                                     Node root2,
                                     HashSet<Node> visited) {

        if (root1 == null && root2 == null) {
            return true;
        }

        if (root1 == null || root2 == null) {
            return false;
        }

        if (root1.data != root2.data) {
            return false;
        }

        if (root1.neighbors.size() != root2.neighbors.size()) {
            return false;
        }

        for (Node nbr1 : root1.neighbors) {
            boolean found = false;
            for (Node nbr2 : root2.neighbors) {
                if (nbr1.data == nbr2.data) {
                    if (!visited.contains(nbr1)) {
                        visited.add(nbr1);
                        areGraphsEqualRec(nbr1, nbr2, visited);
                    }
                    found = true;
                    break;
                }
            }
            if (!found) {
                return false;
            }
        }

        return true;
    }


    protected static class Node {
        public int data;
        public List<Node> neighbors = new ArrayList<Node>();

        public Node(int d) {
            data = d;
        }
    }

    protected static class Graph {
        private static Node cloneRec(Node root,
                                     HashMap<Node, Node> nodes_completed) {
            if (root == null) {
                return null;
            }

            Node pNew = new Node(root.data);
            nodes_completed.put(root, pNew);

            for (Node p : root.neighbors) {
                Node x = nodes_completed.get(p);
                if (x == null) {
                    pNew.neighbors.add(cloneRec(p, nodes_completed));
                } else {
                    pNew.neighbors.add(x);
                }
            }
            return pNew;
        }

        public static Node clone(Node root) {
            HashMap<Node, Node> nodes_completed = new HashMap<Node, Node>();
            return cloneRec(root, nodes_completed);
        }
    }

    protected static class Pair<K, V> {

        private K first;
        private V second;

        public static <K, V> Pair<K, V> createPair(K element0, V element1) {
            return new Pair<K, V>(element0, element1);
        }

        public Pair(K first, V second) {
            this.first = first;
            this.second = second;
        }

        public K getFirst() {
            return first;
        }

        public V getSecond() {
            return second;
        }

    }


    public static void main(String[] args) {
        ArrayList<Node> vertices = createTestGraphUndirected(7, 18);
        printGraph(vertices.get(0));

        Node cp = Graph.clone(vertices.get(0));
        System.out.println();
        System.out.println("After copy: ");
        printGraph(cp);

        HashSet<Node> set = new HashSet<>();
        System.out.println(areGraphsEqualRec(vertices.get(0), cp, set));
    }
}