mirror of
https://github.com/hanzoai/skills.git
synced 2026-11-19 00:47:36 +00:00
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.
752 lines
33 KiB
HTML
752 lines
33 KiB
HTML
<!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:
|
||
"""Flow network representation"""
|
||
|
||
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):
|
||
"""Add directed edge with capacity"""
|
||
self.capacity[u][v] += capacity
|
||
|
||
def get_residual_capacity(self, u: int, v: int) -> float:
|
||
"""Get residual capacity: capacity - flow"""
|
||
return self.capacity[u][v] - self.flow[u][v]
|
||
|
||
def get_neighbors(self, u: int) -> List[int]:
|
||
"""Get all neighbors (forward and backward edges) in residual graph"""
|
||
neighbors = set()
|
||
|
||
# Forward edges with residual capacity
|
||
for v in self.capacity[u]:
|
||
if self.get_residual_capacity(u, v) > 0:
|
||
neighbors.add(v)
|
||
|
||
# Backward edges with flow (can push back)
|
||
for v in self.capacity:
|
||
if self.flow[v][u] > 0:
|
||
neighbors.add(v)
|
||
|
||
return list(neighbors)
|
||
|
||
def ford_fulkerson_dfs(network: FlowNetwork, source: int, sink: int
|
||
) -> Tuple[float, Dict[int, Dict[int, float]]]:
|
||
"""
|
||
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)
|
||
"""
|
||
max_flow = 0.0
|
||
|
||
def dfs_augment(u: int, min_capacity: float, visited: set) -> float:
|
||
"""DFS to find augmenting path, returns bottleneck capacity"""
|
||
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 > 0:
|
||
# Augment along this edge
|
||
bottleneck = dfs_augment(v, min(min_capacity, residual), visited)
|
||
|
||
if bottleneck > 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"Maximum flow: {max_flow}") # 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
|
||
) -> Tuple[float, Dict[int, Dict[int, float]]]:
|
||
"""
|
||
Edmonds-Karp maximum flow algorithm
|
||
|
||
Uses BFS to find shortest augmenting path in each iteration
|
||
|
||
Time: O(V × E²)
|
||
"""
|
||
max_flow = 0.0
|
||
|
||
def bfs_augment() -> Tuple[Optional[List[int]], float]:
|
||
"""
|
||
BFS to find shortest augmenting path
|
||
|
||
Returns: (path, bottleneck_capacity) or (None, 0)
|
||
"""
|
||
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) > 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"Maximum flow (Edmonds-Karp): {max_flow}") # 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
|
||
) -> Tuple[set, set, List[Tuple[int, int]], float]:
|
||
"""
|
||
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
|
||
"""
|
||
# 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) > 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"Max flow: {max_flow}") # 23.0
|
||
print(f"Min cut capacity: {cut_capacity}") # 23.0 (equal!)
|
||
print(f"Cut edges: {cut_edges}")
|
||
print(f"S = {S}, T = {T}")</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]]
|
||
) -> List[Tuple[int, int]]:
|
||
"""
|
||
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
|
||
"""
|
||
# 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"Maximum matching: {matching}") # 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:
|
||
"""Push-relabel maximum flow algorithm"""
|
||
|
||
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):
|
||
"""Push flow from u to v"""
|
||
# 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):
|
||
"""Increase height of vertex u"""
|
||
min_height = math.inf
|
||
|
||
for v in self.network.get_neighbors(u):
|
||
if self.network.get_residual_capacity(u, v) > 0:
|
||
min_height = min(min_height, self.height[v])
|
||
|
||
if min_height < math.inf:
|
||
self.height[u] = min_height + 1
|
||
|
||
def discharge(self, u: int):
|
||
"""Push all excess flow from u"""
|
||
while self.excess[u] > 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 > 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) -> float:
|
||
"""Compute maximum flow using push-relabel"""
|
||
# 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] > 0]
|
||
|
||
while work_list:
|
||
u = work_list.pop()
|
||
|
||
if self.excess[u] > 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] > 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) -> str:
|
||
"""Select optimal max flow algorithm"""
|
||
num_vertices = graph_info["num_vertices"]
|
||
num_edges = graph_info["num_edges"]
|
||
max_capacity = graph_info.get("max_capacity", math.inf)
|
||
|
||
if max_capacity < 100 and num_vertices < 1000:
|
||
return "Ford-Fulkerson (DFS)" # Simple, works for small capacities
|
||
|
||
if num_edges < num_vertices ** 1.5:
|
||
return "Edmonds-Karp" # Good for sparse graphs
|
||
|
||
return "Push-Relabel" # 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
|
||
) -> List[Tuple[List[int], float]]:
|
||
"""
|
||
Decompose flow into paths and cycles
|
||
|
||
Returns: List of (path, flow_amount) pairs
|
||
"""
|
||
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] > 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] > 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> |