Network Flow
David Weir (U of Sussex) Program Analysis Term 1, 2015 559 / 606
Network Flow Problem
18 v5 14
v2
26 12 25
16
s35v4 t
v7
26
28 15
32 30 22
v1
v6
source
19 v3 25
flow
sink
David Weir (U of Sussex)
Program Analysis
Term 1, 2015 560 / 606
Network Flow Problem
18 v5 14
v2
15 16
s35v4 t
v7
26 15 12 25
32
26
1028 15214 6 30
v1 4 4 v6 19 v3 25
flow
22
source
sink
David Weir (U of Sussex)
Program Analysis
Term 1, 2015 561 / 606
Setting up the Problem
Let G = (V,E) be a directed graph
Edge flow:
Flow is associated with each edge in E Amount of flow over edge e ∈ E written as f (e)
Edge capacity:
Each edge e ∈ E as a flow capacity c(e) Flow for edge cannot exceed this capacity
f(e) ≤ c(e) for all e ∈ E We will assume that c(e) is an integer
David Weir (U of Sussex) Program Analysis Term 1, 2015 562 / 606
Setting up the Problem
Edges in and out of a node:
out(v) = {e | e = (v,u) for some u ∈ V } in(v) = {e | e = (u,v) for some u ∈ V }
Sink and source
Goal is to maximise flow from the source to the sink No edges into source, i.e.: in(s) = {}
No edges out of sink, i.e.: out(t) = {}
Conservation of flow:
For each node v, total flow into v equals total flow out of v
f(e) = f(e) e ∈ in(v) e ∈ out(v)
David Weir (U of Sussex) Program Analysis
Term 1, 2015
563 / 606
Setting up the Problem
Flow of a network:
Flow is conserved at each node in the network
Therefore the flow out of the source equals the flow into the sink This is the flow of the network
v(f) = f(e) e ∈ out(s)
We want to maximise v(f)
= f(e) e ∈ in(t)
David Weir (U of Sussex) Program Analysis
Term 1, 2015 564 / 606
Simple Example
100
v3
50
70
s v2 t 45
50
100 25
v1
David Weir (U of Sussex) Program Analysis
Term 1, 2015
565 / 606
Simple Example
100
v3
50
70
100
s v2 t 45
50
100 25
v1
David Weir (U of Sussex) Program Analysis
Term 1, 2015
566 / 606
Simple Example
v3
100
100
40
50
70
60
s v2 t 45
50
100 25
v1
David Weir (U of Sussex) Program Analysis
Term 1, 2015
567 / 606
Simple Example
v3
100
100
40
50
70
60
40
s v2 t 45
50
100 25
v1
David Weir (U of Sussex) Program Analysis
Term 1, 2015
568 / 606
Simple Example
v3
100
100
40
50
70
60
40
s v2 t 45
100
50
v1
25
30
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
569 / 606
Simple Example
v3
100
100
40
50
70
60
40
s v2 t 45
100
5 50 v1
25
30
25
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
570 / 606
Simple Example
v3
100
100
40
50
70
60
45
s v2 t 45
100
5 50 v1
25
30
25
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
571 / 606
Untapped Capacity
Looking for improved flow:
Total flow achieved is 130
Network can support a flow of 140
Push 10 more units of flow along the path (s, v1, v2, v3, t) Redirecting 10 units of flow from (v3, v2) to (v3, t)
Potential for redirection of flow captured in the residual graph
David Weir (U of Sussex) Program Analysis Term 1, 2015 572 / 606
Residual Graphs
100/100
v3
40/50
60/70
s v2 t 45/45
30/100
70
5/50
v1
25/25
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
573 / 606
Residual Graphs
v3
100/100
10
60/70
10
40/50
s v2 t 45/45
30/100
70
45
5/50
25/25
v1
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
574 / 606
Residual Graphs
100
v3
60 10
10
40
s v2 t 45
70
45 5
v1
25
30
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
575 / 606
Residual Graphs
100
v3
60 10
10
40
s v2 t 45
70
45 5
v1
25
30
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
576 / 606
Residual Graphs
Residual Graphs:
Given some directed graph G = (V,E) and some flow f for G The residual graph of G and f will be denoted by Gf
Forward and backwards edges:
Forward edges show additional flow capacity of edge — solid lines
Backward edges show capacity to re-direct flow — dashed lines
— reverse direction of edge original graph
Residual capacity: capacity of an edge in the residual graph
David Weir (U of Sussex) Program Analysis Term 1, 2015 577 / 606
Residual Graph Definition
Suppose we have the following:
A graph G = (V,E) with edge capacities given by c Aflowf forG
Residual graph Gf is defined as follows:
V is the set of vertices in Gf ife=(u,v)isinE andf(e)
include edge (v,u) in Gf with capacity f(e) (v,u) is marked as a backward edge
David Weir (U of Sussex) Program Analysis Term 1, 2015 578 / 606
Bottleneck Edges
Flow in residual graph:
Path from s to t represents route for augmenting the flow
Capacity of path determined by the path’s bottleneck edge
A path’s bottleneck edge is edge with lowest capacity
Flow of network can be augmented by capacity of bottleneck edge
David Weir (U of Sussex) Program Analysis Term 1, 2015 579 / 606
Augmenting Flow
100
v3
60
10
10
40
s v2 t 45
70
45 5 v1
25
30
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
580 / 606
Augmenting Flow
A possible augmentation:
We have identified a path from s to t in the residual graph
— path is (s,v1,v2,v3,t)
The bottleneck edge of this graph has residual capacity 10 We can add 10 units of additional flow to this network
Augmenting a flow using a path:
Increment flow of each forward edge on path by 10
— corresponds to adding new flow along an under-capacity edge
Decrement flow of edges in G that give rise to backward edge on path by 10
— corresponds to redirecting existing flow elsewhere
David Weir (U of Sussex) Program Analysis Term 1, 2015 581 / 606
Flow Augmentation General Case
Suppose we have each of the following:
A graph G = (V,E) with source s and sink t
A flow f on G and corresponding residual graph Gf
A simple path p in Gf from s to t with bottleneck edge having residual capacity x
augment(G, f , p, x ) is defined as:
for each edge (u, v) in the path p if (u, v) is a forward edge then
f(u,v) ← f(u,v) + x
if (u, v) is a backward edge then
f(v,u) ← f(v,u) − x return f
David Weir (U of Sussex) Program Analysis Term 1, 2015 582 / 606
Augmented Flow in Example
v3
100
100
40-10
50
70
60+10
45
s v2 t 45
30+10
100
25
5+10
50
25
v1
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
583 / 606
Augmented Flow in Example
v3
100
100
30
50
70
70
45
s v2 t 45
100
25
40
25
15
50
v1
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
584 / 606
Ford-Fulkerson Algorithm
MaximumFlow(G, s, t, c, ):
let f(e) = 0 for all e ∈ E
let Gf be the residual graph built from G and f whilethereisapathfromstot inGf
letpbeasimplepathfromstot inGf
let x be the residual capacity of the bottleneck edge of p f ← augment(G,f,p,x)
let Gf be the residual graph built from G and f
return f
David Weir (U of Sussex) Program Analysis Term 1, 2015 585 / 606
Implementing Ford-Fulkerson
Finding a s to t path in the residual graph:
Perform depth-first search from s
Takes O(n + m) time
O(m), since we assume all vertices have at least one incident edge
Iterations of while loop?
Flow is increases by at least one on every iteration — assumes edge capacities are integers
Flow is a measure of progress
Number of iterations bounded by upper bound on flow, C Overall running time is O(Cm)
David Weir (U of Sussex) Program Analysis Term 1, 2015 586 / 606
Upper bound on Network Flow
Upper bounds on flow through a network
Can’t exceed what the source can produce
v(f) ≤ c(e) e ∈ out(s)
Can’t exceed what the sink can accept
v(f) ≤ c(e) e ∈ in(t)
There is something more general that can be said
David Weir (U of Sussex) Program Analysis Term 1, 2015 587 / 606
Cuts in a Network
Let G = (V,E) be some network
(A, B) is a cut of the network if: s is in A
t is in B
A∪B=V andA∩B={}
In other words (A, B) is a partition of the set V
David Weir (U of Sussex) Program Analysis Term 1, 2015 588 / 606
Example Cut
20 60
s 80 t 30
David Weir (U of Sussex) Program Analysis Term 1, 2015 589 / 606
Cut Capacity
Let G = (V,E) be a network and (A,B) be a cut of G
The capacity of the cut (A, B), denoted c(A, B) is as follows:
c(A,B) = c(u,v)
(u,v) ∈ E u∈A v∈B
Cut capacity and network flow:
Many different possible cuts
The maximum flow is equal to minimum cut capacity
Captures what might be described as the network’s bottleneck
David Weir (U of Sussex) Program Analysis Term 1, 2015 590 / 606
Example Cut
20 60
s 80 t 30
Capacity of this cut is 20+80+30 = 130
David Weir (U of Sussex) Program Analysis Term 1, 2015 591 / 606
Correctness of Algorithm
The following propositions can be established:
Every cut provides an upper bound on the maximum possible flow The algorithm finds a flow that equals the capacity a particular cut The algorithm finds the maximum flow of the network
The algorithm finds the least capacity of any cut of the network
See textbook for details of the proofs
David Weir (U of Sussex) Program Analysis Term 1, 2015 592 / 606
Network Flow: Bipartite Matching
David Weir (U of Sussex) Program Analysis Term 1, 2015 593 / 606
Bipartite Graphs
A graph G = (V,E) is a bipartite graph if:
V can be partitioned into two sets V1 and V2
V = V1 ∪ V2 and V1 ∩ V2 = {} we can say that (V1, V2) is a partition of V
Everyedgee∈E hasoneendinV1 andoneendinV2
David Weir (U of Sussex) Program Analysis Term 1, 2015 594 / 606
Matching of Bipartite Graphs
M is a matching of a bipartite graph G = (V,E) if: M is a set of edges from E
M⊆E
Each vertex appears in at most one edge in M
if {u,v} ∈ M then there is no v′ ̸= v such that {u,v′} ∈ M
David Weir (U of Sussex) Program Analysis Term 1, 2015 595 / 606
Bipartite Matching Problem
Given a bipartite graph G = (V , E ) the bipartite matching problem is the problem of finding the largest possible matching M for G.
We will assume that the partition (V1, V2) is given
David Weir (U of Sussex) Program Analysis Term 1, 2015 596 / 606
Bipartite Matching Example
x1 x2 x3 x4 x5
y1 y2 y3 y4 y5
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
597 / 606
Bipartite Matching as Network Flow
Suppose G = (V,E) is a bipartite graph with partition (V1,V2) Construct weighted, directed G′ = (V′,E′) from G as follows:
Include two nodes additional nodes in G′ V′ =V∪{s,t}
Each edge in E placed in E′, directed edge from V1 to V2 Extra edges from s to each node in V1
Extra edges from each node in V2 to t
Every edge in E′ given capacity of 1
David Weir (U of Sussex) Program Analysis Term 1, 2015 598 / 606
Bipartite Matching as Network Flow
x1
x2 sx3 x4 x5
y1
y2 y3t y4
y5
David Weir (U of Sussex)
Program Analysis
Term 1, 2015 599 / 606
Maximum Flow is Largest Matching
Size of largest matching of G is equal to maximum flow of G′ Edges with non-zero flow make up the largest match
To justify this we make several observations
David Weir (U of Sussex) Program Analysis Term 1, 2015 600 / 606
All Matches are Flows
Observation: If M is a match then there is a flow k = |M|
Let all edges in match have flow of 1
Let edges from s to vertices involved in edges have flow of 1 Let edges to t from vertices involved in edges have flow of 1 By properties of matchings all flow is conserved
Total flow is |M|
David Weir (U of Sussex) Program Analysis Term 1, 2015 601 / 606
Integer Flows
Observation: Only need to consider flows that are integers
Given all edge capacities are integer
Ford-Fulkerson algorithm produces flows that are integers Ford-Fulkerson finds maximum flow
When edge capacities are all integers so is the maximum flow
Observation: Flow on each edge is either 0 or 1
David Weir (U of Sussex) Program Analysis Term 1, 2015 602 / 606
Matching Property
Observation: Only one edge in matching for any member of V1
Suppose v is in V1
Flow into v is at most 1
Flowoutofv isatmost1
Only one edge out v has non-zero flow
David Weir (U of Sussex) Program Analysis Term 1, 2015 603 / 606
Matching Property
Observation: Only one edge in matching for any member of V2
Suppose v is in V2
Flowoutofv isatmost1
Flow into v is at most 1
Only one edge into v has non-zero flow
David Weir (U of Sussex) Program Analysis Term 1, 2015 604 / 606
Maximum Flows are Matches
Observation: If there is a maximum flow k then there is a matching M with |M| = k
Suppose there is a maximum flow of k
Can assume all flows are integers
Every path from s to t includes exactly one edge from V1 to V2 k edges from V1 to V2 must have flow of 1
Let M be all such edges
From last 2 observations M is a matching
Size of matching M is k
David Weir (U of Sussex) Program Analysis Term 1, 2015 605 / 606
Running Time
The Ford-Fulkerson algorithm takes O(Cm) time C is upper bound on flow (source’s output) m is number of edges in network
In case of bipartite matching:
Upper bound on flow is the number of nodes n So running time is O(nm)
David Weir (U of Sussex) Program Analysis Term 1, 2015 606 / 606