Problem overview
The function clone_graph receives node 1 of a connected, undirected graph, as an Option<Rc<RefCell<Node>>>, and returns a deep copy of the graph: the copy of node 1. The graph has n nodes, node i has the value i, and every node can be reached from node 1. A deep copy is made of exactly n brand-new nodes with the same values, and the neighbor list of each new node holds the new nodes of the original's neighbors, in the same order. No node of the copy may be a node of the original. For an empty graph the function gets None and returns None.
The lesson provides the node type, so there is nothing to define. Each node has a val of type i32 and a vector neighbors of Rc<RefCell<Node>>, and Node::new(val) makes a new node, already wrapped in Rc<RefCell<...>>, with no neighbors.
The examples give a graph by adjacency lists: adjList[i - 1] holds the values of node i's neighbors. For [[2, 4], [1, 3], [2, 4], [1, 3]] the graph is a square of four nodes, and the copy has the same shape, made of four new nodes. For [[]] it is a single node with no neighbors. For [] it is the empty graph.
The lesson asks for O(V + E) time and O(V) extra space, where V is the number of nodes and E the number of edges.
Approach: a map from each original node to its copy
Copying a node is easy. The hard parts are the links: a copy's neighbors must be the copies of the neighbors, never the originals, and the graph has cycles, so a naive walk would go around forever.
The fix is a hash map from each original node to its copy. It does two jobs. It finds the copy of any node already met, so a link can point to it. And it tells which nodes have been met, so no node is copied twice and the search can't loop.
The search is a breadth-first search with a queue:
- Make the copy of node 1 and put node 1 in the queue.
- Take a node
currentout of the queue. Its copy exists, but its neighbor list is still empty. - For each neighbor of
current: if the neighbor has no copy yet, make one and put the neighbor in the queue. Then append the neighbor's copy to the neighbor list ofcurrent's copy.
A node joins the queue exactly when its copy is made, so each node is queued once. The neighbors are visited in the original order, so each copied list keeps that order. A recursive depth-first search with the same map would also work.
The key to the map is the node's address, not its value or its place in the graph. Two nodes with the same value would still have different addresses, and the address is what makes a node the same node.
Step by step
- Unwrap the
Option. Shadownodewith amatch: forSome(node)it gives the node, and forNoneit returnsNonefrom the function at once. An empty graph has nothing to copy. - Create the map
copieswithHashMap::new(). Rust infers its types from the first insert. - Insert the first copy. The key is
Rc::as_ptr(&node), the address of the node inside itsRc, and the value is a new node made byNode::newfromnode.borrow().val. Theborrow()call gives read access to the contents of theRefCell. - Create the queue as a
VecDeque. It holds the nodes whose neighbors still have to be copied. - Push a clone of
nodewithpush_back. Cloning anRccopies the pointer, not the node. - Loop with
while let Some(current) = queue.pop_front(), which ends when the queue is empty. - Loop over the neighbors of
currentwithcurrent.borrow().neighbors.iter(). - Check for a missing copy with
!copies.contains_key(&Rc::as_ptr(neighbor)). No copy means the search meets this node for the first time. - Make the neighbor's copy inside that
if, the same way as the first one. - Queue the neighbor with a clone, so its own neighbors get copied when it leaves the queue.
- Link the copies. Clone the neighbor's copy into
neighbor_copyand push it onto the neighbors ofcurrent's copy, reached withcopies[&Rc::as_ptr(¤t)].borrow_mut(). This line runs for every neighbor, new or not, because every edge needs a link from this node's copy. - Return the copy of
nodewrapped inSome: a clone ofcopies[&Rc::as_ptr(&node)], with no semicolon. The graph is connected, so every node was reached and every list was filled.
The solution in Rust
use std::collections::{HashMap, VecDeque};
impl Solution {
fn clone_graph(node: Option<Rc<RefCell<Node>>>) -> Option<Rc<RefCell<Node>>> {
let node = match node {
Some(node) => node,
None => return None,
};
let mut copies = HashMap::new();
copies.insert(Rc::as_ptr(&node), Node::new(node.borrow().val));
let mut queue = VecDeque::new();
queue.push_back(node.clone());
while let Some(current) = queue.pop_front() {
for neighbor in current.borrow().neighbors.iter() {
if !copies.contains_key(&Rc::as_ptr(neighbor)) {
copies.insert(Rc::as_ptr(neighbor), Node::new(neighbor.borrow().val));
queue.push_back(neighbor.clone());
}
let neighbor_copy = copies[&Rc::as_ptr(neighbor)].clone();
copies[&Rc::as_ptr(¤t)].borrow_mut().neighbors.push(neighbor_copy);
}
}
Some(copies[&Rc::as_ptr(&node)].clone())
}
}
The Rust details worth a closer look:
Rc<RefCell<Node>>.Rclets several owners share one node, which a graph needs, because many nodes point to the same neighbor.RefCellallows changing the node through a shared handle, with the borrowing rules checked while the program runs:borrow()reads, andborrow_mut()writes. Breaking those rules, for example by holding aborrow_mut()while another borrow of the same node is alive, panics.- Why the two borrows in the loop are safe. The loop holds
current.borrow()for its whole length while it writes tocopies[...].borrow_mut(). These are different nodes, the original and the copy, so they don't conflict. Rc::as_ptras the key. It returns a raw pointer to the node'sRefCell, which can be hashed and compared like a number. Raw pointers don't needunsafeto be created or compared, only to be dereferenced, and the code never dereferences them. Two nodes have the same pointer only when they are the same node.- The two meanings of
clone(). Callingclone()on anRccopies the pointer and raises a count. It doesn't copy the node. That is whyqueue.push_back(node.clone())is cheap, and whycopies[...].clone()hands out another handle to the same copy. - Indexing a
HashMap.copies[&key]returns the value for the key and panics if the key is missing. It is safe here because a copy is inserted before any use. matchas an expression. The arm that matches givesnodeits value, andreturn Noneleaves the function from inside the other arm.- Memory. Nodes of a cycle point to each other through
Rc, so their counts never reach zero and the memory isn't freed. For a single call that returns, this is harmless here.
Complexity
Time: O(V + E). Each node is made once and queued once. Each edge is looked at twice, once from each end, and each look costs a constant amount of work: a hash lookup and a push.
Space: O(V) extra. The map holds one entry per node, and the queue holds at most all of them. The copy itself is also O(V + E), since it holds all the neighbor lists, but it is the answer and not extra space.
Edge cases and common mistakes
- The empty graph. With
None, thematchreturnsNonebefore anything reads a node. - A single node. For
[[]], the loop finds no neighbors, and the copy is one new node with the value 1 and an empty list. - Returning the original. The result must be made of new nodes. Pointing a copy's list at the original neighbor, instead of
neighbor_copy, makes the copy share nodes with the original. - Keying the map by value. Here the values happen to be unique, but the address is the right key in general, because it identifies the node itself.
- Linking only new neighbors. The link line must run for every neighbor, not only inside the
if. Otherwise an edge to an already copied node would be missing from the copy. - Queueing a node twice. A node must enter the queue only when its copy is made. Queueing at every meeting would give its copy a neighbor list that grows each time.
- Cycles. Without the map check, the square graph
[[2, 4], [1, 3], [2, 4], [1, 3]]would be walked forever.
Testing
[[2, 4], [1, 3], [2, 4], [1, 3]]gives[[2, 4], [1, 3], [2, 4], [1, 3]], with 4 nodes, none shared with the original.[[]]gives[[]], with 1 node.[]gives[].[[2], [1, 3], [2]]gives[[2], [1, 3], [2]], a chain of 3 nodes.[[3, 2], [1, 3], [2, 1]]gives[[3, 2], [1, 3], [2, 1]], a triangle whose neighbor order is kept.
