Deduplicating the Result Is Not Deduplicating the Work

Here’s a recursive traversal that looks completely fine, returns entirely correct answers, and is exponential:

def get_nodes(self, node_list):
    node_list.add(self)
    for edge in self.edges:
        edge.to_node.get_nodes(node_list)
    return node_list

It collects into a set, so no node appears twice in the output. The bug is that the set deduplicates the result and nothing deduplicates the work.

Why it blows up

Every time the walk reaches a node, it recurses into that node’s children, whether or not it has already done so. The set absorbs the duplicate additions silently, so the answer is right, and the number of recursive calls is the number of distinct paths through the graph rather than the number of nodes.

On a tree those are the same number, which is why this shape survives code review. On any graph where a node is reachable by more than one route, they diverge fast. Take a diamond:

     A
    / \
   B   C
    \ /
     D

D is expanded twice, once via B and once via C. Stack diamonds and the path count doubles per layer. A modest layered graph, fifteen layers of width three, has on the order of three to the fifteenth paths, which is around fourteen million recursive calls to enumerate four dozen nodes. In petersburg, my decision-graph library, that’s not a pathological input, it’s the normal shape produced by building a graph from a dictionary or an adjacency matrix.

The fix, and the part that surprised me

For nodes, the fix is one line. Before recursing, check whether you’ve already been expanded:

def get_nodes(self, node_list):
    if self in node_list:
        return node_list
    node_list.add(self)
    for edge in self.edges:
        edge.to_node.get_nodes(node_list)
    return node_list

Now the accumulator is doing double duty: it records results and marks visited nodes, and since those are the same set of things, that works.

Edges are where it gets interesting, because the same trick does not transfer:

def get_edges(self, edge_list):
    for edge in self.edges:
        edge_list.add(edge)
        edge.to_node.get_edges(edge_list)   # still exponential
    return edge_list

You cannot guard on if edge in edge_list, because a node can be reached by several distinct edges. In the diamond, edges B to D and C to D are two different edges that both lead to D. Skipping the second edge because it’s “already seen” would be wrong (it’s a new edge and belongs in the output), and not skipping the expansion of D is the exponential blowup you’re trying to fix.

The accumulator is a set of edges. The thing you need to deduplicate is nodes. They’re different types and different sets:

def get_edges(self, edge_list, visited=None):
    if visited is None:
        visited = set()          # created once at the top of the walk
    if self in visited:
        return edge_list
    visited.add(self)
    for edge in self.edges:
        edge_list.add(edge)      # every edge is collected, always
        edge.to_node.get_edges(edge_list, visited)
    return edge_list

Every edge still gets added, so the output is unchanged, including the multiple in-edges of a converging node. Each node gets expanded exactly once, so the walk is linear in nodes plus edges. The visited=None default keeps the signature backward compatible for existing callers doing get_edges(set()).

The two questions

The reason I like this example is that it forces a distinction I now apply to every recursive walk. There are two separate questions, and conflating them is the bug:

• “Have I already returned this?” That’s the accumulator, and its type is whatever you’re collecting.
• “Have I already expanded this?” That’s the visited set, and its type is whatever you’re recursing over.

When you’re collecting nodes and recursing over nodes, one set answers both and you get away with it. The moment those two types differ (collecting edges, recursing over nodes; collecting file contents, recursing over directories; collecting matches, recursing over states) you need two structures, and using one is either wrong output or exponential work.

Testing for it

An asymptotic bug does not fail a correctness test, so you need a test that fails on time. Two that I’d write:

def test_diamond_expands_each_node_once():
    graph = diamond_graph()          # A -> B, A -> C, B -> D, C -> D
    with count_calls(Node.get_edges) as calls:
        graph.edge_list()
    assert calls.count == 4          # one per node, not one per path

def test_deep_layered_graph_finishes_quickly():
    graph = layered_graph(layers=15, width=3)
    start = time.monotonic()
    graph.edge_list()
    assert time.monotonic() - start < 1.0

The second one is a wall-clock budget, which is normally a smell in a test suite. Here it’s the assertion that matches the defect: the old code cannot pass it on any machine, and the new code passes it by four orders of magnitude, so it’s nowhere near flaky. A generous budget on a case with an exponential gap is a legitimate test.

What it bought

The nice thing about fixing a traversal primitive is that everything above it gets faster at once. In petersburg, node_list() and edge_list() sit under to_networkx(), to_mermaid(), analyze_sensitivity(), and identify_critical_parameters(). One guard in each of two methods, and every one of those got faster without knowing anything happened.

That’s the general argument for looking hard at your lowest-level walk. It’s usually twenty lines, it’s usually written early when the graphs are small, and everything else in the library is standing on it.