Clone Graph Part I

May 30, 2012 in Uncategorized

Clone a graph. Input is a Node pointer. Return the Node pointer of the cloned graph.

A graph is defined below:
struct Node {
vector neighbors;
}

Hint:
There are two main ways to traverse a graph. Do you still remember them? Could you tell if the graph is directed or undirected?

Solution:
There are two main ways to traverse a graph: Breadth-first or Depth-first. Let’s try the Breadth-first approach first, which requires a queue. For the Depth-first approach, please see Clone Graph Part II.

How does the breadth-first traversal works? Easy, as we pop a node off the queue, we copy each of its neighbors, and push them to the queue.

A straight forward breadth-first traversal seemed to work. But some details are still missing. For example, how do we connect the nodes of the cloned graph?

Before we continue, we first need to make sure if the graph is directed or not. If you notice how Node is defined above, it is quite obvious that the graph is a directed graph. Why?

For example, A can have a neighbor called B. Therefore, we may traverse from A to B. An undirected graph implies that B can always traverse back to A. Is it true here? No, because whether B could traverse back to A depends if one of B’s neighbor is A.

The fact that B can traverse back to A implies that the graph may contain a cycle. You must take extra care to handle this case. Imagine that you finished implementing without considering this case, and later being pointed out by your interviewer that your code has an infinite loop, yuck!

Let’s analyze this further by using the below example:

A simple graph

Assume that the starting point of the graph is A. First, you make a copy of node A (A2), and found that A has only one neighbor B. You make a copy of B (B2) and connects A2->B2 by pushing B2 as A2′s neighbor. Next, you find that B has A as neighbor, which you have already made a copy of. Here, we have to be careful not to make a copy of A again, but to connect B2->A2 by pushing A2 as B2′s neighbor. But, how do we know if a node has already been copied?

Easy, we could use a hash table! As we copy a node, we insert it into the table. If we later find that one of a node’s neighbor is already in the table, we do not make a copy of that neighbor, but to push its neighbor’s copy to its copy instead. Therefore, the hash table would need to store a mapping of key-value pairs, where the key is a node in the original graph and its value is the node’s copy.

Let’s implement the code!

VN:F [1.9.22_1171]
Rating: 4.5/5 (97 votes cast)
Clone Graph Part I, 4.5 out of 5 based on 97 ratings

