Debugging lab: graph bugs in Python

Why this matters

Graph code fails in quiet ways. A search can return a wrong answer that looks plausible, or it can stop with an error message that does not mention graphs at all. A beginner who sees RecursionError: maximum recursion depth exceeded may think the problem is in the error handling, when the real cause is a loop in the graph that the code never stops following.

This lesson takes three bugs that appear again and again in graph code. For each one you will see the symptom, the real output from running the code, the cause, and the fix. The lesson does not teach new algorithms. The earlier lessons in this module covered breadth-first search (BFS), depth-first search (DFS) and the rest. Here the question is only: why did the code go wrong, and how do you find out?

Words used in this lesson

• Vertex: a point in a graph, such as a town, a task or a web page. In Python code it is usually an integer index, 0, 1, 2, and so on.
• Edge: a link between two vertices. A directed edge goes one way only. An undirected edge goes both ways.
• Adjacency list: a table where each vertex has a list of the vertices it links to. In Python this is a list of lists. graph[0] is the list of vertices that vertex 0 links to.
• Cycle: a path that starts and ends at the same vertex, such as 0 to 1 and back to 0.
• Visited set: a set that records every vertex the search has already entered, so the search does not enter it again. A Python set stores each value once, and x in s checks whether x is in the set.
• Deque: a double-ended queue from the collections module. Use append and popleft for a queue (first in, first out), or append and pop for a stack (last in, first out).
• Recursion: a function that calls itself.
• Call stack: the memory where Python keeps one record for each function call that has not finished yet. Python limits how deep this can grow. The limit is a number you can read with sys.getrecursionlimit().
• RecursionError: the exception Python raises when the call stack would grow past that limit. It is a kind of RuntimeError, which a program can catch.
• Reachable: a vertex is reachable from a start vertex when you can get from the start to it by following edges in their direction.

A method for finding graph bugs

Graph bugs are easier to find when you use the same steps each time.

1. Draw the graph on paper with arrows for directed edges. Use a small example, five vertices or fewer.
2. Print the adjacency list. Check that each vertex lists exactly the neighbours you drew.
3. Trace the search by hand on the small graph, writing down the visited set and the queue or stack after each step.
4. Compare your trace with what the program prints.
5. Check the search rule, such as where you mark a vertex as visited.

Step 2 catches the edge direction bug (bug 2). Step 5 catches a missing or late visited check. Bug 3 only shows on a long path, so ask how long the path can be. The example programs in this lesson print little, so the printed output is easy to read.

Bug 1: no visited set

A search must not enter a vertex twice when the graph has a cycle. If it does, it can walk around the cycle forever. Look at this graph with two vertices. Vertex 0 links to 1, and vertex 1 links back to 0:

0 -> 1
1 -> 0

In Python this graph is the list [[1], [0]]. The first inner list says that vertex 0 links to [1]. The second says that vertex 1 links to [0].

Here is a recursive DFS that forgets the visited set:

def dfs_no_visited(graph, node):
    for nxt in graph[node]:
        dfs_no_visited(graph, nxt)

The function visits 0, then calls itself on 1, then calls itself on 0 again, and so on. Nothing stops the cycle. Each call adds a record to the call stack, and Python raises RecursionError when the depth passes the limit of 1000. The error is raised by the call that goes one level too deep.

The next program runs the function on the two-vertex cycle inside a try block. The except clause catches the error and prints a message. The program also runs the fixed version, which is explained below.

Its output is:

bug 1: caught RecursionError: maximum recursion depth exceeded
fixed DFS order: [0, 1]

The fix is to record each vertex when the search enters it, and to stop when the vertex is already recorded:

def dfs_with_visited(graph, node, visited, order):
    if node in visited:
        return
    visited.add(node)
    order.append(node)
    for nxt in graph[node]:
        dfs_with_visited(graph, nxt, visited, order)

