DSA Cloning a Graph

The problem

Cloning a graph builds a full copy of it from fresh node objects. The copy holds the same values and the same neighbour links as the original. No node object is shared between the two graphs.

A graph here is a set of nodes, and each node holds a value and a list of neighbour nodes. Links run both ways in these cases, and cycles are everywhere, since a neighbour links back.

cases = [
    ("triangle", {1: [2, 3], 2: [1, 3], 3: [1, 2]}),
    ("ring", {1: [2, 4], 2: [1, 3], 3: [2, 4], 4: [1, 3]}),
    ("single node", {1: []}),
]
for name, adj in cases:
    print(name)
    for val in sorted(adj):
        print(" node", val, "neighbours", sorted(adj[val]))

The answer for each case is a clone with exactly this shape. The clone must also stay unchanged when the original is later edited. That second demand is what makes the copy a clone rather than a view.

Intuition: copy the node, reuse its neighbours

The first idea copies one node and points the copy at the original neighbours. It is fast and it looks right in a printout. It is not a copy of the graph at all, because the neighbour nodes are still the original objects.

A second naive idea copies each node fresh every time it is met. On a cycle that idea either loops forever or mints a second copy of a node it already copied. The links then point at different objects that claim the same value.

class Node:
    def __init__(self, val):
        self.val = val
        self.neighbors = []

a = Node(1)
b = Node(2)
a.neighbors = [b]
b.neighbors = [a]
shallow = Node(a.val)
shallow.neighbors = a.neighbors
print("neighbour of the copy is the original b:", shallow.neighbors[0] is b)
b.val = 99
print("neighbour value seen through the copy:", shallow.neighbors[0].val)
first_copy = Node(a.val)
second_copy = Node(a.val)
print("two fresh copies of one node are one object:", first_copy is second_copy)

Both failures come from the same gap. The copying process has no memory of which nodes it already copied. A correct clone needs that memory before it needs anything else.

Brute force: describe the graph, then rebuild it from the description

One working method avoids the memory problem in two stages. The first stage writes a description of the graph as values and neighbour values. The second stage builds fresh nodes from the description and wires them by value.

The method is correct when every value is unique, as in these cases. It pays for three passes and a full description, and it leans on values as identities, which the graph itself never promised.

class Node:
    def __init__(self, val):
        self.val = val
        self.neighbors = []
def build(adj):
    nodes = {v: Node(v) for v in adj}
    for v, nbs in adj.items():
        nodes[v].neighbors = [nodes[n] for n in nbs]
    return nodes


def describe(start):
    seen = {}
    stack = [start]
    seen[start.val] = start
    while stack:
        node = stack.pop()
        for nb in node.neighbors:
            if nb.val not in seen:
                seen[nb.val] = nb
                stack.append(nb)
    lines = []
    for val in sorted(seen):
        lines.append((val, sorted(n.val for n in seen[val].neighbors)))
    return lines

def clone_via_description(start):
    desc = describe(start)
    fresh = {val: Node(val) for val, nbs in desc}
    entries = 0
    for val, nbs in desc:
        entries += len(nbs)
        fresh[val].neighbors = [fresh[n] for n in nbs]
    return fresh[start.val], len(desc), entries

nodes = build({1: [2, 4], 2: [1, 3], 3: [2, 4], 4: [1, 3]})
copy_root, node_count, entries = clone_via_description(nodes[1])
print("clone:", describe(copy_root))
print("nodes described:", node_count)
print("neighbour entries wired:", entries)
print("copy shares the root object:", copy_root is nodes[1])

The rebuild clones the ring in three passes over its shape. The description alone holds eight neighbour entries for four nodes. The optimal method below keeps the same memory in a map and finishes in one pass.

The optimal solution: an old-to-new map, filled on first sight

The state is a map from each original node to its clone. A node is cloned once, at the moment the search first reaches it, and every later meeting reads the clone back out of the map.

The walk is a stack search from the start node. Each popped node appends the clone of each neighbour to its own clone neighbour list. Map lookups guarantee those appends point at clones, never at originals.

class Node:
    def __init__(self, val):
        self.val = val
        self.neighbors = []
def build(adj):
    nodes = {v: Node(v) for v in adj}
    for v, nbs in adj.items():
        nodes[v].neighbors = [nodes[n] for n in nbs]
    return nodes


def describe(start):
    seen = {}
    stack = [start]
    seen[start.val] = start
    while stack:
        node = stack.pop()
        for nb in node.neighbors:
            if nb.val not in seen:
                seen[nb.val] = nb
                stack.append(nb)
    lines = []
    for val in sorted(seen):
        lines.append((val, sorted(n.val for n in seen[val].neighbors)))
    return lines
def clone_graph(start):
    if start is None:
        return None
    clones = {}
    stack = [start]
    clones[start] = Node(start.val)
    while stack:
        node = stack.pop()
        for nb in node.neighbors:
            if nb not in clones:
                clones[nb] = Node(nb.val)
                stack.append(nb)
            clones[node].neighbors.append(clones[nb])
    return clones[start]

for name, adj in [("triangle", {1: [2, 3], 2: [1, 3], 3: [1, 2]}), ("ring", {1: [2, 4], 2: [1, 3], 3: [2, 4], 4: [1, 3]}), ("single node", {1: []})]:
    nodes = build(adj)
    copy_root = clone_graph(nodes[1])
    print(name, "clone matches:", describe(copy_root) == describe(nodes[1]), "- shares root:", copy_root is nodes[1])
nodes = build({1: [2, 4], 2: [1, 3], 3: [2, 4], 4: [1, 3]})
copy_root = clone_graph(nodes[1])
nodes[1].val = 99
print("clone after the original is relabelled:", describe(copy_root))

Every case matches its original shape, and no clone shares its root with the original. The relabel test is the stronger proof. The original ring now carries 99, and the clone still reads as the ring from section 1.

Walkthrough: cloning the ring, one pop at a time

The walk starts with node 1 already cloned and on the stack. Each pop wires one clone completely. The printout shows the map keys and the finished neighbour list after each pop.

class Node:
    def __init__(self, val):
        self.val = val
        self.neighbors = []
def build(adj):
    nodes = {v: Node(v) for v in adj}
    for v, nbs in adj.items():
        nodes[v].neighbors = [nodes[n] for n in nbs]
    return nodes


def describe(start):
    seen = {}
    stack = [start]
    seen[start.val] = start
    while stack:
        node = stack.pop()
        for nb in node.neighbors:
            if nb.val not in seen:
                seen[nb.val] = nb
                stack.append(nb)
    lines = []
    for val in sorted(seen):
        lines.append((val, sorted(n.val for n in seen[val].neighbors)))
    return lines

nodes = build({1: [2, 4], 2: [1, 3], 3: [2, 4], 4: [1, 3]})
start = nodes[1]
clones = {}
stack = [start]
clones[start] = Node(start.val)
while stack:
    node = stack.pop()
    for nb in node.neighbors:
        if nb not in clones:
            clones[nb] = Node(nb.val)
            stack.append(nb)
        clones[node].neighbors.append(clones[nb])
    print("wired clone", node.val, "- neighbours", sorted(n.val for n in clones[node].neighbors), "- map holds", sorted(n.val for n in clones))

Node 1 is wired first and creates the clones of 2 and 4 as a side effect. Node 3 is created while node 4 is wired. By the last pop every neighbour already has a clone, so the pop only appends.

Complexity

Each node is cloned once and each neighbour link is followed once per direction, so the time is proportional to the nodes plus the links, written O(V + E). The map holds one entry per node, so the extra space is O(V).

class Node:
    def __init__(self, val):
        self.val = val
        self.neighbors = []

def build_ring(n):
    nodes = {v: Node(v) for v in range(1, n + 1)}
    for v in range(1, n + 1):
        left = v - 1 if v > 1 else n
        right = v + 1 if v < n else 1
        nodes[v].neighbors = [nodes[left], nodes[right]]
    return nodes[1]

def clone_counted(start):
    clones = {}
    links = [0]
    stack = [start]
    clones[start] = Node(start.val)
    while stack:
        node = stack.pop()
        for nb in node.neighbors:
            if nb not in clones:
                clones[nb] = Node(nb.val)
                stack.append(nb)
            clones[node].neighbors.append(clones[nb])
            links[0] += 1
    return len(clones), links[0]

for n in [4, 8, 16]:
    created, links = clone_counted(build_ring(n))
    print("ring of", n, "- clones created:", created, "- links wired:", links)

Doubling the ring doubles both counts. Nothing is cloned twice, and no link is wired twice. The counts grow with the graph and with nothing else.

Edge cases and pitfalls

An empty graph has no start node. The clone of nothing is nothing, and the function returns None before any map work begins.

A self-loop is a node that lists itself as a neighbour. The map already holds its clone when the loop edge is read, so the clone loops to itself. A disconnected node is the opposite trap, since a clone started at node 1 can only reach the component that contains node 1.

class Node:
    def __init__(self, val):
        self.val = val
        self.neighbors = []
def build(adj):
    nodes = {v: Node(v) for v in adj}
    for v, nbs in adj.items():
        nodes[v].neighbors = [nodes[n] for n in nbs]
    return nodes


def describe(start):
    seen = {}
    stack = [start]
    seen[start.val] = start
    while stack:
        node = stack.pop()
        for nb in node.neighbors:
            if nb.val not in seen:
                seen[nb.val] = nb
                stack.append(nb)
    lines = []
    for val in sorted(seen):
        lines.append((val, sorted(n.val for n in seen[val].neighbors)))
    return lines
def clone_graph(start):
    if start is None:
        return None
    clones = {}
    stack = [start]
    clones[start] = Node(start.val)
    while stack:
        node = stack.pop()
        for nb in node.neighbors:
            if nb not in clones:
                clones[nb] = Node(nb.val)
                stack.append(nb)
            clones[node].neighbors.append(clones[nb])
    return clones[start]

print("clone of an empty graph:", clone_graph(None))
solo = Node(1)
copy_solo = clone_graph(solo)
print("single node clone:", describe(copy_solo), "- shares object:", copy_solo is solo)
loop = Node(1)
loop.neighbors = [loop]
copy_loop = clone_graph(loop)
print("self-loop clone:", describe(copy_loop), "- loops to itself:", copy_loop.neighbors[0] is copy_loop)
a = Node(1)
b = Node(2)
a.neighbors = [b]
b.neighbors = [a]
lone = Node(3)
print("clone from node 1 reaches values:", [val for val, nbs in describe(clone_graph(a))])

The last line is a limit of the problem, not a bug. The start node defines the graph to copy. A node in another component is a separate graph and needs its own clone call.