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 {
vectorneighbors;
}
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 graphAssume 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!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | typedef unordered_map<Node *, Node *> Map; Node *clone(Node *graph) { if (!graph) return NULL; Map map; queue<Node *> q; q.push(graph); Node *graphCopy = new Node(); map[graph] = graphCopy; while (!q.empty()) { Node *node = q.front(); q.pop(); int n = node->neighbors.size(); for (int i = 0; i < n; i++) { Node *neighbor = node->neighbors[i]; // no copy exists if (map.find(neighbor) == map.end()) { Node *p = new Node(); map[node]->neighbors.push_back(p); map[neighbor] = p; q.push(neighbor); } else { // a copy already exists map[node]->neighbors.push_back(map[neighbor]); } } } return graphCopy; } |
Chaos said on May 30, 2012
nice job:) and adding this problem to OJ list would be preferable
1337c0d3r said on May 31, 2012
Thanks. I would try my best to add it.
Venki said on May 31, 2012
@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…
1337c0d3r said on May 31, 2012
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.
Venki said on May 31, 2012
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?
Hector said on June 12, 2012
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…
Sanjay Pandey said on June 20, 2012
To embed your code, please use
.
عرب برامج said on July 12, 2012
thank u this is what i am loking for
Jinhui said on July 16, 2012
I cannot help saying this is really a nice work with clear explanation. Thanks
temp123 said on August 8, 2012
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!
moussa said on January 30, 2013
I think you are right. The code will work for spanning tree but Forest which consists of multiple disconnected trees.
Nison said on May 10, 2013
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 : )
Chao Chen said on August 10, 2012
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;
}
1337c0d3r said on August 11, 2012
Yup, DFS is another solution, which is actually considerably easier than the BFS solution.
Chao Chen said on August 10, 2012
And I guess that you can use my codes in your second part(I didn’t find part II).
jack said on August 13, 2012
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?
Nison said on May 10, 2013
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. : )
codez said on August 15, 2012
@1337c0d3r
i have the same doubt as Jack. y r we pushing an empty node?
plz clarify soon
1337c0d3r said on August 15, 2012
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.
jack said on August 16, 2012
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;
}
nehaheights said on August 17, 2012
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]);
}
}
}
Nison said on May 10, 2013
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.
Nison said on May 10, 2013
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.
Bin said on January 23, 2013
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];
}
chen long said on March 11, 2013
// 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;
}
B l said on April 4, 2013
this code will run infinitely if the graph has a loop: A->B->C->A. is it right?
overboming said on April 7, 2013
No, it’s breath first, A->C is already in the hashmap when C is on the top of the queue
WuTeng said on May 18, 2013
To embed your code, please use
.