The key lines are the two that come first: the if node in visited check, then visited.add(node). The check returns early when the vertex was already entered. The add records the vertex, so the next visit to it stops at the check. The two lines are next to each other, and nothing else changes visited between them. Java has a method, Set.add, that returns false when the value is already present, so Java code can do both in one line. Python's set.add returns None, so the Python version uses two lines.

Breadth-first search without a visited set

BFS without a visited set does not crash right away. It keeps adding vertices to the queue, so the queue grows. The following program takes at most a fixed number of steps, so the growth can be seen. It runs on a triangle, where each of the three vertices links to the other two. The triangle is [[1, 2], [0, 2], [0, 1]].

The output for six steps is:

pop 1: took 0, queue size now 2
pop 2: took 1, queue size now 3
pop 3: took 2, queue size now 4
pop 4: took 0, queue size now 5
pop 5: took 2, queue size now 6
pop 6: took 0, queue size now 7

Each step removes one vertex and adds two. The queue grows by one every time. Left running without the max_pops limit, this code keeps growing the queue until the computer runs out of memory. Python may then stop the program with a MemoryError, or the operating system may stop it first. It takes much longer to fail than a recursion error, so the program can look stuck.

The fix is the same idea as in DFS. Mark each vertex when you add it to the queue, not when you remove it:

seen = {start}
queue = deque([start])
while queue:
    node = queue.popleft()
    for nxt in graph[node]:
        if nxt not in seen:
            seen.add(nxt)
            queue.append(nxt)

The check nxt not in seen is followed by seen.add(nxt). A vertex is added to the queue only on the first time it is seen, so each vertex enters the queue at most once.

Bug 2: directed edges stored as undirected

Many graphs have edges with one direction. Task scheduling is a common example. An edge from task 0 to task 1 means "task 0 must finish before task 1 starts". Going the other way is not allowed. If you store that edge in both directions, the graph says things that are not true.

Here is a small task graph with two edges. The edge 0 to 1 means task 0 comes before task 1. The edge 1 to 2 means task 1 comes before task 2:

tasks = [(0, 1), (1, 2)]

The correct way to build the adjacency list adds each edge once, in the direction it has. A list of n empty lists is made first, so that every vertex has a list even when it has no edges:

def build_directed(n, edges):
    graph = [[] for _ in range(n)]
    for a, b in edges:
        graph[a].append(b)
    return graph

The wrong way adds the edge in both directions. The mistake is one extra line:

def build_wrong_undirected(n, edges):
    graph = [[] for _ in range(n)]
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)
    return graph

The next function is a BFS that lists the vertices reachable from a start vertex. It follows edges only in the direction the adjacency list gives. The following program contains both builders, the BFS and the three checks:

The output is:

wrong graph from 2: [2, 1, 0]
correct graph from 2: [2]
correct graph from 0: [0, 1, 2]

Read the first line. The wrong graph says that starting at task 2, you can reach tasks 1 and 0. That is false. Task 2 has no outgoing edge, so nothing can be reached from it. The correct graph shows exactly that: [2]. Starting at task 0, you reach all three tasks, because 0 leads to 1 and 1 leads to 2.

The effect in a real program is serious. A scheduler built on the wrong graph would find dependency loops, such as 0 to 1 and back, that the task rules never mention. It could then refuse to schedule work that is free to run.

A second example of the same bug

Take two edges from one vertex: 0 to 1 and 0 to 2. Starting from 1, the directed graph reaches only 1. The undirected graph reaches 0 and 2 as well. The same two builders and the same BFS give this result:

exercise 2 directed from 1: [1]
exercise 2 undirected from 1: [1, 0, 2]
exercise 2 directed from 0: [0, 1, 2]

The rule to check is simple. When the problem statement says "must come before", "depends on" or "links to", the edge has one direction. When it says "are connected" or "are friends", the edge may have both directions. Write the rule next to the code that builds the graph, so the reader can see it.

Bug 3: recursion too deep for the call stack

Recursion is a clean way to write DFS, but each recursive call uses a record on the call stack. Python's limit is 1000 by default. A walk that goes very deep, such as along a long path, can pass that limit even when the graph has no cycles at all.

