Algorithm to clone a graph

Question

Algorithm to clone a tree is quite easy, we can do pre-order traversal for that. Is there an efficient algorithm to clone a graph?

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

Answer 1

As you copy nodes from the source graph, place each node in a <Node, Integer> map (thus numbering the nodes from 1 to N).

As you paste nodes in the destination graph, place each node in a <Integer, Node> map (again numbering from 1 to N, but with mapping in reverse direction for reasons that will be clear soon).

When you find a backlink in the source graph, you can map that backlinked "source copy" node to an integer i using the first map. Next, you use the second map to lookup the integer i and find the "destination copy" node which needs to have the same backlink created.

Answer 2

To make the cloning efficient, use two things:

• DS with faster deletion and addition at end. Choose among list, queue or stack
• DS with fast searching. Map can be quickly searched 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. i.e. 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)

1. Step 2 and 5 are based on To be processed --> Queue
2. Step 3 on Queue -> To be processed.
3. The queue elements are the ones which are already cloned, but NOT processed (i.e. its neighbours list not updated).
4. Neighbours may or may not have been cloned yet. So, check in map is needed.

Answer 3

Your hash map approach seems viable if you had some quick way of uniquely identifying every node.

Otherwise, you would be best off if you:

1. used data-structure to store graph that allows you to store "is duplicated" unique flag directly in every node (for example, 0 not duplicated, 1 to numberOfNodes for duplicated nodes),

2. traversed nodes (via BFS, DFS) taking care of the already duplicated nodes and reconstructing all connections from the starting graph.

Both your starting graph and finishing graph should have corresponding unique "is duplicated" flag in every node, so you are able to reconstruct connections from starting graph properly. Of course, you could use "is duplicated" flag and "unique identifier" as separate variables.

Answer 4

It suffices to do a depth first search and copy each node as it's visited. As you say, you need some way of mapping nodes in the original graph to corresponding copies so that copies of cycle and cross edges can be connected correctly.

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

So in Java you'd 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 don't want to override equals or hashCode for Node. The map containing copies relies on reference equality as defined by Object.

A different approach is to put an additional field in each node that points to the copy if there is one and is null otherwise. This merely implements the map by another method. But it requires two passes over the graph: one to make the copy and another to clear these map fields for future re-use.