Leetcode 133: clone graph

May 1, 2016

Problem statement and solutions:

http://bangbingsyb.blogspot.ca/2014/11/leetcode-clone-graph.html

http://www.cnblogs.com/springfor/p/3874591.html


C# code:
Easy to read - Node class
https://gist.github.com/jianminchen/c328dbc4391cb03a9ab8665b3ab54966
Fit into leetcode online judge
https://gist.github.com/jianminchen/bf0821320af0e549b486997faf11b358

Question and answer:

1. What do you learn through the practice? Can you write down your own words with your experience of learning?

1. Let us talk about a small test case, undirected graph {0,1,2#1,2#2,2}, here is the graph:

So, in Julia's practice, undirected graph node is defined in class Node:
class Node
{
    public int label;
    public List<node> neighbors;

    public Node(int x)
  {
         label = x;
         neighbors = new List<Node>();
   }
}

The above graph, 3 nodes are declared, node0, node1, node2,
3 edges in the graph:
 0 -- 1,
 0 -- 2
the above 2 edges are saved in node0's neighbors - a list;

edge 1--2
the third edge is saved in node1's neighbors;

edge 2--2 - a loop to itself
the fourth edge is saved in node2's neighbors - a list containing node2 itself.

Here is the expression to parse the graph: {0,1,2#1,2#2,2}

Any edge in the graph is only saved once in the list named in neighbors. <- It is good! 

Julia likes to catch up some reading about graph, so she spent 10 minutes to read:
http://algs4.cs.princeton.edu/41graph/

2. Need to review graph search, DFS vs. BFS, in the above C# practice, queue is used, so it should be BFS - breadth first search.

So, cloneGraph(Node node) function is designed to do BFS - breadth first search. If node0 is passed, then we can go over the steps what should do:

Main idea is to put input argument - a node into queue, copy the node to a first node in cloned graph, denoted as newHead.
Also, in the Dictionary - a map, add one entry - node, newHead.

Next, get into a loop with queue length checking > 0:
dequeue the node from the queue, and then,
check its neighbors, go through the iteration loop one by one.

If the neighbor node is not in the dictionary, then,
    it is not in cloned graph, what we need to do, is to add a new node in cloned graph,
    and also add a new entry in the dictionary,
    and update cloned graph neighbors list as well.
If the neighbor node is in the dictionary, then
    update cloned graph with current node's mapping - add one entry in neighbor list. (*)
<- (*) Need to figure out when this executable path will be executed! 

So, node0 is passed in as an argument, walk through steps:
node0 has two neighbors, node1 and node2, 
go through one by one, 
node1 is not in the dictionary, create a copy for node1, 
add an entry {node1, copy} into the dictionary,
also bind copy to newHead's neighbor. 
add node1 into queue. 

node2 is visited, and then, ...
add node2 into queue

when node1 is dequeued from queue, node1's neighbors are examined:
only one neighbor, node2. 
But node2 is already in the dictionary, <- need to debug the code to verify

when node0 is dequeued from queue, 
node1 and node2 are added to queue, 
two edges are added to clonedGraph, 
ditionary is updated with node1 and node2. 

when node1 is dequeued, need to add edge 1->2. 

change C# code: 
https://gist.github.com/jianminchen/35f3efda39c30d1e993a16a89d14308d

Make the code more flat, remove if/else in previous version. 
foreach (Node aNeighbor in currNeighbors)
                {
                    bool containing = map.ContainsKey(aNeighbor); 

                    // 1.update queue 
                    if (!containing)
                        queue.Enqueue(aNeighbor); 

                    // 2. update map 
                    if (!containing)
                    {
                        Node copy = new Node(aNeighbor.label);
                        map.Add(aNeighbor, copy); 
                    }

                    // 3. update neighbors for cloned graph 
                    // definitely, map.ContainsKey[aNeighbor]                   
                    map[curr].neighbors.Add(map[aNeighbor]);                    

                }

Comment: 
1. The explanation is kind of tricky, not so clear! Improve it later. 

2. Look into issues about else statement, Julia makes mistakes when she write if/else, and do not pay attention to else condition. <- basic logic checking...
Next time, try to put all true case in one statement. Your cognitive ability is in a standard level, only thing to improve is to discipline yourself, write code with more disciplines, simplify!