9.24 Testing Graph Code

You need confidence that a graph algorithm handles real inputs, edge cases, and malformed assumptions correctly.

algorithmsgraphsgraph-theory

9.24 Testing Graph Code

Problem

You need confidence that a graph algorithm handles real inputs, edge cases, and malformed assumptions correctly.

Graph code is easy to get almost right. A DFS may work on connected graphs but fail on disconnected ones. A cycle detector may work for directed graphs but be wrong for undirected graphs. A shortest-path implementation may pass small examples but fail when vertices are isolated, labels are missing, or edge weights are negative.

You need a testing strategy that checks both algorithmic correctness and graph-model correctness.

Solution

Test graph code at three levels:

  1. Representation tests
  2. Algorithm tests
  3. Property tests

Representation tests verify that the graph is built correctly.

Algorithm tests verify known examples.

Property tests verify invariants that must always hold.

Good graph testing begins before the algorithm runs.

Discussion

Most graph bugs come from one of four sources:

Bug Type Example
Representation error Missing sink or isolated vertex
Direction error Treating directed edges as undirected
Traversal error Forgetting visited state
Assumption error Using BFS on weighted edges

A good test suite should expose all four categories.

Do not test only the happy path. Graphs have many boundary cases, and algorithms often depend on subtle structure.

Test the Builder First

Suppose input arrives as edge pairs.

edges = [
    ("A", "B"),
    ("B", "C"),
]

For a directed graph, the expected adjacency list is:

{
    "A": ["B"],
    "B": ["C"],
    "C": [],
}

A builder test:

def test_directed_builder():
    graph = build_directed_graph([
        ("A", "B"),
        ("B", "C"),
    ])

    assert graph == {
        "A": ["B"],
        "B": ["C"],
        "C": [],
    }

The important part is the empty list for C.

If sink vertices are lost, later algorithms may fail or silently produce incomplete results.

Test Undirected Symmetry

For undirected graphs, every edge must appear in both directions.

def assert_undirected(graph):
    for vertex, neighbors in graph.items():
        for neighbor in neighbors:
            assert vertex in graph[neighbor]

Example test:

def test_undirected_builder():
    graph = build_undirected_graph([
        ("A", "B"),
        ("A", "C"),
    ])

    assert_undirected(graph)

This catches a common mistake:

graph[u].append(v)

without:

graph[v].append(u)

Test Isolated Vertices

An isolated vertex has no edges but still belongs to the graph.

def test_isolated_vertex_preserved():
    vertices = ["A", "B", "C"]
    edges = [("A", "B")]

    graph = build_graph(vertices, edges)

    assert "C" in graph
    assert graph["C"] == []

This matters for:

  • Component counting
  • Connectivity testing
  • Topological sorting
  • Graph coloring
  • Euler checks

Omitting isolated vertices changes the problem.

Test Empty Graphs

Many algorithms should define behavior on empty graphs.

Examples:

assert connected_components({}) == []
assert is_connected({}) is True
assert topological_sort({}) == []

An empty graph is usually considered connected by convention only in some contexts, so document your choice.

The important point is consistency.

Test Single-Vertex Graphs

Single-vertex graphs expose off-by-one assumptions.

graph = {
    "A": []
}

Useful checks:

assert connected_components(graph) == [["A"]]
assert has_cycle_directed(graph) is False
assert topological_sort(graph) == ["A"]

For Euler paths, a graph with one vertex and no edges often has a trivial Euler traversal.

Make the convention explicit.

Test Disconnected Graphs

Algorithms that launch from a single starting vertex often miss disconnected regions.

Example:

graph = {
    "A": ["B"],
    "B": ["A"],
    "C": ["D"],
    "D": ["C"],
}

Connected components should return two components.

components = connected_components(graph)

assert normalize_components(components) == [
    ["A", "B"],
    ["C", "D"],
]

A helper makes comparison stable:

def normalize_components(components):
    return sorted(
        sorted(component)
        for component in components
    )

Without normalization, tests may fail because traversal order differs.

Test Traversal Without Assuming Order

DFS and BFS output order depends on adjacency-list order.

Avoid brittle tests unless order is part of the contract.

Instead of:

assert dfs_order(graph, "A") == [
    "A",
    "B",
    "C",
]

prefer:

assert set(dfs_order(graph, "A")) == {
    "A",
    "B",
    "C",
}

For BFS distance, the distance map is a better assertion than visit order.

assert bfs_distance(graph, "A") == {
    "A": 0,
    "B": 1,
    "C": 1,
    "D": 2,
}

Distances are stable even when same-level ordering changes.

Test Directed Cycle Detection

Use both cyclic and acyclic examples.

def test_directed_cycle():
    graph = {
        "A": ["B"],
        "B": ["C"],
        "C": ["A"],
    }

    assert has_cycle_directed(graph) is True

Acyclic:

def test_directed_acyclic():
    graph = {
        "A": ["B"],
        "B": ["C"],
        "C": [],
    }

    assert has_cycle_directed(graph) is False

Also test self-loops:

def test_directed_self_loop():
    graph = {
        "A": ["A"],
    }

    assert has_cycle_directed(graph) is True

