Residual Graph Synthesizer & Back-Edge Generator
Constructs directed flow networks with forward capacities c(u, v) and initializes bidirectional residual edges with reverse capacity c_f(v, u) = f(u, v).
Computer Science / Network Flow & Max-Cut
FREE TO EXPLORELABORATORY 14 · COMPUTER SCIENCE
Empirical Analysis of Network Flow Algorithms: Ford-Fulkerson Method, Edmonds-Karp Shortest Augmenting Paths, Dinic's Blocking Flows, Residual Graphs, and the Max-Flow Min-Cut Duality Theorem
To investigate the mathematical foundations and computational mechanics of network flow optimization, compare the Ford-Fulkerson method against Edmonds-Karp and Dinic algorithms, analyze residual network back-edges and flow conservation, prove the Max-Flow Min-Cut theorem via residual reachability, and empirically verify the linear residual inspection scaling law T(|V|) = k_flow · |V| + T_0 = 10.0000 · |V| + 0.0000 inspections across network scales |V| ∈ [50, 1000] vertices with candidate capacity edges |E| = 3|V|. Explore interactive search algorithms, compare operation counts and analyse complexity scaling.
COMPUTE · BENCHMARK · ANALYSE
Your virtual algorithm laboratory.
RESIDUAL GRAPH AUGMENTING INSPECTIONS T(|V|)—
EXECUTION STATUS
Ready to execute vertex count benchmark.
Adjust vertex count n, then execute benchmark.
Operation counts are generated deterministically by the exact algorithmic execution model. Modern hardware benchmarks additionally reflect cache line prefetching and branch misprediction penalties.
Algorithmic assumptions and limits
The simulated execution environment models idealized network flow graphs where residual edge inspections execute with deterministic cost of 1 operation (T(|V|) = 10|V|). In physical microprocessors, execution latency is modulated by CPU L1/L2 data cache hit ratios during adjacency list traversals, branch predictor mispredictions during capacity feasibility checks (`if (c_f > 0)`), queue memory allocation stalls during BFS expansions, and memory bus contention during backward edge pointer updates. In the Edmonds-Karp Maximum Flow benchmark on a directed network G = (V, E) with edge density |E| = 3|V| and balanced source-to-sink layer topology, the algorithm discovers shortest augmenting paths via Breadth-First Search in the residual network G_f. Each BFS traversal systematically inspects all reachable vertices and incident residual edges (|V| + |E| = 4|V| operations). On a standard benchmark network requiring exactly 2.5 effective augmenting path passes per layer across source-sink capacity saturation, total residual edge inspections scale deterministically as T(|V|) = 2.5 · (4|V|) = 10.0000 · |V| inspections with exact theoretical intercept T_0 = 0.0000 inspections. Ordinary least-squares regression across all benchmark trials yields an ideal coefficient of determination R² = 1.000000 with zero residual variance.
Computational tools & environment.
Edmonds-Karp BFS Shortest-Augmenting-Path Engine
Executes breadth-first search on residual graphs to locate augmenting paths with minimum edge count in O(|E|) time per iteration.
Dinic Level Graph & Blocking Flow Unit
Decomposes residual networks into layered BFS DAGs and routes multiple blocking flows via depth-first search in O(|V|² |E|) time.
Push-Relabel (Preflow-Push) Height-Discharge Processor
Simulates Goldberg-Tarjan preflow reservoirs, active vertex discharge queues, and height relabeling operations in O(|V|³) time.
Max-Flow Min-Cut Duality & S-T Bottleneck Analyzer
Computes source-reachable cut set S via residual BFS from s and verifies capacity equality c(S, T) = |f*|.
Network Topology Generator & Integer Capacity Synthesizer
Configures planar grid networks, bipartite matching matrices, and pathological anti-parallel capacity networks with bounds c(e) in [1, 100].
FOLLOW THE METHOD
A reason behind every step.
To investigate the mathematical foundations and computational mechanics of network flow optimization, compare the Ford-Fulkerson method against Edmonds-Karp and Dinic algorithms, analyze residual network back-edges and flow conservation, prove the Max-Flow Min-Cut theorem via residual reachability, and empirically verify the linear residual inspection scaling law T(|V|) = k_flow · |V| + T_0 = 10.0000 · |V| + 0.0000 inspections across network scales |V| ∈ [50, 1000] vertices with candidate capacity edges |E| = 3|V|. Suggested independent settings: 50, 100, 200, 300, 500, 750, 1000 vertices.
01
Initialize Flow Network Topology & Zero-Flow State
Configure directed network G = (V, E) with |V| vertices, source s, sink t, and integer edge capacities c(u, v). Verify that all edge flows are initialized to f(u, v) = 0.
02
Construct Residual Network & Back-Edges
Instantiate the residual graph G_f, setting forward residual capacity c_f(u, v) = c(u, v) - f(u, v) and backward residual capacity c_f(v, u) = f(u, v).
03
Select Flow Network Scale |V|
Adjust the independent variable control slider to configure the network vertex count |V| between 50 and 1,000 vertices across the designated benchmark sample points.
04
Execute Edmonds-Karp BFS Augmentation Rounds
Trigger the flow solver. Perform BFS from source s to locate the shortest augmenting path P in G_f. Compute bottleneck capacity Δ = min_{(u,v) in P} c_f(u,v) and augment flow along P, logging edge inspections.
05
Evaluate Maximum Flow & Min-Cut Boundary
Continue augmenting until no path exists from s to t in G_f. Traverse reachable vertices from s to identify minimum cut (S, T) and verify that total max flow |f*| = c(S, T).
06
Perform Linear Regression & Complexity Verification
Record total residual inspections across all seven benchmark trials. Regress T(|V|) against vertex count |V| to compute slope k_flow, intercept T_0, and coefficient of determination R².
YOUR NOTEBOOK · 0 OBSERVATIONS
Turn measurements into asymptotic insight.
Points are your recorded benchmark observations. The regression line validates Network Flow & Max-Cut complexity scaling.
LINEAR ASYMPTOTIC FIT · y = mx + b
T(|V|) = k_flow · |V| + T_0 = 10.0000 · |V| + 0.0000 inspections
| # | Flow network vertex count |V| (|E| = 3|V| capacity edges) (vertices) | Residual graph augmenting inspections T(|V|) (inspections) | Network vertex count |V| (vertices) | Residual augmenting inspections T(|V|) = 10·|V| (inspections) | Remove |
|---|
No readings yet. Execute a vertex count benchmark and record it.
Calculate it yourself.
CHECK YOUR UNDERSTANDING