{{ summaryTitle }}
{{ summaryValue }}

{{ summaryLine }}

Algorithm: {{ algorithmLabel }} Augmentations: {{ resultsReady ? computation.values.augmentation_count : '—' }} Cut capacity: {{ resultsReady ? computation.values.cut_capacity : '—' }}

Topology preview unavailable.

Network preset:
The residual search begins here.
Choose a terminal distinct from the source.
Vertices:
2–8 unique labels
IDLabelRemove
{{ vertex.id }}
Directed capacity edges:
1–16 unique pairs
IDFromToCapacityRemove
{{ edge.id }}
Self-loops and duplicate directed pairs are rejected. Opposite directions remain independent edges.
Trace player:

{{ currentTraceMessage }}

Step {{ traceStepDisplay }}
The neutral default is off.
{{ showResidual ? 'Enabled' : 'Disabled' }}
StepPhaseResidual pathBottleneckTotal flowDecisionCopy
{{ row.step }}{{ row.phase }}{{ row.path || '—' }}{{ row.bottleneck || '—' }}{{ row.total_flow }}{{ row.message }}

The chart renderer is unavailable. Exact values remain in the flow certificate.

EdgeFlow / capacityForward residualReverse residualUtilizationCertificate stateCopy
{{ row.label }}{{ row.flow }} / {{ row.capacity }}{{ row.forward_residual }}{{ row.reverse_residual }}{{ row.utilization_percent }}%{{ row.state }}
Directed Graph Algorithms Simulator Trace topological ordering and cycle evidence or find strongly connected components with four classic directed-graph algorithms step by step.
Minimum Spanning Tree Algorithm Simulator Compare Kruskal and Prim on weighted graphs with deterministic edge decisions, cycle rejections, and minimum spanning forest results.
Pathfinding Algorithm Simulator Compare four pathfinding algorithms on an editable weighted grid and inspect route cost, exploration order, diagonal rules and no-path outcomes.
Network Diagram Designer Build a logical or physical network diagram from device and link records, flag missing or isolated endpoints, and prepare a reviewed handoff.

A delivery route can look open while one narrow connection limits everything that can pass through it. Network flow models that situation as a directed graph: vertices are junctions, edges are one-way routes, and each edge has a capacity that flow may not exceed. The central question is how much can travel from one source to one sink at the same time.

Flow is conserved at every intermediate vertex. Apart from the source and sink, whatever enters a vertex must leave it. This makes maximum flow useful for teaching bandwidth allocation, transport capacity, matching, and other allocation problems where a shared route can become a bottleneck.

Residual capacity
How much more flow an edge can carry, together with reverse capacity that can cancel an earlier choice.
Augmenting path
A source-to-sink route in the residual network along which the current flow can increase.
Bottleneck
The smallest residual capacity on an augmenting path, which limits that path's next increase.
Minimum cut
A partition that separates source from sink with the smallest total capacity crossing from the source side.

Edmonds-Karp and Dinic reach the same maximum-flow value but organize the search differently. Edmonds-Karp repeatedly chooses a shortest residual path by edge count. Dinic builds a level graph and sends a blocking flow before rebuilding the levels. Comparing their traces is about search structure and augmentation choices, not about expecting different optimum values.

Capacity is an abstract limit, not automatically time, distance, cost, or physical throughput. A valid maximum-flow result answers the model that was entered. It does not account for lower bounds, costs, shared undirected capacity, time-varying demand, or several commodities competing for the same edges.

How to Use This Tool:

Set up the directed capacity network first, then choose the source, sink, and algorithm you want to trace.

  1. Load Classic capacity network for a general example or Reverse-residual matching to study a trace that may need to cancel earlier flow.
  2. Choose distinct Source and Sink vertices. The source supplies flow and the sink receives it.
  3. Edit edge capacities or add vertices and directed edges. Capacities must be whole numbers from 0 through 999,999; self-loops and duplicate edges in the same direction are rejected.
  4. Select Edmonds-Karp or Dinic, then use Step or Play to follow residual paths, bottlenecks, reverse updates, and the running total.
  5. Read the final maximum flow, then check Flow certificate. The minimum-cut capacity should equal the maximum-flow value, while Edge utilization identifies saturated and cut edges.

Interpreting Results:

The strongest optimality check is the equality between Maximum flow and Cut capacity. The certificate also lists which vertices remain reachable from the source in the final residual network and which original edges cross to the sink side.

  • A saturated edge has no forward residual capacity, but saturation alone does not prove that the edge belongs to every minimum cut.
  • A reverse residual step is not negative physical flow. It cancels part of an earlier assignment so another route can use the capacity better.
  • Different augmenting traces can still be equally correct when they finish with the same maximum-flow value and a matching cut certificate.

If the two algorithms appear to disagree, first keep the exact same source, sink, vertices, edge directions, and capacities. Then compare the final certificate rather than one intermediate path.

Technical Details:

A feasible flow assigns a value to every directed edge while respecting capacity and conservation. The residual network records both unused forward capacity and the amount of existing flow that can be reversed. An augmentation adds the path bottleneck on forward arcs and subtracts it on reverse arcs.

Rule Core:

For an edge from u to v, flow f stays between zero and capacity c. At every vertex other than source s and sink t, total incoming flow equals total outgoing flow.

0≤f(u,v)≤c(u,v)
∑u:(u,v)f(u,v) = ∑w:(v,w)f(v,w) v≠s,t
Rule Exact behavior Why it matters
Forward residual Capacity minus current flow Limits how much more can move in the original direction.
Reverse residual Current flow Allows an earlier assignment to be reduced.
Path bottleneck Minimum residual capacity among all arcs on the path Sets the exact augmentation amount.
Termination No source-to-sink path remains in the residual network Provides the condition used to construct a minimum cut.

Algorithm Mechanism:

Algorithm Search rule Trace structure
Edmonds-Karp Breadth-first search selects one shortest residual path. Search, augment by the bottleneck, then search again.
Dinic Breadth-first search assigns levels; paths advance one level at a time. Send a blocking flow through the level graph, then build the next phase.

The final cut uses all vertices still reachable from the source through positive residual capacity. Original edges that leave this reachable set form the reported cut. Their capacities are added, and the result must equal the net flow leaving the source.

The teaching model accepts 2 to 8 vertices and 1 to 16 directed edges. Capacities are non-negative whole numbers. Opposite directions may coexist as independent edges, but parallel duplicates in the same direction and self-loops are outside the model.

References: