COMP251: Network flows (1)
Jérôme Waldispühl School of Computer Science
McGill University
Based on slides from M. Langer (McGill) & (Cormen et al., 2009)
Flow Network
G = (V, E) directed.
Each edge (u, v) has a capacity c(u, v) ≥ 0.
If (u,v) Ï E, then c(u,v) = 0.
Source vertex s, sink vertex t, assume s v t for all v ∈ V. 2
33
s132t 13
232
Definitions Positive flow: A function p : V × V → R satisfying.
Capacity constraint: For all u, v ∈ V, 0 ≤ p(u, v) ≤ c(u, v) 1/2
Positive flow
Capacity
Flow conservation: For all u ∈ V − {s, t}, 0/2 2/2
∑ p(v, u) = ∑ p(u, v)
v∈V
Flow into u
v∈V
Flow out of u
2/3
1/1 1/2
Flow in: 0 + 2 + 1 = 3 Flow out: 2 + 1 = 3
1/3
s
2/2
Example
2/2 1/1
2/3
0/1 1/3
2/3
1/2
t
2/3
1/2
Cancellation with positive flows
• Without loss of generality, can say positive flow goes either
from u to v or from v to u, but not both.
• In the above example, we can “cancel” 1 unit of flow in each
direction between x and z. 30
52
• Capacity constraint is still satisfied.
• Flow conservation is still satisfied.
Net flow
A function f : V × V ® R satisfying:
• Capacity constraint: For all u, v ∈ V, f (u, v) ≤ c(u, v) • Skewsymmetry:Forallu,v∈V,f(u,v)=−f(v,u)
• Flow conservation: For all u ∈ V − {s, t} ,
∑ f(v,u)= ∑ f(u,v)
v∈V;f (v,u)>0
Total positive flow entering u
v∈V;f (u,v)>0
∑f(u,v)=0 v∈V
Total positive flow leaving u
Positive vs. Net flows
Define net flow in terms of positive flow: f (u,v) = p(u,v) − p(v,u).
The differences between positive flow p and net flow f :
• p(u,v) ≥ 0,
• f satisfies skew symmetry.
Values of flows
Definition: f = |f| = ∑ f (s, v) = total flow out of source. v∈V
1/3 0/1
2/2
1/1 1/3 0/2 2/3
2/3
s
2/2
1/3
t
1/2
Value of flow f =|f|=3.
• • • •
Flow properties
Flow in == Flow out
Source s has outgoing flow
Sink t has ingoing flow
Flow out of source s == Flow in the sink t
2/2 1/3
2/3 1/2
s
0/1 1/3
1/1 1/3 0/2 2/3
t
2/2
Maximum-flow problem
Given G, s, t, and c, find a flow whose value is maximum.
2 33
s132t 13
232
Applications
(https://ais.web.cern.ch/ais/)
(http://driverlayer.com)
Naïve algorithm
Initialize f = 0
While true {
if(∃ pathPfromstotsuchthatall edges have a flow less than capacity)
then
increase flow on P up to max capacity
else
break }
Naïve algorithm
Initialize f = 0
While true {
if(∃ apathPfromstot s.t.all edgese ∈ Pf(e)
then {
put a backward edge (v,u) in Ef
with residual capacity cf(e) = f(e) }
}
Flow network
Example 1/3
Flow Residual graph
s s forward s backward 0/1 0/1 0/1 1/1 1 1
0/1 1/1 1
0/1 t 0/1 1/1 t 0/1 1 t 1
Flow network
Flow s
Residual graph
0/1
s 0/2
0/3
0/1
2/3
forward 1
s backward 2 3-2=1
2 2
t 1
Example 2/3
0/3 t 0/1
2/2
2/3 t 0/1 3-2=1
Example 3/3
0/2
s 0/4 t
0/2
0/3
0/2 0/2
0/3
0/3
0/2
s 3/4 t
0/2
3/3
3/3
0/3
Example 3/3
0/2
Flow s 3/4 t
0/2
0/2
3/3
3/3
0/3
0/2
Residual graph
0/3
s 0/3 t
0/1
0/2
0/2
0/3
0/3
Augmenting path
An augmenting path is a path from the source s to the sink t in the residual graph Gf that allows us to increase the flow.
2 23
s3t 1
3
Q: By how much can we increase the flow using this path?
3
2
Example
0/2 3/4
0/3
2 23
0/2
3/3
t
Flow in G
s
3/3
0/2
Residual s graph Gf
3
t
1
3
3
2
Residual graph Gf
Example
2 23
s3t 1
2
2 20
3
3
Flow in Gf
s2t 0
2
0
2
|f|=3
Example
0/2
Gs 3/4 t
0/2
3/3
|f|=5
3/3 0/3
2/2 2/2
2 20
s2t 0
2
3/3 2/3
3/3 2/2
0/2
s 1/4 t
Gf
0
2
β=2
Methodology
• ComputetheresidualgraphGf
• FindapathP
• AugmenttheflowfalongthepathP
1. Let β be the bottleneck (smallest residual capacity cf(e) of edges on P)
2. Add β to the flow f(e) on each edge of P.
Q: How do we add β into G?
Augmenting a path
f.augment(P) {
β = min { c(e)-f(e) | e ∈ P } foreach edgee=(u,v)∈P{
if e is a forward edge { f(e) += β
} else { // e is a backward edge f(e) -= β
} }
}
Ford-Fulkerson algorithm
f ¬0
Gf¬G
while (there is a s-t path in Gf) {
f.augment(P)
update Gf based on new f }
Correctness (termination)
Claim: The Ford-Fulkerson algorithm terminates. Proof:
• The capacities and flows are strictly positive integers.
• The sum of capacities leaving s is finite.
• Bottleneck values β are strictly positive integers.
• The flow increase by β after each iteration of the loop.
• The flow is an increasing sequence of integers that is bounded.
Complexity (Running time)
• Let
• Finding an augmenting path from s to t takes O(|E|) (e.g. BFS or DFS).
• The flow increases by at least 1 at each iteration of the main while loop.
• The algorithm runs in O(C · |E|)
C= ∑c(e)
e∈E outgoing
from s