Cloning a Graph

Keep a map from each original node to its copy. Before you copy a node's neighbours, you register the copy of that node in the map. Then, whenever you reach a neighbour, you look it up in the map: if it has already been copied you reuse the existing copy, and if not you create it and copy it too.

The map is what makes the cloning terminate. In a graph with a cycle, a naive recursive clone would revisit the same nodes forever, because there is no point at which the recursion bottoms out. With the map, the second time you meet a node you find its copy already exists and you just link to it.

The mechanism is that the map both records what has been done and provides the identity of the copies. The copy of a node is created before its neighbours are processed, so a cycle back to that node finds the copy already registered and links to it rather than creating a second copy.

The trade-off to name is that the map needs one entry per node, so the space is linear in the size of the graph, and the lookup is a hash operation so the time is also linear. The deeper point is the ordering requirement: creating the copy before recursing is what breaks the cycle, and reversing those two steps reintroduces the infinite recursion. A related detail is that the clone must preserve the graph's structure exactly, including the direction of edges and whether edges are directed or undirected.

Map every original node to its copy as you discover it, using a stack so the traversal never recurses indefinitely.

def clone_graph(node):
    if node is None:
        return None
    mapping = {}
    stack = [node]
    while stack:
        current = stack.pop()
        if current in mapping:
            continue
        mapping[current] = []
        for neighbour in current.neighbours:
            if neighbour not in mapping:
                stack.append(neighbour)
            mapping[current].append(neighbour)
    return mapping


class Node:
    def __init__(self, value):
        self.value = value
        self.neighbours = []


a = Node("a")
b = Node("b")
c = Node("c")
a.neighbours = [b, c]
b.neighbours = [a, c]
c.neighbours = [a, b]

copy = clone_graph(a)
print(sorted(n.value for n in copy))
print(sorted(n.value for n in copy[a.neighbours[0]]))

The outputs are a, b, c and then a, c. The copy contains all three nodes, and the copy of the first neighbour of a, which is b, has the two neighbours a and c, exactly as the original did.

The mechanism is that the mapping is created for a node at the moment it is popped and processed, before its neighbours are visited. When the traversal later reaches a neighbour that is already in the mapping, it links to the existing copy instead of creating a second one, which is what terminates the traversal on a cyclic graph.

The trade-off to name is that this version returns an adjacency map rather than a parallel set of node objects, which is often more convenient for comparing the clone with the original. If you need the copy to be a real object graph with the same class as the original, you create the copy node first and then fill in its neighbour list, which is what the next answer does. The space cost is the mapping, one entry per node, and the traversal is iterative so a very large or very deep graph will not exhaust the call stack.

Create the copy of a node as soon as you discover it, then fill in its neighbour list as you go.

class Node:
    def __init__(self, value):
        self.value = value
        self.neighbours = []


def clone_simple(node):
    if node is None:
        return None
    mapping = {node: Node(node.value)}
    stack = [node]
    while stack:
        current = stack.pop()
        for neighbour in current.neighbours:
            if neighbour not in mapping:
                mapping[neighbour] = Node(neighbour.value)
                stack.append(neighbour)
            mapping[current].neighbours.append(mapping[neighbour])
    return mapping[node]


a = Node("a")
b = Node("b")
a.neighbours = [b]
b.neighbours = [a]

copy = clone_simple(a)
print(copy.value, copy.neighbours[0].value)
print(copy.neighbours[0].neighbours[0] is copy)

The outputs are a and b, and then True. The clone has the same values, and the neighbour of the clone points back at the clone itself, so the cycle has been reproduced in the new graph.

The mechanism is that the copy of a node is registered in the mapping before any of its neighbours are processed. That is the ordering that makes the cycle case work, because when the traversal comes back around to the original node it finds the copy already registered and links to it.

The trade-off to name is the difference between this and the adjacency map version. Here the copy is a real object of the same class as the original, which is what most callers want, but the neighbour lists are built by appending, so the order of the neighbours in the copy matches the order of the neighbours in the original. The cost is the same in both cases: one mapping entry per node. The subtle bug to avoid is appending the same neighbour twice, which happens if you append inside the branch that creates a new copy instead of after it, because a node with two edges to the same neighbour would be added twice.