Files
skills/public/network-flow-algorithms.html
zeekay 747dafba10 Register WebMCP tools on every page, and name each page's twin from site.py
Every page now loads /webmcp.js, scripts/webmcp.ts with its types
stripped (npm run webmcp). Where the browser has document.modelContext
it registers two read-only tools: search_skills over the published
skills index, and get_skill, which returns a skill's markdown checked
against the index digest. The markdown alternate link moves from
build.py to site.py, so CI holds every page to it.

The API catalog gains the site itself (llms.txt and the skills index)
and hanzo.ai/agents; the live discovery check now fetches every
catalog link. tests/site.mjs drives the tools through a recording
modelContext, and checks a browser without one loads clean.
2026-10-26 20:57:05 -07:00

752 lines
33 KiB
HTML
Raw Permalink Blame History

This file contains ambiguous Unicode characters
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
<!doctype html>
<html lang="en"><head>
<meta charset="utf-8"><meta name="viewport" content="width=device-width,initial-scale=1">
<title>network-flow-algorithms</title>
<meta name="color-scheme" content="dark">
<style>
/* Committed to one visual world: a dark instrument panel. No light variant —
the dot field and the hairline rules only read on black, and a naive
inversion would wash both out. Every colour is painted explicitly so the page
never borrows a host background. */
@font-face{font-family:'Zen';src:url('/fonts/Zen-Variable.woff2') format('woff2');font-weight:100 900;font-style:normal;font-display:swap}
@font-face{font-family:'Zen';src:url('/fonts/Zen-Italic-Variable.woff2') format('woff2');font-weight:100 900;font-style:italic;font-display:swap}
@font-face{font-family:'Zen Mono';src:url('/fonts/ZenMono-Variable.woff2') format('woff2');font-weight:100 900;font-style:normal;font-display:swap}
@font-face{font-family:'Zen Mono';src:url('/fonts/ZenMono-Italic-Variable.woff2') format('woff2');font-weight:100 900;font-style:italic;font-display:swap}
@font-face{font-family:'Zen Pixel Square';src:url('/fonts/ZenPixel-Square.woff2') format('woff2');font-style:normal;font-display:swap}
:root{
--ink:#f4f4f2; --soft:#9c9c98; --faint:#6a6a66; --ground:#000; --panel:#0a0a0a;
--line:#232323; --line-hi:#3a3a3a; --accent:#f4f4f2;
--font-zen-sans:'Zen',-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif;
--font-zen-mono:'Zen Mono',ui-monospace,"SF Mono",SFMono-Regular,Menlo,Consolas,monospace;
--font-zen-pixel-square:'Zen Pixel Square',monospace;
--mono:var(--font-zen-mono);
--sans:var(--font-zen-sans);
/* Controls are pills and surfaces are soft, as on hanzo.ai. */
--r:999px; --r-soft:14px;
}
*{box-sizing:border-box}
html{-webkit-text-size-adjust:100%}
body{margin:0;background:var(--ground);color:var(--ink);font-family:var(--sans);
font-size:16px;line-height:1.65;-webkit-font-smoothing:antialiased}
.wrap{max-width:60rem;margin:0 auto;padding:0 1.75rem}
/* The dot field. A halftone made of one repeating radial-gradient, faded out
along the diagonal by a mask so it reads as a wave rather than wallpaper. */
/* No overflow clip here: the dot field is inset to the box already, and a clip
would cut off the copy-prompt menu. */
.hero{position:relative;border-bottom:1px solid var(--line)}
.hero::before{content:"";position:absolute;inset:0;
background-image:radial-gradient(var(--line-hi) 1px, transparent 1px);
background-size:7px 7px;
-webkit-mask-image:linear-gradient(115deg,#000 0%,rgba(0,0,0,.55) 38%,transparent 72%);
mask-image:linear-gradient(115deg,#000 0%,rgba(0,0,0,.55) 38%,transparent 72%);
pointer-events:none}
.hero .wrap{position:relative;padding-top:5.5rem;padding-bottom:4rem}
nav{border-bottom:1px solid var(--line)}
nav .in{max-width:60rem;margin:0 auto;padding:1.1rem 1.75rem;display:flex;
justify-content:space-between;align-items:center;gap:1rem}
.brand{font-family:var(--mono);font-size:.85rem;letter-spacing:.14em;
text-transform:uppercase;color:var(--ink);text-decoration:none;
display:inline-flex;align-items:center;gap:.6rem}
.brand i{font-style:normal;color:var(--faint)}
.mark{width:1.15em;height:1.15em;display:block;flex:0 0 auto}
nav a.up{font-family:var(--mono);font-size:.72rem;letter-spacing:.14em;
text-transform:uppercase;color:var(--soft);text-decoration:none}
nav a.up:hover{color:var(--ink)}
h1{font-family:var(--mono);font-size:clamp(2rem,5.4vw,3.4rem);line-height:1.12;
letter-spacing:-.02em;margin:0 0 1.1rem;font-weight:500;text-wrap:balance}
h1 em{font-style:normal;color:var(--faint)}
.lede{color:var(--soft);font-size:1.05rem;max-width:52ch;margin:0 0 2.25rem}
.btns{display:flex;flex-wrap:wrap;gap:.7rem;margin:0 0 .5rem;align-items:center}
.btn{display:inline-flex;align-items:center;gap:.5rem;font-family:var(--mono);
font-size:.72rem;letter-spacing:.14em;text-transform:uppercase;
padding:.8rem 1.4rem;border:1px solid var(--line-hi);border-radius:var(--r);
color:var(--ink);text-decoration:none;background:transparent;cursor:pointer;
line-height:1.2;font-weight:400}
.btn:hover{background:#141414;text-decoration:none;border-color:var(--soft)}
.btn.solid{background:var(--ink);color:#000;border-color:var(--ink)}
.btn.solid:hover{background:#d8d8d4}
.btn .chev{width:.7em;height:.7em;flex:0 0 auto;transition:transform .15s ease}
.btn[aria-expanded="true"] .chev{transform:rotate(180deg)}
/* Copy-prompt selector. Each row copies the prompt for its own target. */
.copy{position:relative;display:inline-flex}
.menu{position:absolute;top:calc(100% + .5rem);left:0;z-index:20;min-width:21rem;
background:var(--panel);border:1px solid var(--line-hi);border-radius:var(--r-soft);
padding:.4rem;display:flex;flex-direction:column;
box-shadow:0 12px 32px rgba(0,0,0,.75)}
.menu[hidden]{display:none}
.mi{display:flex;align-items:center;gap:.7rem;width:100%;text-align:left;
padding:.62rem .8rem;border:0;border-radius:calc(var(--r-soft) - .35rem);
background:transparent;color:var(--ink);font-family:var(--mono);font-size:.76rem;
letter-spacing:.04em;text-decoration:none;cursor:pointer;line-height:1.3;
white-space:nowrap}
.mi:hover,.mi:focus-visible{background:#181818;outline:none}
.mi .mark{width:1.05rem;height:1.05rem;color:var(--soft)}
.mi:hover .mark{color:var(--ink)}
.mi u{margin-left:auto;color:var(--faint);text-decoration:none;font-size:.68rem;
letter-spacing:.1em;text-transform:uppercase}
/* Works-with bar: one scrolling row, name and mark per agent. */
.strip{border-bottom:1px solid var(--line);background:var(--panel)}
.strip .in{max-width:60rem;margin:0 auto;padding:.9rem 1.75rem;display:flex;
align-items:center;gap:1.25rem;font-family:var(--mono);font-size:.72rem;
letter-spacing:.1em;text-transform:uppercase;color:var(--faint)}
.strip b{color:var(--soft);font-weight:400;flex:0 0 auto;
border-right:1px solid var(--line);padding-right:1.25rem;align-self:stretch;
display:flex;align-items:center}
.bar{display:flex;align-items:center;gap:.5rem;flex:1 1 auto;min-width:0;
overflow-x:auto;scrollbar-width:none;scroll-snap-type:x proximity;
-webkit-overflow-scrolling:touch;
-webkit-mask-image:linear-gradient(90deg,#000 calc(100% - 3rem),transparent);
mask-image:linear-gradient(90deg,#000 calc(100% - 3rem),transparent)}
.bar::-webkit-scrollbar{display:none}
.agent{display:inline-flex;align-items:center;gap:.45rem;flex:0 0 auto;
padding:.4rem .85rem;border:1px solid var(--line);border-radius:var(--r);
color:var(--soft);white-space:nowrap;scroll-snap-align:start;
text-decoration:none;background:var(--ground)}
.agent:hover{color:var(--ink);border-color:var(--line-hi);text-decoration:none}
.agent .mark{width:.95rem;height:.95rem}
h2{font-family:var(--mono);font-size:1.1rem;letter-spacing:-.01em;margin:2.75rem 0 .75rem;font-weight:500}
h3{font-size:1rem;margin:2rem 0 .5rem;font-weight:600}
h4,h5,h6{font-size:.94rem;margin:1.5rem 0 .5rem;font-weight:600}
p{margin:0 0 1rem;max-width:70ch}
ul,ol{margin:0 0 1rem;padding-left:1.35rem;max-width:70ch}
li{margin:.22rem 0}
a{color:var(--ink);text-decoration:underline;text-underline-offset:3px;
text-decoration-color:var(--line-hi)}
a:hover{text-decoration-color:var(--ink)}
a:focus-visible{outline:1px solid var(--ink);outline-offset:3px}
code{font-family:var(--mono);font-size:.85em;background:var(--panel);
border:1px solid var(--line);border-radius:5px;padding:.1em .36em}
pre{background:var(--panel);border:1px solid var(--line);padding:1rem 1.1rem;
border-radius:var(--r-soft);overflow-x:auto;margin:0 0 1.25rem}
pre code{background:none;border:0;padding:0;font-size:.82rem;line-height:1.7}
blockquote{margin:0 0 1rem;padding-left:1rem;border-left:1px solid var(--line-hi);color:var(--soft)}
hr{border:0;border-top:1px solid var(--line);margin:2.5rem 0}
table{border-collapse:collapse;width:100%;margin:0 0 1.25rem;font-size:.92rem;
display:block;overflow-x:auto}
th,td{border:1px solid var(--line);padding:.5rem .7rem;text-align:left}
.curl{display:block;background:var(--panel);border:1px solid var(--line);
border-radius:var(--r-soft);padding:.95rem 1.1rem;font-family:var(--mono);
font-size:.8rem;color:var(--soft);overflow-x:auto;margin:0 0 2.5rem;
white-space:pre;line-height:1.9}
.curl b{color:var(--ink);font-weight:400}
.curl i{font-style:normal;color:var(--faint)}
/* index */
#q{width:100%;padding:.85rem 1.2rem;font-family:var(--mono);font-size:.85rem;color:var(--ink);
background:var(--panel);border:1px solid var(--line);border-radius:var(--r);margin:0 0 .6rem}
#q::placeholder{color:var(--faint);text-transform:uppercase;letter-spacing:.1em;font-size:.72rem}
#q:focus{outline:none;border-color:var(--soft)}
#count{color:var(--faint);font-family:var(--mono);font-size:.72rem;letter-spacing:.1em;
text-transform:uppercase;margin:0 0 2rem}
.cat{margin:2.5rem 0 .5rem;font-family:var(--mono);font-size:.7rem;letter-spacing:.16em;
text-transform:uppercase;color:var(--faint);border-bottom:1px solid var(--line);
padding-bottom:.45rem}
.row{display:block;padding:.6rem .9rem;margin:0 -.9rem;border-bottom:1px solid var(--line);
border-radius:var(--r-soft);text-decoration:none}
.row:hover{background:#0a0a0a}
.nm{font-family:var(--mono);font-size:.84rem;color:var(--ink);display:block}
.ds{color:var(--soft);font-size:.9rem;display:block;margin-top:.12rem}
footer{margin-top:4rem;padding:2rem 0 4rem;border-top:1px solid var(--line);
color:var(--faint);font-size:.85rem}
footer a{color:var(--soft)}
.fmap{display:grid;gap:1.75rem;grid-template-columns:repeat(auto-fit,minmax(11rem,1fr));
margin:0 0 2rem;font-size:.85rem}
.fmap b{display:block;font-family:var(--mono);font-size:.68rem;letter-spacing:.16em;
text-transform:uppercase;color:var(--faint);font-weight:400;margin:0 0 .6rem;
border-bottom:1px solid var(--line);padding-bottom:.4rem}
.fmap a{display:inline-block;color:var(--ink);text-decoration:none;margin:.3rem .35rem 0 0}
.fmap a:hover{text-decoration:underline}
.fmap div{color:var(--faint);line-height:1.5}
.fend{border-top:1px solid var(--line);padding-top:1.25rem;font-size:.82rem}
@media (max-width:640px){
.hero .wrap{padding-top:3.25rem;padding-bottom:2.75rem}
.btns{gap:.5rem}
.btn{padding:.75rem 1.15rem;font-size:.68rem}
.copy,.copy .btn{width:100%;justify-content:center}
.menu{left:0;right:0;min-width:0}
.strip .in{flex-direction:column;align-items:flex-start;gap:.6rem;padding:.9rem 1.75rem}
.strip b{border-right:0;padding-right:0}
.bar{width:100%}
}
</style>
<link rel="icon" href="/favicon.svg">
<link rel="canonical" href="https://hanzoskills.com/network-flow-algorithms">
<link rel="alternate" type="text/markdown" href="/network-flow-algorithms.md">
<script type="module" src="/webmcp.js"></script>
</head>
<!-- Reading this with a machine? Every page here is also plain markdown.
This one: https://hanzoskills.com/network-flow-algorithms.md
Index: https://hanzoskills.com/llms.txt
Corpus: https://hanzoskills.com/all.md
Append .md to any path for the markdown twin. -->
<body>
<nav><div class="in">
<a class="brand" href="/"><svg class="mark" viewBox="0 0 67 67" fill="currentColor" aria-hidden="true"><path d="M22.21 67V44.6369H0V67H22.21Z"/><path d="M66.7038 22.3184H22.2534L0.0878906 44.6367H44.4634L66.7038 22.3184Z"/><path d="M22.21 0H0V22.3184H22.21V0Z"/><path d="M66.7198 0H44.5098V22.3184H66.7198V0Z"/><path d="M66.7198 67V44.6369H44.5098V67H66.7198Z"/></svg> HANZO<i>SKILLS</i></a>
<a class="up" href="/">All skills</a>
</div></nav>
<div class="wrap">
<h1>network-flow-algorithms</h1><p class="lede">Maximum flow, minimum cut, Ford-Fulkerson, Edmonds-Karp, and flow-based algorithms for capacity-constrained network optimization</p><h1>Network Flow Algorithms</h1>
<p><strong>Last Updated</strong>: 2025-10-25</p>
<h2>When to Use This Skill</h2>
<p><strong>Activate when</strong>:</p>
<ul><li>Maximizing throughput in networks (data, traffic, pipelines)</li><li>Finding bottlenecks in systems</li><li>Solving bipartite matching problems</li><li>Computing minimum cuts in graphs</li><li>Optimizing resource allocation with capacities</li><li>Solving circulation and transportation problems</li></ul>
<p><strong>Prerequisites</strong>: <code>graph-theory-fundamentals.md</code>, <code>graph-data-structures.md</code>, <code>graph-traversal-algorithms.md</code></p>
<p><strong>Related Skills</strong>: <code>shortest-path-algorithms.md</code>, <code>minimum-spanning-tree.md</code>, <code>advanced-graph-algorithms.md</code></p>
<hr>
<h2>Core Concepts</h2>
<h3>Flow Network</h3>
<p><strong>Definition</strong>: Directed graph G = (V, E) with:</p>
<ul><li><strong>Source</strong> s ∈ V: Flow originates here</li><li><strong>Sink</strong> t ∈ V: Flow terminates here</li><li><strong>Capacity</strong> c: E → ℝ⁺: Maximum flow on each edge</li><li><strong>Flow</strong> f: E → ℝ: Actual flow on each edge</li></ul>
<p><strong>Flow Properties</strong>:</p>
<pre><code>1. Capacity constraint: 0 ≤ f(u,v) ≤ c(u,v) for all (u,v) ∈ E
2. Flow conservation: ∑f(u,v) = ∑f(v,w) for all v ∈ V \ {s,t}
(in) (out)
(Flow in = flow out for non-source/sink vertices)
3. Value of flow: |f| = ∑f(s,v) - ∑f(u,s)
(out of s) (into s)</code></pre>
<p><strong>Maximum Flow Problem</strong>: Find flow f with maximum value |f|</p>
<hr>
<h2>Core Algorithms</h2>
<h3>1. Ford-Fulkerson Method</h3>
<p><strong>Concept</strong>: Iteratively find augmenting paths and increase flow</p>
<p><strong>Key Ideas</strong>:</p>
<ul><li><strong>Residual graph</strong> Gf: Shows remaining capacity</li><li><strong>Augmenting path</strong>: Path from s to t in residual graph</li><li><strong>Max-flow min-cut theorem</strong>: Max flow value = min cut capacity</li></ul>
<pre><code class="lang-python">from typing import Dict, List, Tuple, Optional
from collections import defaultdict, deque
import math
class FlowNetwork:
&quot;&quot;&quot;Flow network representation&quot;&quot;&quot;
def __init__(self, num_vertices: int):
self.num_vertices = num_vertices
# capacity[u][v] = capacity from u to v
self.capacity: Dict[int, Dict[int, float]] = defaultdict(lambda: defaultdict(float))
# flow[u][v] = current flow from u to v
self.flow: Dict[int, Dict[int, float]] = defaultdict(lambda: defaultdict(float))
def add_edge(self, u: int, v: int, capacity: float):
&quot;&quot;&quot;Add directed edge with capacity&quot;&quot;&quot;
self.capacity[u][v] += capacity
def get_residual_capacity(self, u: int, v: int) -&gt; float:
&quot;&quot;&quot;Get residual capacity: capacity - flow&quot;&quot;&quot;
return self.capacity[u][v] - self.flow[u][v]
def get_neighbors(self, u: int) -&gt; List[int]:
&quot;&quot;&quot;Get all neighbors (forward and backward edges) in residual graph&quot;&quot;&quot;
neighbors = set()
# Forward edges with residual capacity
for v in self.capacity[u]:
if self.get_residual_capacity(u, v) &gt; 0:
neighbors.add(v)
# Backward edges with flow (can push back)
for v in self.capacity:
if self.flow[v][u] &gt; 0:
neighbors.add(v)
return list(neighbors)
def ford_fulkerson_dfs(network: FlowNetwork, source: int, sink: int
) -&gt; Tuple[float, Dict[int, Dict[int, float]]]:
&quot;&quot;&quot;
Ford-Fulkerson with DFS for finding augmenting paths
Time: O(E × |f*|) where |f*| is max flow value
Not polynomial - can be slow if capacities are large
Returns: (max_flow_value, flow_dict)
&quot;&quot;&quot;
max_flow = 0.0
def dfs_augment(u: int, min_capacity: float, visited: set) -&gt; float:
&quot;&quot;&quot;DFS to find augmenting path, returns bottleneck capacity&quot;&quot;&quot;
if u == sink:
return min_capacity
visited.add(u)
for v in network.get_neighbors(u):
if v in visited:
continue
residual = network.get_residual_capacity(u, v)
if residual &gt; 0:
# Augment along this edge
bottleneck = dfs_augment(v, min(min_capacity, residual), visited)
if bottleneck &gt; 0:
# Update flow
network.flow[u][v] += bottleneck
network.flow[v][u] -= bottleneck # Reverse flow
return bottleneck
return 0.0
# Find augmenting paths until none exist
while True:
visited = set()
augment = dfs_augment(source, math.inf, visited)
if augment == 0:
break # No more augmenting paths
max_flow += augment
return max_flow, dict(network.flow)
# Example usage
network = FlowNetwork(6)
network.add_edge(0, 1, 16)
network.add_edge(0, 2, 13)
network.add_edge(1, 2, 10)
network.add_edge(1, 3, 12)
network.add_edge(2, 1, 4)
network.add_edge(2, 4, 14)
network.add_edge(3, 2, 9)
network.add_edge(3, 5, 20)
network.add_edge(4, 3, 7)
network.add_edge(4, 5, 4)
max_flow, flow = ford_fulkerson_dfs(network, source=0, sink=5)
print(f&quot;Maximum flow: {max_flow}&quot;) # 23.0</code></pre>
<h3>2. Edmonds-Karp Algorithm</h3>
<p><strong>Concept</strong>: Ford-Fulkerson using BFS to find shortest augmenting paths</p>
<p><strong>Properties</strong>:</p>
<ul><li><strong>Time</strong>: O(V × E²) - polynomial, independent of capacities</li><li><strong>Space</strong>: O(V + E)</li><li><strong>Guarantees</strong>: Finds max flow in polynomial time</li></ul>
<pre><code class="lang-python">def edmonds_karp(network: FlowNetwork, source: int, sink: int
) -&gt; Tuple[float, Dict[int, Dict[int, float]]]:
&quot;&quot;&quot;
Edmonds-Karp maximum flow algorithm
Uses BFS to find shortest augmenting path in each iteration
Time: O(V × E²)
&quot;&quot;&quot;
max_flow = 0.0
def bfs_augment() -&gt; Tuple[Optional[List[int]], float]:
&quot;&quot;&quot;
BFS to find shortest augmenting path
Returns: (path, bottleneck_capacity) or (None, 0)
&quot;&quot;&quot;
queue = deque([source])
parents = {source: None}
while queue:
u = queue.popleft()
if u == sink:
# Reconstruct path and find bottleneck
path = []
node = sink
bottleneck = math.inf
while node != source:
parent = parents[node]
path.append(node)
# Update bottleneck
residual = network.get_residual_capacity(parent, node)
bottleneck = min(bottleneck, residual)
node = parent
path.append(source)
path.reverse()
return path, bottleneck
# Explore neighbors in residual graph
for v in network.get_neighbors(u):
if v not in parents and network.get_residual_capacity(u, v) &gt; 0:
parents[v] = u
queue.append(v)
return None, 0.0
# Find augmenting paths until none exist
while True:
path, bottleneck = bfs_augment()
if path is None:
break
# Augment flow along path
for i in range(len(path) - 1):
u, v = path[i], path[i + 1]
network.flow[u][v] += bottleneck
network.flow[v][u] -= bottleneck
max_flow += bottleneck
return max_flow, dict(network.flow)
# Example usage (same network as above)
network2 = FlowNetwork(6)
network2.add_edge(0, 1, 16)
network2.add_edge(0, 2, 13)
network2.add_edge(1, 2, 10)
network2.add_edge(1, 3, 12)
network2.add_edge(2, 1, 4)
network2.add_edge(2, 4, 14)
network2.add_edge(3, 2, 9)
network2.add_edge(3, 5, 20)
network2.add_edge(4, 3, 7)
network2.add_edge(4, 5, 4)
max_flow, flow = edmonds_karp(network2, source=0, sink=5)
print(f&quot;Maximum flow (Edmonds-Karp): {max_flow}&quot;) # 23.0</code></pre>
<h3>3. Minimum Cut</h3>
<p><strong>Concept</strong>: Partition vertices into sets S and T such that s ∈ S, t ∈ T, minimizing capacity of edges crossing cut</p>
<p><strong>Max-Flow Min-Cut Theorem</strong>: Maximum flow value = minimum cut capacity</p>
<pre><code class="lang-python">def find_min_cut(network: FlowNetwork, source: int, sink: int
) -&gt; Tuple[set, set, List[Tuple[int, int]], float]:
&quot;&quot;&quot;
Find minimum cut after computing maximum flow
Must run max flow algorithm first!
Returns: (S, T, cut_edges, cut_capacity)
where S = reachable from source in residual graph
T = unreachable from source
cut_edges = edges crossing from S to T
&quot;&quot;&quot;
# BFS from source in residual graph
reachable = {source}
queue = deque([source])
while queue:
u = queue.popleft()
for v in network.get_neighbors(u):
if v not in reachable and network.get_residual_capacity(u, v) &gt; 0:
reachable.add(v)
queue.append(v)
# Partition: S = reachable, T = unreachable
S = reachable
T = set(range(network.num_vertices)) - S
# Find cut edges and compute capacity
cut_edges = []
cut_capacity = 0.0
for u in S:
for v in network.capacity[u]:
if v in T:
cut_edges.append((u, v))
cut_capacity += network.capacity[u][v]
return S, T, cut_edges, cut_capacity
# Example usage
network3 = FlowNetwork(6)
network3.add_edge(0, 1, 16)
network3.add_edge(0, 2, 13)
network3.add_edge(1, 2, 10)
network3.add_edge(1, 3, 12)
network3.add_edge(2, 1, 4)
network3.add_edge(2, 4, 14)
network3.add_edge(3, 2, 9)
network3.add_edge(3, 5, 20)
network3.add_edge(4, 3, 7)
network3.add_edge(4, 5, 4)
# First compute max flow
max_flow, _ = edmonds_karp(network3, source=0, sink=5)
# Then find min cut
S, T, cut_edges, cut_capacity = find_min_cut(network3, source=0, sink=5)
print(f&quot;Max flow: {max_flow}&quot;) # 23.0
print(f&quot;Min cut capacity: {cut_capacity}&quot;) # 23.0 (equal!)
print(f&quot;Cut edges: {cut_edges}&quot;)
print(f&quot;S = {S}, T = {T}&quot;)</code></pre>
<h3>4. Bipartite Matching via Flow</h3>
<p><strong>Concept</strong>: Maximum bipartite matching reduces to maximum flow problem</p>
<p><strong>Reduction</strong>:</p>
<ol><li>Create source s connected to all left vertices (capacity 1)</li><li>Create sink t connected to all right vertices (capacity 1)</li><li>Direct edges from left to right (capacity 1)</li><li>Max flow = maximum matching size</li></ol>
<pre><code class="lang-python">def maximum_bipartite_matching(left_vertices: set,
right_vertices: set,
edges: List[Tuple[int, int]]
) -&gt; List[Tuple[int, int]]:
&quot;&quot;&quot;
Find maximum matching in bipartite graph using max flow
Args:
left_vertices: Vertices in left partition
right_vertices: Vertices in right partition
edges: Edges between left and right
Returns: List of matched pairs
&quot;&quot;&quot;
# Create flow network
num_vertices = len(left_vertices) + len(right_vertices) + 2
source = num_vertices - 2
sink = num_vertices - 1
network = FlowNetwork(num_vertices)
# Source to left vertices (capacity 1)
for u in left_vertices:
network.add_edge(source, u, 1)
# Right vertices to sink (capacity 1)
for v in right_vertices:
network.add_edge(v, sink, 1)
# Left to right edges (capacity 1)
for u, v in edges:
network.add_edge(u, v, 1)
# Compute max flow
max_flow, flow_dict = edmonds_karp(network, source, sink)
# Extract matching from flow
matching = []
for u in left_vertices:
for v in right_vertices:
if flow_dict[u][v] == 1: # Flow of 1 means matched
matching.append((u, v))
return matching
# Example: Job assignment
jobs = {0, 1, 2} # Left: workers
tasks = {3, 4, 5} # Right: tasks
edges = [
(0, 3), (0, 4), # Worker 0 can do tasks 3, 4
(1, 3), (1, 5), # Worker 1 can do tasks 3, 5
(2, 4), (2, 5) # Worker 2 can do tasks 4, 5
]
matching = maximum_bipartite_matching(jobs, tasks, edges)
print(f&quot;Maximum matching: {matching}&quot;) # 3 workers matched</code></pre>
<hr>
<h2>Advanced Algorithms</h2>
<h3>Push-Relabel Algorithm</h3>
<p><strong>Concept</strong>: Maintain preflow (local excess allowed), push flow forward, relabel vertices</p>
<p><strong>Properties</strong>:</p>
<ul><li><strong>Time</strong>: O(V² × E) with simple implementation, O(V³) with optimizations</li><li><strong>Space</strong>: O(V + E)</li><li><strong>Advantage</strong>: Faster on dense graphs, parallelizable</li></ul>
<pre><code class="lang-python">class PushRelabel:
&quot;&quot;&quot;Push-relabel maximum flow algorithm&quot;&quot;&quot;
def __init__(self, network: FlowNetwork, source: int, sink: int):
self.network = network
self.source = source
self.sink = sink
# Height function: source at V, others at 0
self.height = [0] * network.num_vertices
self.height[source] = network.num_vertices
# Excess flow at each vertex
self.excess = [0.0] * network.num_vertices
# Initialize: push max flow from source
for v in network.capacity[source]:
capacity = network.capacity[source][v]
network.flow[source][v] = capacity
network.flow[v][source] = -capacity
self.excess[v] = capacity
self.excess[source] -= capacity
def push(self, u: int, v: int):
&quot;&quot;&quot;Push flow from u to v&quot;&quot;&quot;
# Push minimum of excess and residual capacity
residual = self.network.get_residual_capacity(u, v)
push_amount = min(self.excess[u], residual)
self.network.flow[u][v] += push_amount
self.network.flow[v][u] -= push_amount
self.excess[u] -= push_amount
self.excess[v] += push_amount
def relabel(self, u: int):
&quot;&quot;&quot;Increase height of vertex u&quot;&quot;&quot;
min_height = math.inf
for v in self.network.get_neighbors(u):
if self.network.get_residual_capacity(u, v) &gt; 0:
min_height = min(min_height, self.height[v])
if min_height &lt; math.inf:
self.height[u] = min_height + 1
def discharge(self, u: int):
&quot;&quot;&quot;Push all excess flow from u&quot;&quot;&quot;
while self.excess[u] &gt; 0:
# Try to push to neighbors with lower height
pushed = False
for v in self.network.get_neighbors(u):
if self.excess[u] == 0:
break
residual = self.network.get_residual_capacity(u, v)
if residual &gt; 0 and self.height[u] == self.height[v] + 1:
self.push(u, v)
pushed = True
if not pushed:
# No valid push - relabel
self.relabel(u)
def max_flow(self) -&gt; float:
&quot;&quot;&quot;Compute maximum flow using push-relabel&quot;&quot;&quot;
# Process all vertices with excess (except source/sink)
work_list = [v for v in range(self.network.num_vertices)
if v != self.source and v != self.sink
and self.excess[v] &gt; 0]
while work_list:
u = work_list.pop()
if self.excess[u] &gt; 0:
self.discharge(u)
# Re-add neighbors if they now have excess
for v in self.network.get_neighbors(u):
if v != self.source and v != self.sink and self.excess[v] &gt; 0:
if v not in work_list:
work_list.append(v)
# Max flow = excess at sink
return self.excess[self.sink]</code></pre>
<hr>
<h2>Patterns</h2>
<h3>Pattern 1: Algorithm Selection</h3>
<pre><code class="lang-python">def choose_flow_algorithm(graph_info: dict) -&gt; str:
&quot;&quot;&quot;Select optimal max flow algorithm&quot;&quot;&quot;
num_vertices = graph_info[&quot;num_vertices&quot;]
num_edges = graph_info[&quot;num_edges&quot;]
max_capacity = graph_info.get(&quot;max_capacity&quot;, math.inf)
if max_capacity &lt; 100 and num_vertices &lt; 1000:
return &quot;Ford-Fulkerson (DFS)&quot; # Simple, works for small capacities
if num_edges &lt; num_vertices ** 1.5:
return &quot;Edmonds-Karp&quot; # Good for sparse graphs
return &quot;Push-Relabel&quot; # Best for dense graphs</code></pre>
<h3>Pattern 2: Flow Decomposition</h3>
<pre><code class="lang-python">def decompose_flow(network: FlowNetwork, source: int, sink: int, flow_dict: dict
) -&gt; List[Tuple[List[int], float]]:
&quot;&quot;&quot;
Decompose flow into paths and cycles
Returns: List of (path, flow_amount) pairs
&quot;&quot;&quot;
paths = []
# Create residual graph from flow
residual = defaultdict(lambda: defaultdict(float))
for u in flow_dict:
for v in flow_dict[u]:
if flow_dict[u][v] &gt; 0:
residual[u][v] = flow_dict[u][v]
# Extract paths using DFS
while residual[source]:
path = [source]
current = source
min_flow = math.inf
# Find path from source to sink
while current != sink:
for next_v in residual[current]:
if residual[current][next_v] &gt; 0:
path.append(next_v)
min_flow = min(min_flow, residual[current][next_v])
current = next_v
break
# Subtract flow along path
for i in range(len(path) - 1):
u, v = path[i], path[i + 1]
residual[u][v] -= min_flow
if residual[u][v] == 0:
del residual[u][v]
paths.append((path, min_flow))
return paths</code></pre>
<hr>
<h2>Quick Reference</h2>
<h3>Algorithm Comparison</h3>
<p>| Algorithm | Time | Space | Best Use Case | |-----------|------|-------|---------------| | Ford-Fulkerson (DFS) | O(E × \|f*\|) | O(V) | Small integer capacities | | Edmonds-Karp (BFS) | O(V × E²) | O(V) | General purpose, polynomial | | Push-Relabel | O(V² × E) | O(V) | Dense graphs | | Dinic | O(V² × E) | O(V) | Better average case |</p>
<h3>Max-Flow Min-Cut Theorem</h3>
<pre><code>max_flow(s, t) = min_cut(S, T)
where S = vertices reachable from s in residual graph
T = vertices not reachable from s</code></pre>
<hr>
<h2>Anti-Patterns</h2>
<h3>❌ Not Checking Undirected Graphs</h3>
<pre><code class="lang-python"># WRONG: Flow algorithms for directed graphs only
undirected_graph = ...
max_flow = edmonds_karp(undirected_graph, s, t) # Incorrect!
# CORRECT: Convert undirected to directed (both directions)
for u, v in undirected_edges:
network.add_edge(u, v, capacity)
network.add_edge(v, u, capacity) # Reverse edge</code></pre>
<h3>❌ Forgetting Integer Capacities for Ford-Fulkerson</h3>
<pre><code class="lang-python"># WRONG: Ford-Fulkerson with large/fractional capacities
network.add_edge(0, 1, 1e9) # May take 10⁹ iterations!
# CORRECT: Use Edmonds-Karp for large capacities
max_flow = edmonds_karp(network, s, t) # Polynomial time</code></pre>
<hr>
<h2>Related Skills</h2>
<p><strong>Next Steps</strong>:</p>
<ul><li><code>advanced-graph-algorithms.md</code> → Matching, vertex cover, edge coloring</li><li><code>graph-applications.md</code> → Real-world network optimization</li></ul>
<p><strong>Foundations</strong>:</p>
<ul><li><code>graph-theory-fundamentals.md</code> → Basic graph concepts</li><li><code>graph-traversal-algorithms.md</code> → BFS and DFS</li><li><code>shortest-path-algorithms.md</code> → Path finding algorithms</li></ul>
<hr>
<h2>Summary</h2>
<p>Network flow algorithms solve capacity-constrained optimization problems:</p>
<ul><li><strong>Ford-Fulkerson</strong>: Augmenting path method, O(E × |f*|)</li><li><strong>Edmonds-Karp</strong>: BFS-based augmenting paths, O(V × E²)</li><li><strong>Min Cut</strong>: Partition with minimum capacity, equals max flow</li><li><strong>Bipartite Matching</strong>: Reduces to max flow problem</li></ul>
<p><strong>Key takeaways</strong>:</p>
<ol><li>Max-flow min-cut theorem: Maximum flow = minimum cut capacity</li><li>Edmonds-Karp guarantees polynomial time via BFS shortest paths</li><li>Bipartite matching, edge-disjoint paths reduce to max flow</li><li>Residual graph guides augmenting path search</li><li>Push-relabel often faster on dense graphs</li></ol>
<p><strong>Next</strong>: Move to <code>advanced-graph-algorithms.md</code> for specialized algorithms.</p>
<footer>
<div class="fmap">
<div><b>Build</b>
<a href="https://hanzo.app">hanzo.app</a> app builder
<a href="https://hanzo.codes">hanzo.codes</a> code with an agent
<a href="https://hanzoskills.com">hanzoskills.com</a> what an agent reads</div>
<div><b>Run</b>
<a href="https://console.hanzo.ai">console.hanzo.ai</a> cloud console
<a href="https://api.hanzo.ai">api.hanzo.ai</a> the API</div>
<div><b>Account</b>
<a href="https://hanzo.id">hanzo.id</a> sign in
<a href="https://pay.hanzo.ai">pay.hanzo.ai</a> top up
<a href="https://billing.hanzo.ai">billing.hanzo.ai</a> invoices and usage</div>
<div><b>Company</b>
<a href="https://hanzo.ai">hanzo.ai</a> canonical
<a href="https://hanzo.ventures">hanzo.ventures</a> ventures</div>
</div>
<div class="fend"><a href="/network-flow-algorithms.md">This page as plain text</a> · <a href="/llms.txt">Index for agents</a></div>
</footer>
</div></body></html>