Debugging lab: graph bugs

Why this matters

Most graph code that beginners write fails in a few predictable ways. The program may never stop, print a wrong count, or crash with no message of its own. The earlier lessons in this module showed how the searches work when they are written correctly. This lesson is the other side: you are given code that is wrong, and your job is to find out why.

Debugging is a skill you build by running small programs and reading the evidence they give you. Each program here is short on purpose. It has one bug, and the output shows the symptom. You will predict what the program should print, run it, read the output, explain the bug in plain words, and then fix it.

The lab uses three bugs.

1. A depth-first search (DFS) or breadth-first search (BFS) without a visited check, so it goes around a cycle forever.
2. A directed graph whose edges are also added in reverse, so the program follows edges that do not exist.
3. A recursive DFS on a long path, which runs out of call stack space.

The searches in the earlier lessons of this module use the same pattern, so the same bugs can appear there.

Setting up the lab

Create a folder for the lab files. Each program below goes in its own file. Compile each one with the same command, changing only the file name and the program name.

g++ -std=c++20 -Wall -o dfs_no_visited dfs_no_visited.cpp

The flags have these meanings. -std=c++20 tells the compiler to use the C++20 rules. -Wall turns on the usual warnings. -o dfs_no_visited sets the name of the program file that the compiler writes. The last part names the source file.

Run each program with a time limit. A time limit stops the program after a set number of seconds, so a program that never ends does not hang your terminal. The timeout command does this, and echo "exit $?" prints the exit code of the last command. An exit code is the number a program returns when it finishes. Zero means success. Other numbers mean something went wrong.

timeout 10 ./dfs_no_visited; echo "exit $?"

Keep three habits while you work through the lab. Write down what you expect the program to print before you run it. Read the whole output, including the last line. When the output is wrong, change one thing at a time and run again.

Lab 1: the search that never stops

The first program is a DFS that counts how many nodes it can reach from node 0. The graph has three nodes in a cycle. A cycle is a path that leads back to where it started. Here the edges are 0 to 1, 1 to 2 and 2 to 0.

#include <iostream>
#include <vector>
 
using Graph = std::vector<std::vector<int>>;
 
void dfs(const Graph& g, int u, int& count) {
    ++count;
    for (int v : g[u]) {
        dfs(g, v, count);  // BUG: no visited check
    }
}
 
int main() {
    Graph g = {{1}, {2}, {0}};  // 0 -> 1 -> 2 -> 0
    int count = 0;
    dfs(g, 0, count);
    std::cout << "reachable: " << count << '\n';
    return 0;
}

The correct answer is 3. Before running it, look at the call to dfs. Node 0 calls node 1. Node 1 calls node 2. Node 2 calls node 0. Node 0 calls node 1 again, and so the calls go around the cycle without end. The function never returns, so the line that prints the count is never reached.

Run it.

timeout 10 ./dfs_no_visited; echo "exit $?"

The output on this machine has no count, only the exit code:

exit 139

Some shells also print a line such as Segmentation fault ./dfs_no_visited, with a process ID number in front that changes on each run. The exit code 139 comes from a segmentation fault, which means the program tried to use memory it does not own. Here the memory in question is the call stack. The call stack is the area of memory where the computer keeps track of the function calls that are still running. Each call uses some of that space, and the space is limited. On this machine the limit is 8192 kilobytes, which the command ulimit -s prints. The program never printed a count because the calls went on until the stack ran out.

The fix is a list of nodes already visited, sometimes called a visited array. Before a call goes into a node, it checks whether that node was seen. The list is a std::vector<bool> with one entry per node.

#include <iostream>
#include <vector>
 
using Graph = std::vector<std::vector<int>>;
 
void dfs(const Graph& g, int u, std::vector<bool>& seen, int& count) {
    seen[u] = true;
    ++count;
    for (int v : g[u]) {
        if (!seen[v]) {
            dfs(g, v, seen, count);
        }
    }
}
 
int main() {
    Graph g = {{1}, {2}, {0}};
    std::vector<bool> seen(g.size(), false);
    int count = 0;
    dfs(g, 0, seen, count);
    std::cout << "reachable: " << count << '\n';
    return 0;
}

Run it. The output is:

reachable: 3