57 responses to Clone Graph Part I

  1. nice job:) and adding this problem to OJ list would be preferable

    VN:F [1.9.22_1171]
    +2
    • Thanks. I would try my best to add it.

      VN:F [1.9.22_1171]
      +5
      • @1 337c0d3r,
        Hi,
        Please let me know what do you think about following approach,

        Instead of using hash table to store the prevoiusly cloned nodes / visited nodes. We can keep a pointer in original graph ( cloned_node ), and set it at time of clone node creation and use it at time of visiting it as a visited neighbour of a new node.
        I know it leads to O(V) space overhead in original graph, but it provides actual O(1) access time and avoid requirements to have a lable in nodes.

        VN:F [1.9.22_1171]
        +3
  2. @1337c0d3r,

    I am not clear about graph representation. If the graph is having more than one SCC, how can it be represented using Node structure? For example, a directed graph with four nodes, A, B, C and D. Assume we have the directed edges, (A, B), (B, A), (D, C), (B, C) and (A, C) where pair (X, Y) represents directed edge from X to Y.

    I was unable to construct graph for the above input. Am I missing anything? Please correct me…

    VN:F [1.9.22_1171]
    0
    • In your above example,
      Node A would have neighbors B, C.
      Node B would have neighbors A, C.
      Node C would have 0 neighbor.
      Node D would have neighbor C.

      Your job is to clone the above graph, and return a copy of its graph.

      VN:F [1.9.22_1171]
      0
  3. Oh, okay. I got it. Thanks. I face the above problem when I tried to create few test cases. But it worked fine for the partial graph. To add further, we can extend the Node structure with second level pointer that will point next component of the graph.

    Any inputs?

    VN:F [1.9.22_1171]
    0
  4. Guess the problem was to clone a “Connected” graph. Consider graph:

    A->B<-C

    Code above start from A will stop at node B. Node C will be ignored…

    VN:F [1.9.22_1171]
    +2
    • this graph can not be represented using only a node pointer. and it is not the case here.

      VN:F [1.9.22_1171]
      +4
  5. To embed your code, please use

    .

    VN:F [1.9.22_1171]
    0
  6. thank u this is what i am loking for

    VA:F [1.9.22_1171]
    0
  7. I cannot help saying this is really a nice work with clear explanation. Thanks

    VN:F [1.9.22_1171]
    0
  8. I’m not sure if I got the problem right.

    I don’t why you can represent a graph as a node.
    A graph is defined below:
    struct Node {
    vector neighbors;
    }

    What if the graph is not connected?

    I also don’t know why this is difficult — graph is always represented by data structures. Can we just copy the data representation? Do we have to traverse the graph?

    Thanks!

    VA:F [1.9.22_1171]
    +2
    • I think you are right. The code will work for spanning tree but Forest which consists of multiple disconnected trees.

      VA:F [1.9.22_1171]
      0
    • Believe the question is not clear by its definition. Intuitively, as the Graph is defined by Node, it is supposed to be connected.

      And by further reflection, a graph is usually defined as array of pointer of linked list, if clone a graph, the possible solution is simply combination of the individual graph clone, together with the final combination of the individual graphs into the whole graph.

      But in latter case, the graph is not given by a node, rather, it should be given as a pointer of array of pointer of linked list. In cases when graph is represented in other form, the solution is similar.

      So up to now, the solution of the creator of this topic and other great guys are focusing on the individual graph clone — the core of the whole graph clone. You are all great guys and I have benefit a lot : )

      VN:F [1.9.22_1171]
      0
  9. You are using BFS.
    Actually I was interviewed with this question yesterday.

    And I used DFS. The following are my codes:
    Node* DFS(Node *Input, hash_map &hm){

    if(hm.find(Input) != hm.end()){
    return hm[Input];
    }
    Node *output = new Node();
    hm[Input] = output;
    for(int i = 0; i next.size();i++){
    output->next.push_back(DFS(Input->next[i],hm));
    }
    return output;
    }

    VA:F [1.9.22_1171]
    +6
    • Yup, DFS is another solution, which is actually considerably easier than the BFS solution.

      VN:F [1.9.22_1171]
      0
    • Thanks for your code.

      VN:F [1.9.22_1171]
      0
    • I am not quite sure. But there seems a bug in the code.

      The function return the cloned node. However, it accepts the original node and it is in recursive manner.

      So the second visit on the recursive function will provide the wrong parameter (cloned node rather than original node)

      VN:F [1.9.22_1171]
      0
    • Sorry, my mistake. It works. Awesome

      VN:F [1.9.22_1171]
      0
  10. And I guess that you can use my codes in your second part(I didn’t find part II).

    VA:F [1.9.22_1171]
    +2
  11. sorry,I don’t understand this “if” part:

    if (map.find(neighbor) == map.end()) {
    Node *p = new Node();
    map[node]->neighbors.push_back(p);
    map[neighbor] = p;
    q.push(neighbor);
    }

    if a copy doesn’t exist, an empty new node p was pushed to the end of one of graphCopy’s node’s neighbors vector table. Why push_back an empty new node, not a node from original graph node?

    VA:F [1.9.22_1171]
    +1
    • IMHO, an empty new node was pushed…. the point is that, it is not only pushed into the vector, but also be added into the map, so the node in original graph and the node in new graph is “related to each other” by the bridge of map.

      In first glance, it will only be put into the vector. But after thinking twice, we can notice that the neighbor will be put into the queue. And at the time the neighbor is pop out, we will traverse its neighbor — that’s the time we will edit “empty node ” p — node p now shows as “node”. By modification of node map[node], we actually modify node p.

      So the connection is built through map, and the queue will serve as an coordinator to help decide who will be traversed first and who later.

      Focus on the map and queue. They are the heart of the algorithm provided by this topic’s creator, if my guess is not wrong. : )

      VN:F [1.9.22_1171]
      +2
  12. @1337c0d3r
    i have the same doubt as Jack. y r we pushing an empty node?
    plz clarify soon

    VA:F [1.9.22_1171]
    0
    • By pushing an empty node you are essentially making a copy of the node. You are to clone a graph, so essentially make a copy of each node and linking all of them together.

      VN:F [1.9.22_1171]
      0
      • In a graph, each node should have some data fields, such as “int data”.
        Each node should have 2 parts:

        struct Node {

        int data;

        vector neighbors;
        }

        VA:F [1.9.22_1171]
        +1
  13. typedef unordered_map Map;
    Map map;

    void cloneDFS (Node *graph, Node *&graphCopy) {
    if (!graph) return;

    if(map.find(graph) == map.end())
    {
    graphCopy = new Node();
    map[graph] = graphCopy;
    map[graph]->data = graph->data;
    }

    int n = graph->neighbors.size();
    for (int i = 0; i neighbors[i];
    // no copy exists
    if (map.find(neighbor) == map.end()) {
    Node *p = new Node();
    map[graph]->neighbors.push_back(p);
    map[neighbor] = p;
    map[neighbor]->data = neighbor->data;
    cloneDFS(neighbor, p);
    } else { // a copy already exists
    map[graph]->neighbors.push_back(map[neighbor]);
    }
    }
    }

    VN:F [1.9.22_1171]
    0
    • IMHO, there are 3 aspects that you can improve your code.

      1). The clone of parent node and clone of child node have some identical part. Those part could be simplified by recursive call. Yes, you did, but why clone neighbor twice, in the if statement under the true field?

      2). Because of the void return type, you cannot benefit for its return information. So you made your choice to create the node before clone it, and then call recursive. But when calling recursively, you create another node using “new”, again. The will destroy the graph structure. Also, this will consume resources.

      3). Another point is that because you select the cloned graph as an parameter, you have to declare it before the clone call. To avoid warning of uninitialized variable, you maybe choose to initialize it by new. This is not a fairly good choice IMO.

      So, you refer to Chao Chen’s code. Why is his code so simple? Because
      1) he use return type smartly, so as to avoid duplicate information
      2) he separate steps clearly, no overlapping function

      Let’s come back to your code, and I modify it according to your idea, as below. And you will see that it doesn’t work.

      VN:F [1.9.22_1171]
      +7
    • IMHO, there are 3 aspects that you can improve your code.

      1). The clone of parent node and clone of child node have some identical part. Those part could be simplified by recursive call. Yes, you did, but why clone neighbor twice, in the if statement under the true field?

      2). Because of the void return type, you cannot benefit for its return information. So you made your choice to create the node before clone it, and then call recursive. But when calling recursively, you create another node using “new”, again. The will destroy the graph structure. Also, this will consume resources.

      3). Another point is that because you select the cloned graph as an parameter, you have to declare it before the clone call. To avoid warning of uninitialized variable, you maybe choose to initialize it by new. This is not a fairly good choice IMO.

      So, you refer to Chao Chen’s code. Why is his code so simple? Because
      1) he use return type smartly, so as to avoid duplicate information
      2) he separate steps clearly, no overlapping function

      Let’s come back to your code, and I modify it according to your idea, as below. And you will see that it doesn’t work.

      VN:F [1.9.22_1171]
      0
      • using namespace std;

        struct node{
        int data;
        vector neighbors;
        };

        unordered_map m;

        void cloneNeighbors(node*, node*);

        node* cloneGraphDFS(node* graph){
        if(!graph)
        return NULL;

        node* graphClone = new node;
        graphClone->data = graph->data;
        m[graph] = graphClone;

        cloneNeighbors(graph, graphClone);

        return graphClone;
        }

        void cloneNeighbors(node* origin, node* clone){

        int n = origin->neighbors.size();

        for(int i=0; ineighbors[i];

        if(m.find(pNeighbor)== m.end()){
        node* pNeighborClone = new node;
        pNeighborClone->data = pNeighbor->data;
        m[pNeighbor] = pNeighborClone;
        m[origin]->neighbors.push_back(pNeighborClone);

        cloneNeighbors(pNeighbor, pNeighborClone);
        }
        else{
        m[origin]->neighbors.push_back(m[pNeighbor]);
        }

        }//for i
        }

        int main( )
        {
        node* root = new node;
        root->data = 0;

        node* node1 = new node;
        node1->data = 1;
        root->neighbors.push_back(node1);
        node1->neighbors.push_back(root);

        node * node2 = new node;
        node2->data = 2;
        node1->neighbors.push_back(node2);

        node* graphClone = cloneGraphDFS(root);

        return 0;
        }

        VN:F [1.9.22_1171]
        0
  14. seems separate the node creating and relationship copying makes code more readable, this is my answer

    class Node
    {
    public Node()
    {
    neighbors = new List();
    }
    public IList neighbors { get; private set; }
    }

    Node Copy(Node org)
    {
    if (null == org)
    return null;
    Queue wait = new Queue();
    IDictionary map = new Dictionary();

    wait.Enqueue(org);
    while (wait.Count > 0)
    {
    var current = wait.Dequeue();
    if (!map.ContainsKey(current))
    {
    Node copy = new Node();
    map.Add(current, copy);
    }
    foreach (Node neighbor in current.neighbors)
    {
    if (!map.ContainsKey(neighbor))
    {
    wait.Enqueue(neighbor);
    }
    }
    }

    foreach (KeyValuePair pair in map)
    {
    foreach (Node neighbor in pair.Key.neighbors)
    {
    pair.Value.neighbors.Add(map[neighbor]);
    }
    }

    return map[org];
    }

    VA:F [1.9.22_1171]
    0
  15. // Type your C++ code and click the “Run Code” button!
    // Your code output will be shown on the left.
    // Click on the “Show input” button to enter input data to be read (from stdin).

    #include
    #include
    #include
    #include
    #include

    using namespace std;

    struct Node {
    Node(int value) : value(value) {}

    Node(Node &rhs) {
    if (&rhs == this) {return;}
    this->value = rhs.value;
    this->neighbors.resize(rhs.neighbors.size());
    }
    int value;
    vector neighbors;
    };

    Node* clone(Node *node) {
    if(node == 0) { return 0; }

    map created;
    queue to_expand;

    int id = 0;
    Node *copy = new Node(*node);
    created[node] = copy;

    to_expand.push(node);

    while(!to_expand.empty()) {
    // fetech the first node
    Node *curr = to_expand.front();
    to_expand.pop();

    int n_size = curr->neighbors.size();
    // copy the neighbors of curr_src into curr_dst.
    for(int n_idx = 0; n_idx neighbors[n_idx];

    // if we have created the copy, fill out the created one.
    if(created.find(c) != created.end()) {
    // cloned node alreayd exist.
    created[curr]->neighbors[n_idx] = created[c][/c];
    }else{
    // no cloned node existed.
    Node* n = new Node(*c);
    // this is a new node, we need to fill out its neighbors as well.
    // let’s register into the BFS queue for future explore.
    created[curr]->neighbors[n_idx] = n;
    created[c][/c] = n;
    to_expand.push(c);
    }
    }
    }
    return copy;
    }

    int main() {

    Node *src = new Node(100);
    src->neighbors.push_back(new Node(101));
    src->neighbors[0]->neighbors.push_back(src);

    Node *dst = clone(src);

    // cout <value << endl;
    cout <value << endl;
    cout <neighbors[0]->value << endl;
    cout <neighbors[0]->neighbors[0]<< endl;

    return 0;
    }

    VA:F [1.9.22_1171]
    0
  16. this code will run infinitely if the graph has a loop: A->B->C->A. is it right?

    VN:F [1.9.22_1171]
    0
    • No, it’s breath first, A->C is already in the hashmap when C is on the top of the queue

      VN:F [1.9.22_1171]
      0
  17. we are creating one copy and using pointers in the vector.. my concern is when we need to delete nodes the question comes who is responsible for free up memory and so need to be extra careful in deleting node..I would convert node* to some shared pointer so that ownership issues wil not arise

    VN:F [1.9.22_1171]
    0
  18. VN:F [1.9.22_1171]
    0
  19. VN:F [1.9.22_1171]
    0
  20. why i can not use OJ ?

    VN:F [1.9.22_1171]
    0
  21. god! , why the disscuss need another count

    VN:F [1.9.22_1171]
    0
  22. Neat, seems like a lot of different ways we can clone a graph. But which one is most efficient. and main question is do we really need to clone the whole graph. Good read, comments are even more interesting. :)

    VA:F [1.9.22_1171]
    0
  23. Logic similar to what has been posted above, but used a queue…

    VN:F [1.9.22_1171]
    0
    • This two lines makes it returns the original graph.

      VN:F [1.9.22_1171]
      0
  24. I have a question here.. Generally or rather mathematically, a graph is defined as a set of vertices and edges. Till now, whatever implementations I have made on graphs, I have made use of this property of graph and it actually helps in proper designing of the graph.

    But, the definition given here contains just the neighbors of every Vertex. Now, this kinda scenario is good for this problem, but if say, we have to implement the Djikstra algo, then this may not be the best way of implementing a graph as we need to assign weights to the edges, which doesn’t quite seem possible here.

    So, is it the case that we need to make new graph implementation per problem or would having an uber-graph with all properties be more helpful? I am also asking from the interviewing purposes. Is the structure always imposed upon us or we can make assumptions and go ahead?

    Any suggestions would be highly appreciated.

    VN:F [1.9.22_1171]
    0
  25. where is part II ??

    VN:F [1.9.22_1171]
    +1
  26. thanks

    VN:F [1.9.22_1171]
    0
  27. Does this question have a flaw? Suppose we have a directed graph as follows:
    A->B<-C
    And, the input pointer points to B. How can I traverse this graph?

    VN:F [1.9.22_1171]
    +2
  28. Java Version

    VN:F [1.9.22_1171]
    0
    • There is a bug in the code. I should not have added clonedNeighbor into the queue. Here is the fixed code.

      VN:F [1.9.22_1171]
      0
    • VN:F [1.9.22_1171]
      0
  29. Breath first and Depth first Java code

    VN:F [1.9.22_1171]
    +2
  30. unordered_map, queue. You used too many helpers. :(

    VA:F [1.9.22_1171]
    0
  31. Spent some time and found that using map is really a good idea.

    VN:F [1.9.22_1171]
    0
  32. without using a hashmap

    VA:F [1.9.22_1171]
    0
    • VA:F [1.9.22_1171]
      0
      • VA:F [1.9.22_1171]
        0
  33. https://github.com/mission-peace/interview/wiki
    More interview questions here

    VA:F [1.9.22_1171]
    0

Leave a reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

2 trackbacks