DSA DSA In Depth
0%
From-Scratch Build

Dinic Blocking-Flow Max-Flow, Min-Cut & Bipartite Matching Engine

Dinic blocking-flow maximum flow engine with BFS level graphs, Shimon Even current-arc pointer pruning, s-t minimum cut extraction, and bipartite maximum cardinality matching.

~50 min Advanced Lessons: Build Lab: Dinic's Maximum Flow, Min-Cut Partitioning & Bipartite Matching Engine, Dinic's Algorithm: BFS Level Graphs, DFS Blocking Flows with Current-Arc Pointer & O(E√V) Unit Networks, Maximum Bipartite Matching: König's Theorem, Hall's Marriage Theorem & Hopcroft-Karp O(E√V), Minimum-Cost Maximum Flow (MCMF): Successive Shortest Paths with Johnson Potentials, Depth-First Search: Parenthesis Theorem, White-Path Theorem & Tree/Back/Forward/Cross Edges, Matroid Theory: Graphic & Linear Matroids and When the Greedy Algorithm Is Guaranteed Optimal
Interactive Build Lab 0/4 Steps Completed

Code & Verify in the Browser Workbench

Complete 4 progressive engineering steps in JavaScript or TypeScript against an in-browser Node.js v22 runtime (virtual filesystem, loopback TCP/HTTP, and automated unit tests) — zero local setup required.

Why Edmonds-Karp Is $O(V E^2)$ and Dinic Is $O(V^2 E)$

Edmonds-Karp runs a full $O(E)$ BFS for every single augmenting path. Yefim Dinitz (1970) observed that a single BFS from $s$ defines a Level Graph ($L[v] = L[u] + 1$), and we can saturate all shortest augmenting paths of length $L[t]$ in a single phase by finding a blocking flow.

With Shimon Even's current-arc pointer (this.ptr[u]) optimization:

  • Whenever _dfs fails to push flow along an arc $(u, v)$ or saturates it, this.ptr[u] increments so that $(u, v)$ is never examined again in the current phase.
  • Each blocking-flow phase runs in $O(VE)$ time, and since $L[t]$ strictly increases after every phase, there are at most $V - 1$ phases ($O(V^2 E)$ total, or $O(E \sqrt{V})$ on unit-capacity bipartite networks—matching Hopcroft-Karp!).

Curriculum Connections

Guided Implementation Walkthrough (4 Progressive Steps)

Step 1: Residual Graph XOR Edge Pairing

  • Core Mechanical Concept: Residual Graph XOR Edge Pairing
  • Target Module: index.js (Step1)
  • Engineering Specification: Store forward edge at even index 2k and backward residual edge at odd index 2k + 1 in this.edges, so id ^ 1 toggles between an edge and its residual counterpart in $O(1)$.
  • Verification Invariant: verifies Step 1: Residual Graph XOR Edge Pairing

Step 2: Level Graph Construction via BFS

  • Core Mechanical Concept: Level Graph Construction via BFS
  • Target Module: index.js (Step2)
  • Engineering Specification: Implement _bfs(s, t) over edges with positive residual capacity cap - flow > 0 to assign shortest-path hop distances this.level[v].
  • Verification Invariant: verifies Step 2: Level Graph Construction via BFS

Step 3: Blocking Flow DFS with Current-Arc Pointers

  • Core Mechanical Concept: Blocking Flow DFS with Current-Arc Pointers
  • Target Module: index.js (Step3)
  • Engineering Specification: Implement _dfs(u, t, pushed) advancing this.ptr[u] so saturated or dead-end arcs are never re-inspected within the same BFS phase, achieving $O(V^2 E)$ general and $O(E \sqrt{V})$ unit-network time.
  • Verification Invariant: verifies Step 3: Blocking Flow DFS with Current-Arc Pointers

Step 4: Min-Cut Extraction & Unit Bipartite Matching

  • Core Mechanical Concept: Min-Cut Extraction & Unit Bipartite Matching
  • Target Module: index.js (Step4)
  • Engineering Specification: Extract the minimum $s$-$t$ cut from the final residual reachability set and verify the Ford-Fulkerson Max-Flow Min-Cut equality.
  • Verification Invariant: verifies Step 4: Min-Cut Extraction & Unit Bipartite Matching

Asymptotic & Memory Layout Guarantees

  • Category: Network Flow & Matching
  • Difficulty: Advanced (~50 minutes)
  • Key Architectural Highlights:
    • Residual edge pairing via XOR index (edgeIdx ^ 1) in a flat edge pool
    • BFS level-graph construction paired with current-arc pointer DFS blocking flows
    • Max-Flow Min-Cut partition extraction and O(E sqrt(V)) unit-network bipartite matching
  • Tags & Primitives: Dinic Algorithm, Level Graph, Current-Arc Optimization, Max-Flow Min-Cut, Bipartite Matching

Production Systems Context & Verification

This from-scratch implementation is engineered with zero external dependencies and deterministic verification harnesses. Every internal invariant—from pointer restoration and bitmask addressing to amortized potential bounds and tree height balance—is asserted directly in test.js. Use the interactive browser workbench above to complete the guided steps in Guided Lab mode or inspect and benchmark the complete reference architecture in Full Solution mode.