Self-loops are cycles.

Test Undirected Cycle Detection

Undirected graphs require parent tracking.

def test_undirected_no_cycle():
    graph = {
        "A": ["B"],
        "B": ["A", "C"],
        "C": ["B"],
    }

    assert has_cycle_undirected(graph) is False

Cycle:

def test_undirected_cycle():
    graph = {
        "A": ["B", "C"],
        "B": ["A", "C"],
        "C": ["A", "B"],
    }

    assert has_cycle_undirected(graph) is True

This pair catches implementations that mistake the parent edge for a cycle.

Test Topological Sort by Verifying Edges

Do not require one exact topological ordering unless the graph has only one valid order.

Given:

graph = {
    "A": ["C"],
    "B": ["C"],
    "C": [],
}

Both are valid:

["A", "B", "C"]
["B", "A", "C"]

Test the property instead:

def assert_topological_order(graph, order):
    position = {
        vertex: i
        for i, vertex in enumerate(order)
    }

    assert len(order) == len(graph)

    for source, neighbors in graph.items():
        for target in neighbors:
            assert position[source] < position[target]

Then:

order = topological_sort(graph)
assert_topological_order(graph, order)

This test matches the algorithmic contract.

Test Shortest Paths with Known Distances

For shortest paths, assert distances and reconstructed paths.

graph = {
    "A": [("B", 5), ("C", 2)],
    "B": [("D", 3)],
    "C": [("D", 1)],
    "D": [],
}

Expected distances from A:

{
    "A": 0,
    "B": 5,
    "C": 2,
    "D": 3,
}

Test:

distance, parent = dijkstra(graph, "A")

assert distance["D"] == 3
assert reconstruct(parent, "D") == ["A", "C", "D"]

If multiple shortest paths exist, check cost rather than exact path.

Test MSTs by Cost and Size

MST algorithms may produce different valid trees when equal weights exist.

Do not require an exact edge set unless the MST is unique.

Instead check:

mst = kruskal(vertices, edges)

assert len(mst) == len(vertices) - 1
assert total_weight(mst) == expected_cost
assert is_tree(vertices, mst)

Helper:

def total_weight(edges):
    return sum(weight for _, _, weight in edges)

For unique examples, exact edge tests are fine.

For non-unique examples, property checks are better.

Property-Based Testing Ideas

For random small graphs, compare optimized algorithms against slower simple versions.

Examples:

Optimized Algorithm Slow Checker
Articulation points Remove each vertex and count components
Bridges Remove each edge and count components
MST Enumerate small spanning trees
Shortest paths Floyd-Warshall on tiny graphs
Bipartite test Try both-color assignments for tiny graphs

This approach is powerful because optimized graph algorithms often have subtle invariants.

A slow checker gives a reliable reference.

Example: Testing Bridges Against a Slow Checker

def test_bridges_random_small(graph):
    fast = {
        tuple(sorted(edge))
        for edge in bridges(graph)
    }

    slow = {
        tuple(sorted(edge))
        for edge in bridges_slow(graph)
    }

    assert fast == slow

Run this on many small random graphs.

The slow version may be too expensive for production, but it is excellent for tests.

Test Invalid Inputs

Graph code should either handle invalid inputs or reject them clearly.

Examples:

  • Edge points to missing vertex
  • Negative weight given to Dijkstra
  • Duplicate edge when unsupported
  • Self-loop when unsupported
  • Non-numeric weight
  • Directed graph passed to undirected-only algorithm

Example validation:

def validate_nonnegative_weights(graph):
    for source, edges in graph.items():
        for target, weight in edges:
            if weight < 0:
                raise ValueError(
                    "negative edge weight"
                )

Test:

def test_dijkstra_rejects_negative_weight():
    graph = {
        "A": [("B", -1)],
        "B": [],
    }

    try:
        dijkstra(graph, "A")
        assert False
    except ValueError:
        assert True

Test Large but Simple Graphs

Performance bugs often appear on simple large structures.

Use:

Long chain

0 -- 1 -- 2 -- 3 -- ... -- n

Tests recursion depth and linear behavior.

Star graph

      1
      |
2 --  0 -- 3
      |
      4

Tests high-degree vertices.

Complete graph

Every vertex connects to every other vertex.

Tests dense behavior.

Empty-neighbor graph

Many isolated vertices.

Tests component logic.

These structures are easy to generate and expose many defects.

Common Pitfalls

Do not test traversal order unless order is the contract.

Do not ignore disconnected graphs.

Do not forget self-loops and isolated vertices.

Do not test only one graph shape.

Do not compare MST edge sets when multiple MSTs are valid.

Do not use weighted tests for unweighted assumptions without being explicit.

Do not let invalid inputs fail silently.

Takeaway

Testing graph code requires more than checking one example. Start by testing graph construction, especially directionality, isolated vertices, and sink vertices. Then test algorithms using known examples and property-based assertions. When outputs are not unique, validate the contract rather than an arbitrary order. For subtle algorithms, compare optimized implementations against slow reference checkers on small random graphs. This approach catches the representation, traversal, and assumption errors that cause most graph bugs.