The next function builds a path with 200,000 vertices. Vertex i links to vertex i + 1, and the last vertex has no outgoing edge. The list comprehension [i + 1] if i + 1 < n else [] makes one inner list for each vertex. It reads as: the list [i + 1] when there is a next vertex, otherwise the empty list [].

def path(n):
    return [[i + 1] if i + 1 < n else [] for i in range(n)]

A recursive count of the reachable vertices looks like this:

def recursive_count(graph, node, visited):
    if node in visited:
        return
    visited.add(node)
    for nxt in graph[node]:
        recursive_count(graph, nxt, visited)

The visited set is correct here. There is no cycle. The problem is the depth. Starting at vertex 0, the walk needs 200,000 nested calls before it can return, and the limit of 1000 is passed long before that. A program that imports path and recursive_count and calls recursive_count(path(200000), 0, set()) on line 3, with no try block, shows the error. The file paths are shortened here, and the line numbers and the repeat count depend on the file and the Python version:

Traceback (most recent call last):
  File ".../uncaught.py", line 3, in <module>
    recursive_count(path(200000), 0, set())
    ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^
  File ".../lab_funcs.py", line 10, in recursive_count
    recursive_count(graph, nxt, visited)
    ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^
  File ".../lab_funcs.py", line 10, in recursive_count
    recursive_count(graph, nxt, visited)
    ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

The last line says what happened: the call stack went past its limit. The traceback lines show where the program was when it failed. When the same line repeats many times, Python prints [Previous line repeated N more times] in place of the repeats. Your count and file paths may differ.

Catching the error inside the program prints a message instead of stopping:

try:
    recursive_count(path(200000), 0, set())
except RecursionError as e:
    print("bug 3: caught RecursionError:", e)

bug 3: caught RecursionError: maximum recursion depth exceeded

Catching the error is only a way to see the symptom. It does not fix the walk, because the walk still cannot finish on a path that long.

The fix: use an explicit stack

An explicit stack is a list that you manage yourself. A Python list works as a stack with append and pop. The list lives in heap memory, the part of memory that grows as the program needs it, not on the call stack. The function pushes the start vertex, pops one vertex at a time, and pushes its neighbours. It uses extend to push all of them at once:

def iterative_count(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        stack.extend(graph[node])
    return len(visited)

The check node in visited happens when the vertex is popped, not when it is pushed. That is safe, because a vertex can be pushed more than once, and the second copy is skipped when it is popped. It keeps the count of reachable vertices correct.

The next program builds the 200,000-vertex path and runs the iterative count on it:

The output is:

iterative count: 200000

The program finishes, and the count matches the number of vertices on the path.

Two things make this work. The list grows as needed, so the depth is limited by memory rather than by the call stack limit. The loop does not nest, so no call record builds up.

Python also has sys.setrecursionlimit(), which raises the limit. On the machine used to check this lesson, a limit of 300000 let the recursive count finish with 200,000 vertices. That is a setting, not a fix. The walk still makes one call per vertex, and a limit set too high can make Python crash instead of raising an error. The safe limit depends on the machine, so the explicit stack is the better choice for long paths.

Common mistakes

Marking visited after the loop

Some code marks a vertex as visited after it has handled all its neighbours. That is too late. Inside a cycle, the walk comes back to the vertex before it was marked, and the walk never ends.

This small program has three vertices in a loop, 0 to 1, 1 to 2, and 2 back to 0. The bad function marks each vertex only at the end:

def dfs_late_mark(graph, node, visited):
    for nxt in graph[node]:
        if nxt not in visited:
            dfs_late_mark(graph, nxt, visited)
    visited.add(node)

Calling it on the cycle inside a try block prints:

exercise 3: caught RecursionError

The fix is to call visited.add(node) before the loop, as the dfs_with_visited function does.

Checking the visited set on the wrong vertex

A common slip is to check whether node is visited but add nxt to the set, or the other way round. The two names are easy to mix up when the loop variable is called nxt. Use one name for the vertex being entered, and check that name on the line before the add.

Using the return value of set.add

Java's Set.add returns true or false, and many Java programs write if (seen.add(next)). In Python, set.add returns None. The if test treats None as false, so this code never runs its body and shows no error:

seen = set()
if seen.add(1):
    print("new")
print(seen)

The output is:

{1}

The print inside the if never runs, and the set still gets the value. Write the check and the add on separate lines, as shown in the fixes above.

Reading an error with the wrong question

A RecursionError is a sign that a call never stopped or that the walk is too deep. In graph code, that usually means a missing visited check or a path longer than the call stack limit. Ask two questions: does the graph have a cycle, and is the walk recursive? If the answer to the first is yes, look for the visited set. If the answer to the second is yes, and the graph is large, switch to an explicit stack.

Forgetting the direction when building the graph

If a graph problem says one thing must happen before another, store that as a directed edge. Check the graph build code against the problem statement, one edge at a time. The output for the directed and undirected versions shows the mistake clearly, so compare them on a small example when in doubt.

Practice

Each exercise is followed by its answer. Try each one on paper before you read the answer.

Exercise 1

The graph has three vertices in a loop: 0 to 1, 1 to 2, and 2 to 0. A recursive DFS starts at 0 and has no visited set. What happens?

Show the answer

The walk goes 0, 1, 2, 0, 1, 2, and so on without end. Each call adds a record to the call stack, so after about 1000 calls Python raises RecursionError: maximum recursion depth exceeded. Adding a visited set that is checked before each entry stops the walk after each vertex is visited once.

Exercise 2

Two edges are 0 to 1 and 0 to 2. The graph is directed. Starting at 1, what is the list of reachable vertices? What would the list be if the edges were stored as undirected?

Show the answer

Starting at 1 in the directed graph, the only reachable vertex is 1, so the list is [1]. In the undirected version, 1 links back to 0, and 0 links to 2, so the list is [1, 0, 2]. The program prints exactly those two lists.

Exercise 3

This DFS has a bug. Explain it and say where the fix goes.

def dfs_late_mark(graph, node, visited):
    for nxt in graph[node]:
        if nxt not in visited:
            dfs_late_mark(graph, nxt, visited)
    visited.add(node)

Show the answer

The vertex is added to visited after the loop, so during a cycle the search enters the same vertex again before it is marked. The walk then recurses until the call stack limit is reached, and Python raises RecursionError. The fix is to move visited.add(node) to the top of the function, before the loop. With the add at the top and a check before it, the function can return early when the vertex is already visited, as dfs_with_visited does.

Exercise 4

A path has 50 vertices, and the walk from the start visits each one in order. Would a recursive DFS on that path with a visited set need 50 nested calls or 1 nested call?

Show the answer

It needs 50 nested calls. Each call handles one vertex and then calls the next vertex. The depth equals the number of vertices on the path. Fifty is well under the default limit of 1000, so this walk finishes. The depth is what matters for RecursionError, and the earlier example with 200,000 vertices went past the limit for that reason.

Exercise 5

Explain in your own words why the iterative version with a list used as a stack does not raise RecursionError on the 200,000-vertex path.

Show the answer

The list stores the vertices to visit in heap memory, which grows as the program needs it. The loop does not call itself, so no call record is added for each vertex. The depth of the walk is limited by the amount of memory, not by the call stack limit. The program prints iterative count: 200000.

Summary

• A search needs a visited set when the graph has cycles. Check the set first, then add to it, on the lines right next to each other.
• Without a visited set, BFS keeps growing its queue, and recursive DFS passes the call stack limit and raises RecursionError.
• Store an edge in one direction when the problem gives it a direction, and check the graph build against the problem statement.
• A RecursionError on a long path means the recursion is too deep. Use a list as a stack to keep the depth in heap memory.
• Print a small graph's adjacency list and trace the search by hand before you change any code.