Cloning a graph in Python
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.
If you have ever played around with Algorithms & Data Structures, then you most likely have heard of Leetcode.com, which contains a number of famous (or infamous) of technical questions. One of my favorite in there is the graph clone question, which can be shortly stated as:
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
Like most algorithms & data structures problems, there are usually many variants to solving this problem, but here I will go through the solution that is most typically reported. To begin, it is generally good form to define a Node
class:
You can test the Node
class in your Python interpreter as below (although this would never be considered a test per-se if we are talking in engineering terms!)
Finally, we can define the Solution
class, which will allow us to clone any graph given that we are provided at least one of its node:
So what does the code above do? Quite clearly, the cloneGraph
function in lines 5-7 takes as input a node belonging to the graph we wish to clone, and then initializes a hash map (or dictionnary if we are talking in Python terms). Finally it invokes the cloneNode
function that is defined in lines 9-18. First, the cloneNode
function checks for an empty node and if this statement is met returns a None
value. The next step (lines 12-13) is to check whether the input node is already in nodeMap
, which would indicate it has already been processed. If this condition is met, then we simply return label of the node (for reasons that will become clear in the next paragraph).
At this point, we get to the meaty part of our solution. Line 14 with the statement newNode = Node(node.label)
initiates a new node with the same label as the input node and no neighbors (the default for the Node
class). Next, we add the newly created newNode
object to the hash map nodeMap
. Finally, we iterate through all known neighbors of the input node, and recursively append the results of calling cloneNode
to each of those neighbors. In doing so, nodes already cloned in nodeMap
will simply be appended to the neighbor list of newNode
(because of the conditional statement in lines 12-13), while all others will also be recursively added to the nodeMap
hash map. This will have the direct effect of cloning the entire original graph to the nodeMap
hashmap! And we are done!
R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.