The new code marks a node as seen when the call enters it. Any later call that reaches the same node sees the mark and does not go in again. That breaks every cycle, because a cycle must come back to a node that was already marked.

Lab 2: the BFS that keeps growing

The second program is a BFS with the same missing check. This time the graph has a node with two outgoing edges, so the bug shows up in the queue instead of the call stack. The program prints the node it removes from the queue at each step and the size of the queue. It stops after eight removals, so it finishes.

#include <iostream>
#include <queue>
#include <vector>
 
using Graph = std::vector<std::vector<int>>;
 
int main() {
    Graph g = {{1, 2}, {0}, {0}};  // 0 -> 1, 0 -> 2, 1 -> 0, 2 -> 0
    std::queue<int> q;
    q.push(0);
    for (int step = 0; step < 8; ++step) {  // stop after 8 pops so the program ends
        int u = q.front();
        q.pop();
        std::cout << "visit " << u << ", queue size now " << q.size() << '\n';
        for (int v : g[u]) {
            q.push(v);  // BUG: no visited check
        }
    }
    return 0;
}

Predict the order of the nodes. Node 0 is visited first. It pushes 1 and 2. Node 1 is visited next, and it pushes 0 again. Node 0 is now in the queue for a second time. The output confirms it:

visit 0, queue size now 0
visit 1, queue size now 1
visit 2, queue size now 1
visit 0, queue size now 1
visit 0, queue size now 2
visit 1, queue size now 3
visit 2, queue size now 3
visit 1, queue size now 3

Node 0 appears three times in these eight lines. Each time it is visited, it pushes 1 and 2 again, so the queue gets longer. In a graph where this loop never ends, the queue would grow without limit and the program would eventually run out of memory. The stop after eight pops is only there so this lab can finish.

The fix is the same idea as in Lab 1. A node is marked when it is first pushed, and it is not pushed again. Note that the mark goes on when the node joins the queue, not when it leaves. If the mark waited until the node was removed, the same node could be pushed many times before its first removal.

#include <iostream>
#include <queue>
#include <vector>
 
using Graph = std::vector<std::vector<int>>;
 
int main() {
    Graph g = {{1, 2}, {0}, {0}};
    std::vector<bool> seen(g.size(), false);
    seen[0] = true;
    std::queue<int> q;
    q.push(0);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        std::cout << "visit " << u << ", queue size now " << q.size() << '\n';
        for (int v : g[u]) {
            if (!seen[v]) {
                seen[v] = true;
                q.push(v);
            }
        }
    }
    return 0;
}

The output is:

visit 0, queue size now 0
visit 1, queue size now 1
visit 2, queue size now 0

Each node is visited once. The loop ends when the queue is empty, so no time limit is needed.

Lab 3: the edges that point the wrong way

The third program builds a graph from a list of directed edges. Save it as directed_as_undirected.cpp. A directed edge goes one way, from a start node to an end node. A road that allows traffic in only one direction is a good picture of it. The program then finds the nodes reachable from node 0.

The edges are 0 to 1, 2 to 1 and 3 to 0. From node 0 you can go to node 1. Nothing else is reachable, because no edge leaves node 1, and node 0 has no other outgoing edge. The correct answer is nodes 0 and 1.

#include <algorithm>
#include <iostream>
#include <stack>
#include <utility>
#include <vector>
 
using Graph = std::vector<std::vector<int>>;
 
Graph build(int n, const std::vector<std::pair<int, int>>& edges) {
    Graph g(n);
    for (auto [a, b] : edges) {
        g[a].push_back(b);
        g[b].push_back(a);  // BUG: also adds b -> a
    }
    return g;
}
 
std::vector<int> reachableFrom(const Graph& g, int start) {
    std::vector<bool> seen(g.size(), false);
    std::stack<int> todo;
    todo.push(start);
    seen[start] = true;
    std::vector<int> order;
    while (!todo.empty()) {
        int u = todo.top();
        todo.pop();
        order.push_back(u);
        for (int v : g[u]) {
            if (!seen[v]) {
                seen[v] = true;
                todo.push(v);
            }
        }
    }
    return order;
}
 
void print(const std::vector<int>& xs) {
    for (int x : xs) std::cout << x << ' ';
    std::cout << '\n';
}
 
