Graph Cloning Algorithm

Question

The tree cloning algorithm is quite simple, we can do a workaround for this order. Is there an efficient chart cloning algorithm?

I tried a similar approach and came to the conclusion that we need to maintain a hash map of the nodes already added to the new graph, otherwise there will be duplication of nodes, since one node can have many parents.

Answer 1

It is enough to first perform a deep search and copy each node when he visited. As you say, you need some way to map the nodes in the source graph to the corresponding copies so that the copies of the loops and transverse edges can be connected correctly.

This map is also enough to remember the nodes already visited in DFS.

So in Java you will have something like:

class Node { // Contents of node... Data data; // ... member declarations like array of adjacent nodes final ArrayList<Node> children = new ArrayList<>(); // Recursive graph walker for copying, not called by others. private Node deepCloneImpl(Map<Node, Node> copies) { Node copy = copies.get(this); if (copy == null) { copy = new Node(data); // Map the new node _before_ copying children. copies.put(this, copy); for (Node child : children) copy.children.add(child.deepCloneImpl(copies)); } return copy; } public Node deepClone() { return deepCloneImpl(new HashMap<Node, Node>()); } } 

Note that you do not want to override equals or hashCode for Node . A map containing copies is based on equality of links, as defined in Object .

Another approach is to place an extra field in each node that points to the copy, if any, and otherwise null. It just implements the map in a different way. But this requires two passes on the schedule: one to create a copy, and the other to clear these map fields for subsequent reuse.

Answer 2

Your hash map approach seems viable if you have a quick way to uniquely identify each node.

Otherwise, you would be better off if you:

• the data structure used to store the graph, which allows you to store a “duplicated” unique flag directly in each node (for example, 0 not duplicated, 1 to numberOfNodes for duplicated nodes),

• traversed nodes (through BFS, DFS), taking care of already duplicated nodes and restoring all connections from the initial graph.

Both start and end graphs must have a corresponding unique “duplicated” flag in each node, so you can correctly reconnect from the initial graph. Of course, you can use the "duplicated" and "unique identifier" flags as separate variables.

Answer 3

When you copy nodes from the original graph, put each node on the <Node, Integer> map (thus, the number of nodes is from 1 to N).

When you insert the nodes in the destination graph, put each node on the <Integer, Node> map (again the numbering is from 1 to N, but with the display in the opposite direction for reasons that will soon be clear).

When you find the backlink in the source graph, you can map the backward "source copy" of the node to the integer i using the first map. Then you use the second map to search for the integer i and find the “target copy” of the node, which should have the same backlink.

Answer 4

To make cloning effective, use two things:

• DS with faster removal and adding at the end. Choose from list , queue or stack
• DS with quick search. Map can be quickly found, i.e. O(1) amortized.

Algorithm:

  To be processed <--> Queue / Not_Cloned_Yet -> Clone it -> Map `~~~~~~~~checks~~~~~~~~~~^ Root is "Not Cloned yet" and needs to be "To be processed" -- (1) Clone it -> Put in Map & Queue -- (2) Continue till "To be processed" is not zero. ie Queue is not empty. -- (3) Traverse and update the list of neighbours -- (4) Neighbours that are "Not cloned yet" needs "Clone it -> Put in Map & Queue" --(5) 

• Step 2 and 5 are based on To be processed --> Queue
• Step 3 on Queue -> To be processed .
• The elements of the queue are those that are already cloned, but are NOT processed (i.e., the list of its neighbors is not updated).
• Neighbors may or may not be cloned yet. Therefore, you need to check the card.