6c:T4a3,def build_residual_graph(graph, flow): """ Build residual graph from original graph and current flow. Args: graph: Dict[node, Dict[neighbor, capacity]] flow: Dict[node, Dict[neighbor, flow_value]] Returns: residual: Dict[node, Dict[neighbor, residual_capacity]] """ residual = {v: {} for v in graph} for u in graph: for v, capacity in graph[u].items(): current_flow = flow.get(u, {}).get(v, 0) # Forward edge: remaining capacity if capacity - current_flow > 0: residual[u][v] = capacity - current_flow # Backward edge: flow that can be canceled if current_flow > 0: if v not in residual: residual[v] = {} residual[v][u] = current_flow return residual # Example usage: # Original network: S->A (cap 10), A->T (cap 8) # Current flow: S->A = 5, A->T = 5 graph = {'S': {'A': 10}, 'A': {'T': 8}, 'T': {}} flow = {'S': {'A': 5}, 'A': {'T': 5}} residual = build_residual_graph(graph, flow) # Result: {'S': {'A': 5}, 'A': {'T': 3, 'S': 5}, 'T': {'A': 5}}6d:T5cb,import java.util.*; public class ResidualGraph { /** * Build residual graph from original graph and current flow. * Uses adjacency map representation. */ public static Map> buildResidualGraph( Map> graph, Map> flow) { Map> residual = new HashMap<>(); // Initialize all vertices for (String v : graph.keySet()) { residual.put(v, new HashMap<>()); } // Process each edge for (String u : graph.keySet()) { for (Map.Entry edge : graph.get(u).entrySet()) { String v = edge.getKey(); int capacity = edge.getValue(); int currentFlow = flow.getOrDefault(u, Collections.emptyMap()) .getOrDefault(v, 0); // Forward edge: remaining capacity if (capacity - currentFlow > 0) { residual.get(u).put(v, capacity - currentFlow); } // Backward edge: flow that can be canceled if (currentFlow > 0) { residual.putIfAbsent(v, new HashMap<>()); residual.get(v).put(u, currentFlow); } } } return residual; } }6e:T541,The maximum flow problem has a fascinating history that intertwines with Cold War logistics, the birth of combinatorial optimization, and some of the most beautiful theorems in computer science. **Origins — The 1950s:** The formal study of network flows began in the 1950s, motivated by military logistics during the Cold War. The U.S. Air Force needed to understand the capacity of Soviet rail networks for transporting supplies. This practical problem led to foundational theoretical work. **Key Milestones:** **1954 — Ford and Fulkerson:** Lester Ford Jr. and Delbert Fulkerson, working at RAND Corporation, published the foundational paper establishing the Ford-Fulkerson method and proving the Max-Flow Min-Cut Theorem. This work is considered a cornerstone of combinatorial optimization. **1970 — Edmonds-Karp:** Jack Edmonds and Richard Karp showed that using BFS to find augmenting paths guarantees O(VE²) time complexity, making the algorithm truly polynomial. **1970 — Dinic's Algorithm:** Efim Dinic independently discovered a more efficient blocking flow approach achieving O(V²E) time, which was further improved for special cases. **Modern Developments:** Advanced algorithms like Push-Relabel (Goldberg-Tarjan, 1988) and more recent near-linear time algorithms have continued to push the boundaries of efficiency.64:{"json":{"id":"seed_6530e4cef9d23ebdddf6960911e7f896","slug":"network-flow-conceptual-introduction","category":"Data Structures & Algorithms","topic":"Network Flow","title":"Network Flow — Conceptual Introduction","description":"Master the foundational concepts of network flow theory, including the maximum flow problem, flow networks, the Ford-Fulkerson method, the max-flow min-cut theorem, and real-world applications in resource allocation and bipartite matching.","difficulty":"ADVANCED","estimatedMinutes":90,"pages":[{"id":"seed_df71f7c21192facf8c1c6905d43c94fb","title":"The Maximum Flow Problem — Optimizing Resource Distribution","order":0,"content":[{"id":"opening-hook","title":"When Pipes, Routes, and Networks Meet Optimization","content":[{"data":{"content":"Imagine you're the chief engineer of a water distribution company. You have a massive network of pipes connecting a reservoir (your **source**) to a city's water treatment facility (your **sink**). Each pipe has a maximum capacity—it can only carry so much water per second before the pressure becomes dangerous. Your mission: **determine the maximum amount of water you can push through this network from source to sink**.\n\nThis seemingly simple question—*how much can flow?*—is the essence of the **Maximum Flow Problem**, one of the most elegant and powerful optimization frameworks in computer science. Far from being merely about water or pipes, the maximum flow problem captures the mathematical structure underlying countless real-world optimization challenges."},"type":"text"},{"data":{"icon":"Target","title":"What You'll Master in This Module","content":"By the end of this module, you'll understand how to model flow networks, grasp the mechanics of the Ford-Fulkerson method, appreciate the deep connection between maximum flow and minimum cuts, and recognize flow problems disguised in domains like bipartite matching, resource allocation, and scheduling. These concepts form the backbone of advanced algorithmic problem-solving.","variant":"info"},"type":"callout"}]},{"id":"formal-definition","title":"The Maximum Flow Problem — Formal Definition","content":[{"data":{"content":"Let's ground our intuition with mathematical precision. The Maximum Flow Problem is defined on a special type of directed graph called a **flow network**.\n\n**Formal Definition:**\n\nA **flow network** is a directed graph G = (V, E) with the following properties:\n\n1. **Source vertex (s):** A distinguished vertex with no incoming edges (or where we ignore incoming edges). All flow originates here.\n\n2. **Sink vertex (t):** A distinguished vertex with no outgoing edges (or where we ignore outgoing edges). All flow terminates here.\n\n3. **Capacity function c:** Each edge (u, v) ∈ E has an associated **capacity** c(u, v) ≥ 0, representing the maximum flow that can traverse that edge.\n\n4. **Flow function f:** An assignment of flow values to edges, where f(u, v) represents the actual flow from u to v."},"type":"text"},{"data":{"icon":"Lightbulb","title":"The Central Question","content":"Given a flow network with source s and sink t, **what is the maximum total flow** that can be sent from s to t while respecting all edge capacities? This value is called the **maximum flow** of the network.","variant":"note"},"type":"callout"},{"data":{"content":"**The Constraints a Valid Flow Must Satisfy:**\n\nFor a flow function f to be valid, it must satisfy two fundamental constraints:\n\n**1. Capacity Constraint (Don't Overflow):**\n\nFor every edge (u, v) ∈ E:\n\n$$0 \\leq f(u, v) \\leq c(u, v)$$\n\nThe flow on each edge must be non-negative and cannot exceed the edge's capacity. You can't push more water through a pipe than the pipe can handle, and flow doesn't go backward spontaneously.\n\n**2. Flow Conservation (What Goes In Must Come Out):**\n\nFor every vertex v ∈ V except s and t:\n\n$$\\sum_{u \\in V} f(u, v) = \\sum_{w \\in V} f(v, w)$$\n\nThe total flow entering any intermediate vertex must equal the total flow leaving it. Flow doesn't accumulate or disappear at intermediate nodes—like water through a pipe network, what enters a junction must exit."},"type":"text"},{"data":{"rows":[["Capacity Constraint","0 ≤ f(u,v) ≤ c(u,v)","Flow can't exceed pipe capacity","Pushing 100 gallons/sec through a 50 gallon/sec pipe"],["Conservation","Flow in = Flow out (at intermediate nodes)","No accumulation at junctions","10 units enter vertex v, but 15 units leave"]],"caption":"The Two Fundamental Flow Constraints","headers":["Constraint","Mathematical Form","Intuition","Violation Example"]},"type":"table"}],"titleType":"number","titleNumber":1},{"id":"visualizing-flow-networks","title":"Visualizing Flow Networks","content":[{"data":{"content":"Abstract definitions become concrete through visualization. Let's examine a simple flow network to build intuition.\n\n**Consider this network:**\n\n```\n [A]----10--->[C]\n ↗ ↘ ↗ ↘\n 8 4 6 8\n ↗ ↘ ↗ ↘\n [S] [B]----5---->[T]\n ↘ ↗ ↘ ↗\n 6 3 4 9\n ↘ ↗ ↘ ↗\n [D]----7--->[E]\n```\n\nHere, **S** is the source, **T** is the sink, and the numbers represent edge capacities. The vertices A, B, C, D, E are intermediate nodes through which flow is routed.\n\n**Key Observations:**\n\n1. **Multiple paths exist** from S to T (S→A→C→T, S→B→T, S→D→E→T, etc.)\n2. **Bottlenecks matter** — even if S→A has capacity 8 and A→C has capacity 10, we can only push 8 units through this path segment\n3. **Flow can split and merge** — flow from S can go through multiple vertices and recombine before reaching T"},"type":"text"},{"data":{"icon":"Lightbulb","title":"The Bottleneck Principle","content":"The maximum flow along any single path from source to sink is limited by the **minimum capacity edge** on that path—the bottleneck. However, maximum flow in a network isn't simply the sum of individual path capacities, because edges may be shared across multiple paths.","variant":"tip"},"type":"callout"},{"data":{"content":"**A Simple Example with Numbers:**\n\nConsider the simplest non-trivial network:\n\n```\n [S] ---10---> [A] ---5---> [T]\n```\n\nThe maximum flow here is 5, not 10, because the bottleneck edge (A→T) limits total throughput. Even though we can push 10 units from S to A, only 5 can continue to T.\n\nNow consider a slightly more complex case:\n\n```\n ----10----\n / \n [S] [T]\n \\ /\n ----8-----\n```\n\nWith two parallel edges from S to T with capacities 10 and 8, the maximum flow is 10 + 8 = 18. The paths don't share edges, so their capacities add directly.\n\n**The complexity arises when paths share edges**—this is where naive approaches fail and sophisticated algorithms become necessary."},"type":"text"}],"titleType":"number","titleNumber":2},{"id":"why-max-flow-matters","title":"Why Maximum Flow Matters","content":[{"data":{"content":"The maximum flow problem isn't merely an academic curiosity—it models an extraordinary range of practical optimization problems. Understanding why this formulation is so powerful reveals the deep structure underlying seemingly unrelated domains."},"type":"text"},{"data":{"items":["**Transportation & Logistics** — Maximizing throughput of goods through a shipping network from warehouses (sources) to retail locations (sinks) through distribution centers.","**Computer Networks** — Determining maximum data bandwidth between two endpoints in a network with links of varying capacities.","**Pipeline Systems** — Optimizing oil, gas, or water distribution from production facilities to consumers through pipeline infrastructure.","**Airline Scheduling** — Maximizing passenger throughput or aircraft utilization across route networks with capacity constraints.","**Bipartite Matching** — Assigning workers to jobs, students to schools, or organs to patients—reducible to maximum flow (as we'll see).","**Sports Tournament Elimination** — Determining if a team can still win a tournament given current standings and remaining games.","**Image Segmentation** — Separating foreground from background in computer vision using graph cuts, which are dual to max flow."],"title":{"icon":"Target","text":"Real-World Applications of Maximum Flow","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"icon":"Sparkles","title":"The Power of Reduction","content":"Many problems that don't initially look like flow problems can be **reduced** to maximum flow. Once you recognize a problem as a flow problem in disguise, you gain access to decades of efficient algorithms and theoretical insights. This reduction skill separates expert algorithm designers from novices.","variant":"success"},"type":"callout"},{"data":{"content":"**The Computational Perspective:**\n\nFrom a complexity standpoint, maximum flow occupies a sweet spot:\n\n- It's powerful enough to model NP-complete problems in certain formulations\n- Yet efficient polynomial-time algorithms exist for the standard version\n- It provides a gateway to deeper optimization frameworks (linear programming, combinatorial optimization)\n\nAlgorithms like Ford-Fulkerson, Edmonds-Karp, and Dinic's algorithm solve maximum flow in polynomial time, making it practically applicable to real-world problem instances with millions of nodes and edges."},"type":"text"}],"titleType":"number","titleNumber":3},{"id":"value-of-flow","title":"The Value of Flow — Measuring Success","content":[{"data":{"content":"Before we can optimize flow, we need a precise way to measure it. The **value of a flow** quantifies the total amount of \"stuff\" moving from source to sink.\n\n**Definition — Value of Flow |f|:**\n\nThe value of a flow f is the total flow leaving the source (equivalently, entering the sink):\n\n$$|f| = \\sum_{v \\in V} f(s, v) - \\sum_{v \\in V} f(v, s) = \\sum_{v \\in V} f(v, t) - \\sum_{v \\in V} f(t, v)$$\n\nIn most formulations, we assume no edges enter the source and no edges leave the sink, simplifying to:\n\n$$|f| = \\sum_{v \\in V} f(s, v) = \\sum_{v \\in V} f(v, t)$$\n\nThis equivalence follows from flow conservation: every unit of flow that leaves s must eventually reach t, since intermediate vertices neither create nor absorb flow."},"type":"text"},{"data":{"icon":"Info","title":"Conservation Implies Equality","content":"The fact that total outflow from source equals total inflow to sink is not an additional constraint—it's a mathematical consequence of flow conservation at all intermediate vertices. If you sum the conservation equations across all vertices except s and t, the intermediate flows cancel, leaving source outflow equal to sink inflow.","variant":"note"},"type":"callout"},{"data":{"content":"**Worked Example:**\n\nConsider this simple network with a valid flow (shown as flow/capacity):\n\n```\n [A]\n ↗ ↘\n 5/8 5/6\n ↗ ↘\n[S] [T]\n ↘ ↗\n 3/5 3/4\n ↘ ↗\n [B]\n```\n\n**Verification:**\n\n1. **Capacity constraints:** All flows (5, 5, 3, 3) are within edge capacities (8, 6, 5, 4). ✓\n\n2. **Conservation at A:** Flow in = 5, Flow out = 5. ✓\n\n3. **Conservation at B:** Flow in = 3, Flow out = 3. ✓\n\n4. **Value of flow:** |f| = 5 + 3 = 8 (from source) = 5 + 3 = 8 (to sink). ✓\n\n**Is this maximum?** Not necessarily! There might be unused capacity that could increase the flow. Finding the true maximum requires systematic exploration—which is exactly what flow algorithms provide."},"type":"text"}],"titleType":"number","titleNumber":4},{"id":"why-greedy-fails","title":"The Challenge — Why Greedy Fails","content":[{"data":{"content":"A natural first instinct: find any path from s to t with available capacity, push as much flow as possible along it, repeat until no paths remain. This **greedy approach** seems reasonable but fails spectacularly in general.\n\n**The Classic Counterexample:**\n\nConsider this network:\n\n```\n [A]\n ↗ ↘\n 1 1\n ↗ ↘\n[S] 1 [T]\n ↘ ↗\n 1 1\n ↘ ↗\n [B]\n```\n\nWith edge from A→B having capacity 1, and all other edges having capacity 1 as well.\n\n**Greedy Execution (Bad Luck):**\n\nSuppose greedy picks path S→A→B→T first and pushes 1 unit. Now:\n- S→A is saturated (flow = capacity = 1)\n- A→B is saturated (flow = capacity = 1)\n- B→T is saturated (flow = capacity = 1)\n\n**Greedy concludes:** Maximum flow = 1. No more paths exist.\n\n**But the actual maximum is 2:**\n- Path S→A→T carries 1 unit\n- Path S→B→T carries 1 unit\n- Total flow = 2"},"type":"text"},{"data":{"icon":"AlertCircle","title":"The Fundamental Problem","content":"Greedy made a poor initial choice (using the A→B edge) that blocked better overall routing. In flow problems, local decisions can have non-local consequences. An edge used by one path might be needed by another path for a better global solution.","variant":"warning"},"type":"callout"},{"data":{"content":"**The Deep Insight:**\n\nThe failure of greedy reveals a fundamental truth: **we might need to \"undo\" previous decisions** to find the global optimum.\n\nThis leads to the brilliant concept of **residual graphs** and **augmenting paths**:\n\n- Instead of committing irrevocably to flow choices, we maintain the ability to \"push flow back\"\n- The residual graph captures not just remaining forward capacity, but also the potential to redirect existing flow\n- An augmenting path in the residual graph might use \"backward edges\" representing flow cancellation\n\nThis is the conceptual foundation of the Ford-Fulkerson method, which we'll explore in detail. The key insight: **the ability to backtrack enables finding the true optimum, even when initial choices are suboptimal**."},"type":"text"},{"data":{"rows":[["Decision model","Irrevocable choices","Choices can be revised via residual graph"],["Path selection","First available path","Augmenting paths in residual graph"],["Flow reduction","Not possible","Backward edges allow flow cancellation"],["Guarantee","May find suboptimal flow","Provably finds maximum flow"],["Complexity","Could be very fast","Polynomial (with proper path selection)"]],"caption":"Greedy vs. Optimal Flow Strategies","headers":["Aspect","Greedy Approach","Optimal Approach (e.g., Ford-Fulkerson)"]},"type":"table"}],"titleType":"number","titleNumber":5},{"id":"residual-graphs","title":"Residual Graphs — The Key Insight","content":[{"data":{"content":"The **residual graph** is the conceptual breakthrough that makes efficient maximum flow algorithms possible. It elegantly encodes both unused forward capacity AND the potential to redirect existing flow.\n\n**Definition — Residual Graph G_f:**\n\nGiven a flow network G = (V, E) with capacity function c and a flow f, the **residual graph** G_f = (V, E_f) is constructed as follows:\n\nFor each edge (u, v) ∈ E:\n\n1. **Forward edge:** If f(u, v) < c(u, v), include edge (u, v) with **residual capacity** c_f(u, v) = c(u, v) - f(u, v). This represents remaining forward capacity.\n\n2. **Backward edge:** If f(u, v) > 0, include edge (v, u) with **residual capacity** c_f(v, u) = f(u, v). This represents the ability to \"cancel\" existing flow.\n\nThe residual graph may have up to 2|E| edges: for each original edge, potentially one forward and one backward edge."},"type":"text"},{"data":{"icon":"Lightbulb","title":"The Backward Edge Intuition","content":"A backward edge (v, u) with residual capacity f(u, v) means: \"We previously sent f(u, v) units from u to v. If we 'send' flow along (v, u) in the residual graph, we're actually **canceling** some of that previous flow.\" This isn't physical flow going backward—it's a mathematical device representing flow reallocation.","variant":"tip"},"type":"callout"},{"data":{"content":"**Worked Example:**\n\nOriginal network with current flow (flow/capacity):\n\n```\n[S] --5/10--> [A] --5/8--> [T]\n```\n\nResidual graph:\n\n```\n[S] --5--> [A] --3--> [T] (forward edges: remaining capacity)\n[S] <--5-- [A] <--5-- [T] (backward edges: cancellation potential)\n```\n\n**Reading the residual graph:**\n\n1. Forward S→A (capacity 5): We can push 5 more units from S to A\n2. Backward A→S (capacity 5): We could cancel up to 5 units of S→A flow\n3. Forward A→T (capacity 3): We can push 3 more units from A to T\n4. Backward T→A (capacity 5): We could cancel up to 5 units of A→T flow\n\n**The augmenting path perspective:**\n\nAn **augmenting path** is any path from s to t in the residual graph. The existence of an augmenting path means we can increase the total flow. The amount we can increase equals the minimum residual capacity along the path (the bottleneck)."},"type":"text"},{"data":{"fileName":"residual_graph.py","languages":[{"code":"$6c","label":"Python","value":"python"},{"code":"$6d","label":"Java","value":"java"}],"showLineNumbers":true},"type":"code"}],"titleType":"number","titleNumber":6},{"id":"historical-context","title":"Historical Context and Significance","content":[{"data":{"content":"$6e"},"type":"text"},{"data":{"icon":"Info","title":"A Cold War Origin Story","content":"The original motivation for studying maximum flow was estimating enemy supply capacity. Ironically, this military application led to mathematical tools now used for peaceful purposes: internet routing, organ donation matching, airline scheduling, and computational biology.","variant":"note"},"type":"callout"},{"data":{"rows":[["Ford-Fulkerson","1954","O(E × max_flow)","Residual graphs, augmenting paths"],["Edmonds-Karp","1972","O(VE²)","BFS for shortest augmenting path"],["Dinic's","1970","O(V²E)","Level graphs, blocking flows"],["Push-Relabel","1988","O(V²E) or O(V³)","Local operations, height functions"],["King-Rao-Tarjan","1994","O(VE log_{E/(V log V)} V)","Dynamic trees"]],"caption":"Evolution of Maximum Flow Algorithms","headers":["Algorithm","Year","Time Complexity","Key Innovation"]},"type":"table"}],"titleType":"number","titleNumber":7},{"id":"summary-preview","title":"Summary and Preview","content":[{"data":{"content":"We've established the foundations of the maximum flow problem. Let's consolidate what we've learned:"},"type":"text"},{"data":{"type":"ordered","items":["**The maximum flow problem** asks: given a network with capacities, what's the maximum throughput from source to sink?","**Valid flows** must satisfy capacity constraints (don't exceed edge limits) and conservation (flow in = flow out at intermediate nodes).","**The value of a flow** is the total throughput, measured as outflow from source or inflow to sink.","**Greedy approaches fail** because early choices can block better global solutions.","**Residual graphs** encode both remaining forward capacity AND the potential to cancel/redirect existing flow.","**Augmenting paths** in the residual graph reveal opportunities to increase total flow.","**The problem has deep historical significance**, arising from Cold War logistics and spawning fundamental algorithms."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's Next:**\n\nIn the next page, we'll dive deeper into **flow network components**—examining sources, sinks, and capacities in detail. We'll explore how to properly model real-world problems as flow networks, including handling multiple sources/sinks, undirected edges, and vertex capacities. This modeling skill is often the difference between recognizing a flow problem and missing it entirely."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Foundation Established","content":"You now understand the maximum flow problem's formal definition, intuition, and significance. The residual graph concept—allowing flow \"corrections\"—is the key insight that makes polynomial-time algorithms possible. Next, we'll master the components that make up flow networks.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":8}],"isLocked":false},{"id":"seed_019f40a85847691cb16af76001a8a352","title":"Flow Networks — Source, Sink, and Capacity","order":1,"content":null,"isLocked":true},{"id":"seed_1221b3ef512ef1f7517c58b5db55cb2a","title":"Ford-Fulkerson Method — The Augmenting Path Framework","order":2,"content":null,"isLocked":true},{"id":"seed_204e775cfe0a25dbf4588665472250ce","title":"The Max-Flow Min-Cut Theorem — Duality in Optimization","order":3,"content":null,"isLocked":true},{"id":"seed_42dae3e0d303bb6096a241d1c133172a","title":"Applications — Resource Allocation, Matching, and Beyond","order":4,"content":null,"isLocked":true}]}}