int main() {
    // Directed edges: 0 -> 1, 2 -> 1, 3 -> 0
    Graph g = build(4, {{0, 1}, {2, 1}, {3, 0}});
    std::cout << "reachable from 0 (sorted): ";
    auto r = reachableFrom(g, 0);
    std::sort(r.begin(), r.end());
    print(r);
    return 0;
}

Run it.

reachable from 0 (sorted): 0 1 2 3 

The program claims that node 2 and node 3 are reachable from node 0. They are not. The bug is in build. Every edge is stored twice, once in each direction. So the edge 2 to 1 also becomes an edge 1 to 2, and the edge 3 to 0 also becomes an edge 0 to 3. The search from 0 then walks 0 to 3, and 1 to 2, and finds nodes that no directed path reaches.

The rule to check is simple. An undirected graph, where a road goes both ways, needs the reverse edge. A directed graph does not. Before you copy a line that adds a reverse edge, ask whether the problem says the edges go both ways.

The fix removes the reverse line. Nothing else changes.

    for (auto [a, b] : edges) {
        g[a].push_back(b);
    }

With the fix, the program prints:

reachable from 0 (sorted): 0 1 

The output is right. Compare the two outputs to see the effect of one line. Keep in mind that the bug did not crash the program or cause an error. It printed a result that looked plausible, and only a check against a small example shows it is wrong. That is why a small hand-built graph is a good test: you know the answer before you run the code.

Lab 4: the call stack runs out

The fourth program is a DFS on a long path. The graph has n nodes in a row: 0 to 1, 1 to 2, and so on up to n - 2 to n - 1. The n value comes from the command line, so you can try different sizes without editing the file.

#include <cstdlib>
#include <iostream>
#include <vector>
 
using Graph = std::vector<std::vector<int>>;
 
void dfs(const Graph& g, int u, std::vector<bool>& seen, int& count) {
    seen[u] = true;
    ++count;
    for (int v : g[u]) {
        if (!seen[v]) dfs(g, v, seen, count);
    }
}
 
int main(int argc, char** argv) {
    int n = std::atoi(argv[1]);
    Graph g(n);
    for (int i = 0; i + 1 < n; ++i) g[i].push_back(i + 1);  // a path 0 -> 1 -> ... -> n-1
    std::vector<bool> seen(n, false);
    int count = 0;
    dfs(g, 0, seen, count);
    std::cout << "n = " << n << ", reachable: " << count << '\n';
    return 0;
}

The code is correct. It has a visited check, so there is no cycle problem. The bug is in how deep the calls go. On a path of n nodes, the first call calls the second, which calls the third, and so on. The deepest call is n levels down before the search turns back. Each level takes some space on the call stack. For a large n, the total space needed is more than the stack can hold.

Run it with a few sizes. Use a time limit on each run, so an unexpected hang is caught.

timeout 10 ./deep_recursion 50000; echo "exit $?"
timeout 10 ./deep_recursion 100000; echo "exit $?"

The results on this machine were:

The crashes have the same exit code, 139, as in Lab 1. The exact size where the crash begins depends on the machine, the compiler and the stack limit. Here, 50,000 levels worked and 100,000 did not. Adding -O2 to the compile command did not change the result for 1,000,000 nodes, which still crashed. With -O2, 100,000 nodes did finish, so the exact limit also depends on the compiler settings.

The fix is to replace the call stack with a stack of your own. An explicit stack is a std::vector<int> that holds the nodes still to visit. The program takes the last node from it, marks it, and pushes its neighbours. The data lives in heap memory (the part of memory a program can request while it runs), which grows as needed, so the depth is limited by the memory on the machine rather than by the fixed size of the call stack.

#include <cstdlib>
#include <iostream>
#include <vector>
 
using Graph = std::vector<std::vector<int>>;
 
int main(int argc, char** argv) {
    int n = std::atoi(argv[1]);
    Graph g(n);
    for (int i = 0; i + 1 < n; ++i) g[i].push_back(i + 1);
    std::vector<bool> seen(n, false);
    std::vector<int> todo{0};  // explicit stack instead of the call stack
    seen[0] = true;
    int count = 0;
    while (!todo.empty()) {
        int u = todo.back();
        todo.pop_back();
        ++count;
        for (int v : g[u]) {
            if (!seen[v]) {
                seen[v] = true;
                todo.push_back(v);
            }
        }
    }
    std::cout << "n = " << n << ", reachable: " << count << '\n';
    return 0;
}

