12.24 Testing Flow Code

Flow implementations are compact, but bugs are easy to hide.

algorithmsgraphsnetwork-flow

12.24 Testing Flow Code

Problem

Flow implementations are compact, but bugs are easy to hide.

A wrong residual update may still return a plausible value on small examples. A missing reverse edge may pass tests where no rerouting is needed. A sign error in lower-bound circulation may work on balanced toy inputs and fail on real cases.

Flow code needs tests that check both the final answer and the internal invariants.

Solution

Test flow code at three levels:

  1. Unit tests for graph construction and residual updates.
  2. Known-answer tests for standard networks.
  3. Property tests that verify invariants and compare against slower reference implementations.

Do not test only the maximum-flow value. Also test conservation, capacity bounds, residual consistency, cut certificates, and solution recovery.

Test the Edge Pair

Most implementations store every edge with a reverse edge.

A logical edge:

u -> v
capacity = c

creates:

forward edge: u -> v, capacity c
reverse edge: v -> u, capacity 0

The two edges must point to each other by reverse index.

Test this directly.

Expected properties:

graph[u][i].to = v
graph[v][rev].to = u
graph[v][rev].rev = i

If this structure is wrong, every algorithm built on it is suspect.

Test a Single Push

Start with one edge:

s -> t capacity 10

Push:

4

Expected residual capacities:

Edge Residual
s -> t 6
t -> s 4

This is the smallest useful residual-graph test.

It catches one-sided updates, incorrect reverse indices, and subtraction errors.

Known-Answer Max-Flow Tests

Use small graphs whose answers are obvious.

Single Edge

s -> t capacity 7

Expected max flow:

7

Two Parallel Paths

s -> a -> t
s -> b -> t

Capacities:

Edge Capacity
s -> a 3
a -> t 3
s -> b 5
b -> t 5

Expected max flow:

8

Bottleneck

s -> a -> b -> t

Capacities:

Edge Capacity
s -> a 10
a -> b 2
b -> t 10

Expected max flow:

2

Test Rerouting

A good test must require reverse edges.

Network:

Edge Capacity
s -> a 1
s -> b 1
a -> b 1
a -> t 1
b -> t 1

If DFS first chooses:

s -> a -> b -> t

it must later reroute through a reverse edge to reach total flow 2.

Expected max flow:

2

An implementation without reverse edges may return 1.

Test the Min-Cut Certificate

After computing max flow:

  1. Run BFS or DFS in the residual graph from s.
  2. Let reachable vertices be A.
  3. Compute cut capacity using original edges from A to B.
  4. Assert:
maxFlow == cutCapacity

This test is extremely valuable.

It verifies not only the answer, but also the residual graph and cut extraction logic.

Capacity Invariants

After the algorithm finishes, reconstruct flow for every original edge.

For each edge:

0 ≤ flow ≤ capacity

Assert this for all original edges.

Do not apply it to artificial reverse edges.

If your implementation stores only residual capacity, recover flow as:

flow = originalCapacity - residualForwardCapacity

Conservation Invariants

For every vertex except source and sink:

incoming flow = outgoing flow

Compute this from original edges.

Assert exact equality for integer flows.

For floating-point flows, use a tolerance.

This catches many bugs that a correct final flow value may not expose.

Residual Invariants

For every original edge:

forward residual = capacity - flow
reverse residual = flow

Assert both.

This is especially useful after every augmentation in debug builds.

If the algorithm fails later, these assertions locate the first broken step.

Integrality Tests

For integer capacities, max-flow algorithms using integral augmentations should produce integral flows.

For matching and disjoint-path reductions, assert that each relevant edge flow is either:

0

or:

1

This catches accidental fractional logic or floating-point misuse.

Matching Tests

For bipartite matching:

  1. Compute matching.
  2. Assert no left vertex appears more than once.
  3. Assert no right vertex appears more than once.
  4. Assert every matched edge exists in the original graph.

For small graphs, compare against brute force.

Example brute-force size for small n:

n ≤ 8

is often enough for randomized testing.

Lower-Bound Tests

For lower-bounded flow, test both directions:

  1. If the solver says feasible, reconstruct original flows.
  2. Assert every edge satisfies:
lower ≤ flow ≤ capacity
  1. Assert vertex conservation or required balances.
  2. Assert every edge from the super source is saturated.

Also test impossible cases.

Example:

Edge Lower Capacity
a -> b 5 3

This must be rejected immediately because:

lower > capacity

Min-Cost Flow Tests

For min-cost flow, verify:

  • flow amount
  • total cost
  • capacity constraints
  • conservation
  • residual reverse costs

Small instances should be checked by brute force.

For assignment with n ≤ 8, compare against all permutations.

For each residual edge pair, assert:

reverse.cost = -forward.cost

For potentials-based implementations, assert reduced costs are nonnegative where required.

Randomized Testing

Generate small random graphs.

For each graph:

  1. Run your fast algorithm.
  2. Run a slow reference implementation.
  3. Compare results.

Good reference choices:

Problem Reference
Max flow Edmonds-Karp
Bipartite matching brute force or simple augmenting paths
Assignment brute-force permutations
Min cut enumerate cuts for small V
Lower bounds brute-force small integer flows

Enumerating all cuts is simple for small graphs.

For V ≤ 16, enumerate subsets containing s and not containing t, compute cut capacity, and compare to max flow.

Fuzzing Edge Cases

Include random cases with:

  • zero capacities
  • disconnected graphs
  • parallel edges
  • self loops
  • source with no outgoing edges
  • sink with no incoming edges
  • very large capacities
  • many equal capacities
  • long chains
  • dense graphs
  • multiple minimum cuts

Parallel edges are especially important because many implementations accidentally merge them or mishandle reverse indices.

Test Graph Transformations

When using reductions, test the transformation separately.

For vertex capacities:

  • confirm every original vertex has v_in -> v_out
  • confirm incoming edges go to v_in
  • confirm outgoing edges leave from v_out

For project selection:

  • confirm positive values create source edges
  • confirm negative values create sink edges
  • confirm dependencies point from dependent project to required project

For scheduling:

  • confirm no edge exists for unavailable assignments
  • confirm demand edges have correct capacities
  • confirm recovered assignments match edges with positive flow

Regression Tests

Every discovered bug should become a test case.

Store:

  • graph input
  • expected flow or matching
  • expected cut if useful
  • short note explaining the bug

Flow bugs often reappear during optimization. Regression tests prevent a faster implementation from becoming a less correct implementation.

Debug Output

For difficult failures, print:

edge list
residual capacities
flow values
reachable set from source
cut edges
active vertices
height labels

depending on the algorithm.

For push-relabel, also print:

excess[v]
height[v]

For Dinic, print:

level[v]
current edge pointer

This makes state-machine bugs easier to isolate.

Common Mistakes

Testing Only the Answer

A wrong implementation may return the right value on easy cases. Always test invariants.

Skipping Reverse-Edge Cases

Include tests that require canceling previous flow.

Using Only Connected Graphs

Disconnected graphs expose reachability and termination bugs.

Ignoring Parallel Edges

Parallel edges are legal in many flow models and should be supported unless explicitly forbidden.

Not Testing Reductions

A correct max-flow solver can still produce wrong answers if the graph construction is wrong.

Discussion

Testing flow code is less about large test cases and more about adversarial small cases. You want graphs that force the algorithm to use every mechanism: reverse edges, bottlenecks, cuts, lower bounds, node splitting, and cost reweighting.

The strongest simple test is the min-cut certificate. If the computed flow equals the capacity of a cut recovered from the final residual graph, you have a compact correctness witness for that instance.

Takeaway

Reliable flow code requires invariant testing, known-answer examples, randomized comparison against slower solvers, and regression tests for every bug found.

For max flow, always verify the final min-cut certificate. For reductions, test the constructed graph and the recovered solution. This combination catches most implementation errors before they reach production or contest submissions.