Run it with the million-node path.

timeout 10 ./deep_iterative 1000000; echo "exit $?"

The output is:

n = 1000000, reachable: 1000000
exit 0

The explicit version visits every node and does not crash. The search order is different from the recursive version, but the set of nodes reached is the same, which is what the count checks.

Recursion is still the clearest way to write many graph searches. Use it when you know the depth is small, such as a tree of a few hundred levels, or when the problem is naturally recursive. Switch to an explicit stack when the input can be large, or when you cannot predict its depth.

Common mistakes

The lab bugs are the most common ones, but a few others come up when you run the code yourself.

Forgetting an include

The third program uses std::sort, which is in the <algorithm> header. A first version without that include failed to compile, and the compiler said:

directed_as_undirected.cpp: In function ‘int main()’:
directed_as_undirected.cpp:47:10: error: ‘sort’ is not a member of ‘std’; did you mean ‘qsort’?
   47 |     std::sort(r.begin(), r.end());
      |          ^~~~
      |          qsort

The message names the missing piece and suggests a similar name. The fix is to add #include <algorithm> at the top of the file. Read the first line of a compiler error first. It names the function and the file, so you know where to look.

Reading an exit code as a result

A program that crashes can still print lines before it dies, and a program that finished can still print a wrong answer. The exit code only says whether the program ended normally. Read the printed output as well as the code. When the exit code is 139, look for a recursion that does not stop or a call stack that is too deep.

Testing on a graph that is too large

A large random graph hides the bug, because a wrong answer looks like any other answer. The bugs in this lab were found with graphs of three or four nodes, where the correct answer can be worked out by hand. Start with a small graph, check the answer on paper, and only then test a large one.

Using a visited check in the wrong place

The visited mark must go on when the node is first found, not when the search finishes with it. In Lab 2 the mark goes on when the node is pushed. If the mark were set only when the node is popped, the same node could be pushed many times before the first pop reaches it.

Practice

Exercise 1

Run the fixed Lab 1 program on the graph {{1}, {2}, {}}, starting from node 0. What does it print?

Show the answer

It prints reachable: 3. The path 0, 1, 2 has no cycle, so the program visits each node once. Node 2 has no outgoing edges, so the search stops there.

Exercise 2

The program in Lab 3 stores each edge in both directions. Is that correct for a graph of roads where traffic goes both ways? Explain your answer.

Show the answer

Yes. When the roads allow traffic both ways, an edge from a to b is also an edge from b to a, so the reverse line is needed. The bug only appears when the edges are one-way.

Exercise 3

In the Lab 2 output, node 0 appears three times in the first eight lines. Explain why it appears again after it was visited the first time.

Show the answer

Node 1 has an edge back to node 0, and node 2 also has an edge back to node 0. Without a visited check, each visit to 1 or 2 pushes node 0 into the queue again. The visits to 0 push 1 and 2 again, so the pattern repeats.

Exercise 4

Give two ways to fix a recursive DFS that crashes on a deep path. Which one is more reliable, and why?

Show the answer

One way is to rewrite the search with an explicit stack in a std::vector, as the Lab 4 fix does. The other is to make the program use a larger call stack, for example with a system setting. The explicit stack is more reliable, because its size is limited by the memory on the machine rather than by a fixed stack limit that a different machine may set lower.

Exercise 5

A graph has 200,000 nodes in a single path. You want to count the reachable nodes with a DFS. Would you use the recursive version or the explicit stack version, and why?

Show the answer

Use the explicit stack version. The path is 200,000 levels deep, which is above the 100,000 that crashed in the Lab 4 test on this machine. The explicit version uses memory on the heap, so it does not depend on the call stack limit.

Summary

• A DFS or BFS needs a visited check, or a cycle makes the search go around forever, or the queue grows without limit.
• Mark a node as visited when it is first reached, so it is never added a second time.
• Store only the edges the problem gives. Add a reverse edge only for undirected graphs.
• A segmentation fault with exit code 139 in a recursive search usually means the call stack ran out, because the recursion is too deep.
• Replace deep recursion with an explicit stack in a std::vector when the input can be large.
• Test a new graph search on a graph of three or four nodes first, where the correct answer is known.