Network Flow

Network Flow

A Network is a set of connected nodes or vertices,
described as a Directed Graph

Network Flow problem is identifying the
maximum flow that a network can sustain

Cornerstone problem in area of optimization

Numerous Application areas:
Data Mining Project Selection
Stable Matching Bipartite Matching
Distributed Computing Airlines Scheduling
Image Segmentation Network Connectivity
Network Reliability Intrusion Detection
Flow Network
Basic Concept.

Abstraction for material flowing through the edges.

G = (V, E) = directed graph, no parallel edges.

Two distinguished nodes: s = source, t = sink.

c(e) = capacity of edge e.

9
2 5

10 15 10
15
4

5 8 10
source s 3 6 t sink

6 10
4 15
15

30
4 7
Cuts
Def. An s-t cut is a partition (A, B) of V with s  A and t  B.

Def. The capacity of a cut (A, B) is: cap( A, B)   c(e)

e out of A

Capacity = 10 + 5 + 15

= 30
9
2 5

10
15 10
15
4

5 8 10
s 3 6 t

A
6
4 15
15 10

30
4 7
Cuts
Def. An s-t cut is a partition (A, B) of V with s  A and t  B.

Def. The capacity of a cut (A, B) is: cap( A, B)   c(e)

e out of A

Capacity = 9 + 15 + 8 + 30
= 62
 9
2 5

10 10
15
15
4

5 8 10
s 3 6 t

A 15 6 10
4 15

30
4 7
Minimum Cut Problem
Min s-t cut problem. Find an s-t cut of minimum capacity.

Capacity = 10 + 8 + 10
= 28

9
2 5

10 15 10
15
4

5 8 10
s 3 6 t

4 15
A 6 10
15

30
4 7
Flows
Def. An s-t flow is a function that satisfies:

For each e  E: 0  f (e)  c(e) (capacity)

For each v  V – {s, t}:  f (e)   f (e) (conservation)
e in to v e out of v

 f is:
Def. The value of a flow v( f )   f (e) .
e out of s

0/9
2 5

4/10 0/15 0/10

4/4 0/15

0/5
4/8 4/10
s 3 6 t

0/6 0/10
0/10 0/4 0/15

Shown as
0/30
Flow/ capacity Value = 4
4 7
Flows
Def. An s-t flow is a function that satisfies:

For each e  E: 0  f (e)  c(e) (capacity)

For each v  V – {s, t}:  f (e)   f (e) (conservation)
e in to v e out of v

flow f is: v( f ) 
Def. The value of a   f (e) .
e out of s

6/9
2 5

10/10 0/15 6/10

4/4 0/15

3/5 8/8 8/10

s 3 6 t

1/6 10/10
0/4 0/15

11/15
11/30 Value = 24
4 7
Flows
Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then, the
net flow sent across the cut is equal to the amount leaving s.

 f (e)   f (e)  v( f )
e out of A e in to A

 6/9
2 5

10/10 6/10
0/15
4/4 0/15

3/5 8/8 8/10

s 3 6 t

A
1/6 10/10
0/4 0/15

11/15
11/30
Value = 24
4 7
Flows and Cuts
Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then, the
net flow sent across the cut is equal to the amount leaving s.

 f (e)   f (e)  v( f )
e out of A e in to A

 6/9
2 5

10/10 6/10
0/15
4/4 0/15

3/5 8/8 8/10

s 3 6 t

A
1/6 10/10
0/4 0/15

11/15
11/30 Value = 6 + 0 + 8 - 1 + 11
= 24
4 7
Flows and Cuts
Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then, the
net flow sent across the cut is equal to the amount leaving s.

 f (e)   f (e)  v( f )
e out of A e in to A

 6/9
2 5

10/10 6/10
0/15
4/4 0/15

3/5 8/8 8/10

s 3 6 t

A
1/6 10/10
0/4 0/15

11/15
11/30 Value = 10 - 4 + 8 - 0 + 10
= 24
4 7
Flows and Cuts
Duality Lemma. Let f be any flow, and let (A, B) be any cut.
If v(f) = cap(A, B), then f is a max flow and (A, B) is a min cut.

Value of flow = 28
Cut capacity = 28  Flow value  28

9/9
2 5

10/10 9/10
1/15
0/4 0/15

4/5 8/8 9/10

s 3 6 t

4/6 10/10
A 0/4 0/15

14/15
14/3
4 7
Max Flow Algorithm
Greedy algorithm.

Start with f(e) = 0 for all edge e  E.

Find an s-t path P where each edge has f(e) < c(e).

Augment flow along path P.

Repeat until you get stuck.

20 10

s 30 t

10 20
Flow value = 0
2
Max Flow Algorithm
Greedy algorithm.

Start with f(e) = 0 for all edge e  E.

Find an s-t path P where each edge has f(e) < c(e).

Augment flow along path P.

Repeat until you get stuck.
locally optimality  global optimality

20/20
10

s 20/30 t

10
20/20 Flow value = 20
2
Max Flow Algorithm
Greedy algorithm & Optimization.

Greedy Algorithm may not give the maximum flow

Different optimization techniques needed to achieve maximum

1 1

20/20 0/10 20/20 10/10

s t s t
20/30 10/30

0/10 10/10 20/20

20/20

2 2
greedy = 20 opt = 30
Residual Network
capacity
Original edge: e = (u, v)  E. flow
6/ 17

Flow f(e), capacity c(e). u v

Residual edge.

"Undo" flow sent. residual capacity

e = (u, v) and eR = (v, u). 11
u v

Residual capacity:
6
c(e)  f (e) if e  E residual capacity
c f (e)  
f (e) if e R  E

Residual graph: Gf = (V, Ef ).

 Residual edges with positive residual capacity.



Ef = {e : f(e) < c(e)}  {eR : c(e) > 0}.
Max Flow Min Cut Theorem
Max-flow min-cut theorem. The value of the
max flow in a network is equal to the value
of the min cut.
Proof strategy. We prove the above by showing the that the following
are equivalent:
(i) There exists a cut (A, B) such that the flow through the Cut
is equal to the Capacity of the Cut; v(f) = cap(A, B).
(ii) Flow f is a max flow.
(iii) There is no augmenting path relative to f in the residual
graph.

(i)  (ii) This was the duality lemma between flows and cuts.

(ii)  (iii) We show contrapositive.


Let f be a flow. If there exists an augmenting path, then we can
improve f by sending flow along path.
Max Flow Min Cut Theorem
Proof (Contd.)
(iii)  (i)

Let f be a flow with no augmenting paths.

Let A be set of vertices reachable from s in residual graph.

By definition of A, s  A.

By definition of f, t  A.
v( f )   f (e)   f (e)
e out of A e in to A
A B
  c(e)
e out of A t
 cap(A, B)



original network
Ford Fulkerson Algorithm
Input: Flow Network G (V,E), Source s, Sink t
Associated Structure: Residual Network Gf
Output: Maximum Flow from Source to Sink

Non Full Forward edge

Non Zero Backward edge
Procedure Ford-Fulkerson (G)
Begin
Repeat for all(u, v) in E
Set f[u, v] := 0
Set f[v, u] := 0
End Repeat
Repeat while there exists a path p from s to t in Gf
Set cf (p) := min {cf (u, v) | (u, v) is in p}
Repeat for all (u, v) in p
Set f[u, v] := f[u, v] + cf (p)
Set f[v, u] := -f[u, v]
End Repeat
End Repeat
End
Example

Procedure Ford-Fulkerson (G)

(residual) network Gf Begin
12 Repeat for all (u, v) in E
v1 v3 Set f[u,v]:= 0
20
16 Set f[v,u]:= 0
End Repeat
Repeat while there exists a path p
S t
6

7 from s to t in Gf
Set cf(p):= min {cf(u,v)|(u,v)in p}
9

Repeat for all (u,v) in p

13 4 Set f[u,v]:= f[u,v]+cf(p)
v2 v4
14 Set f[v,u]:= -f[u, v]
End Repeat
End Repeat
End
Example - 1

Procedure Ford-Fulkerson (G)

(residual) network Gf Begin
0/12 Repeat for all (u, v) in E
v1 v3 Set f[u,v]:= 0
6 0/
0/ 1 20 Set f[v,u]:= 0
End Repeat
0/6

Repeat while there exists a path p

S 0/7 t from s to t in Gf
9
0/

Set cf(p):= min {cf(u,v)|(u,v)in p}

4 Repeat for all (u,v) in p
0/ 1
3 0/ Set f[u,v]:= f[u,v]+cf(p)
v2 v4
0/14 Set f[v,u]:= -f[u, v]
End Repeat
End Repeat
End
Example - 2

Procedure Ford-Fulkerson (G)

(residual) network Gf Begin
12 Repeat for all (u, v) in E
v1 v3 Set f[u,v]:= 0
20
16 Set f[v,u]:= 0
End Repeat
Repeat while there exists a path p
S t
6

7 from s to t in Gf
Set cf(p):= min {cf(u,v)|(u,v)in p}
9

Repeat for all (u,v) in p

13 4 Set f[u,v]:= f[u,v]+cf(p)
v2 v4
14 Set f[v,u]:= -f[u, v]
End Repeat
End Repeat
End
Example - 3

Procedure Ford-Fulkerson (G)

(residual) network Gf Begin
12 Repeat for all (u, v) in E
v1 v3 Set f[u,v]:= 0
20
16 Set f[v,u]:= 0
End Repeat
Repeat while there exists a path p
S t
6

7 from s to t in Gf
Set cf(p):= min {cf(u,v)|(u,v)in p}
9

Repeat for all (u,v) in p

13 4 Set f[u,v]:= f[u,v]+cf(p)
v2 v4
14 Set f[v,u]:= -f[u, v]
End Repeat
End Repeat
End

temporary variable:
cf (p) = 12
Example - 4

Procedure Ford-Fulkerson (G)

(residual) network Gf Begin
12 Repeat for all (u, v) in E
v1 v3 Set f[u,v]:= 0
20
16 Set f[v,u]:= 0
End Repeat
Repeat while there exists a path p
S t
6

7 from s to t in Gf
Set cf(p):= min {cf(u,v)|(u,v)in p}
9

Repeat for all (u,v) in p

13 4 Set f[u,v]:= f[u,v]+cf(p)
v2 v4
14 Set f[v,u]:= -f[u, v]
End Repeat
End Repeat
flow network G End
v1
12/12 v3
16 12/
12/ 20 temporary variable:
cf (p) = 12
S t
6

7
9

13 4
v2 v4
14
Example - 5

Procedure Ford-Fulkerson (G)

(residual) network Gf Begin
12 Repeat for all (u, v) in E
v1 v3 Set f[u,v]:= 0
4 8
Set f[v,u]:= 0
12 End Repeat
12 Repeat while there exists a path p
S t
6

7 from s to t in Gf
Set cf(p):= min {cf(u,v)|(u,v)in p}
9

Repeat for all (u,v) in p

13 4 Set f[u,v]:= f[u,v]+cf(p)
v2 v4
14 Set f[v,u]:= -f[u, v]
End Repeat
End Repeat
flow network G End
v1
12/12 v3
16 12/
12/ 20

S t
6

7
9

13 4
v2 v4
14
Example - 6

Procedure Ford-Fulkerson (G)

(residual) network Gf Begin
12 Repeat for all (u, v) in E
v1 v3 Set f[u,v]:= 0
4 8
Set f[v,u]:= 0
12 End Repeat
12 Repeat while there exists a path p
S t
6

7 from s to t in Gf
Set cf(p):= min {cf(u,v)|(u,v)in p}
9

Repeat for all (u,v) in p

13 4 Set f[u,v]:= f[u,v]+cf(p)
v2 v4
14 Set f[v,u]:= -f[u, v]
End Repeat
End Repeat
flow network G End
v1
12/12 v3
16 12/
12/ 20

S t
6

7
9

13 4
v2 v4
14
Example - 7

Procedure Ford-Fulkerson (G)

(residual) network Gf Begin
12 Repeat for all (u, v) in E
v1 v3 Set f[u,v]:= 0
8
4 Set f[v,u]:= 0
12 End Repeat
12 Repeat while there exists a path p
S t
6

7 from s to t in Gf
Set cf(p):= min {cf(u,v)|(u,v)in p}
9

Repeat for all (u,v) in p

13 4 Set f[u,v]:= f[u,v]+cf(p)
v2 v4
14 Set f[v,u]:= -f[u, v]
End Repeat
End Repeat
flow network G End
v1
12/12 v3
16 12/
12/ 20

S t
6

7
9

13 4
v2 v4
14
Example - 8

Procedure Ford-Fulkerson (G)

(residual) network Gf Begin
12 Repeat for all (u, v) in E
v1 v3 Set f[u,v]:= 0
4 8
Set f[v,u]:= 0
12 End Repeat
12 Repeat while there exists a path p
S t
6

7 from s to t in Gf
Set cf(p):= min {cf(u,v)|(u,v)in p}
9

Repeat for all (u,v) in p

13 4 Set f[u,v]:= f[u,v]+cf(p)
v2 v4
14 Set f[v,u]:= -f[u, v]
End Repeat
End Repeat
flow network G End
v1
12/12 v3
16 12/
12/ 20 temporary variable:
cf (p) = 4
S t
6

7
9

13 4
v2 v4
14
Example - 9

Procedure Ford-Fulkerson (G)

(residual) network Gf Begin
12 Repeat for all (u, v) in E
v1 v3 Set f[u,v]:= 0
4 8
Set f[v,u]:= 0
12 End Repeat
12 Repeat while there exists a path p
S t
6

7 from s to t in Gf
Set cf(p):= min {cf(u,v)|(u,v)in p}
9

Repeat for all (u,v) in p

13 4 Set f[u,v]:= f[u,v]+cf(p)
v2 v4
14 Set f[v,u]:= -f[u, v]
End Repeat
End Repeat
flow network G End
v1
12/12 v3
16 12/
12/ 20 temporary variable:
cf (p) = 4
S t
6

7
9

4
4/1
3 4/
v2 v4
4/14
Example - 10

Procedure Ford-Fulkerson (G)

(residual) network Gf Begin
12 Repeat for all (u, v) in E
v1 v3 Set f[u,v]:= 0
4 8
Set f[v,u]:= 0
12 End Repeat
12 Repeat while there exists a path p
S t
6

7 from s to t in Gf
4 Set cf(p):= min {cf(u,v)|(u,v)in p}
9

Repeat for all (u,v) in p

9 4 4
v2 v4 Set f[u,v]:= f[u,v]+cf(p)
10 Set f[v,u]:= -f[u, v]
End Repeat
End Repeat
flow network G End
v1
12/12 v3
16 12/
12/ 20

S t
6

7
9

4
4/1
3 4/
v2 v4
4/14
Example - 11

Procedure Ford-Fulkerson (G)

(residual) network Gf Begin
12 Repeat for all (u, v) in E
v1 v3 Set f[u,v]:= 0
4 8
Set f[v,u]:= 0
12 End Repeat
12 Repeat while there exists a path p
S t
6

7 from s to t in Gf
4 Set cf(p):= min {cf(u,v)|(u,v)in p}
9

Repeat for all (u,v) in p

9 4 4
v2 v4 Set f[u,v]:= f[u,v]+cf(p)
10 Set f[v,u]:= -f[u, v]
End Repeat
End Repeat
flow network G End
v1
12/12 v3
16 12/
12/ 20

S t
6

7
9

4
4/1
3 4/
v2 v4
4/14
Example - 12

Procedure Ford-Fulkerson (G)

(residual) network Gf Begin
12 Repeat for all (u, v) in E
v1 v3 Set f[u,v]:= 0
4 8
Set f[v,u]:= 0
12 End Repeat
12 Repeat while there exists a path p
S t
6

7 from s to t in Gf
4 Set cf(p):= min {cf(u,v)|(u,v)in p}
9

Repeat for all (u,v) in p

9 4 4
v2 v4 Set f[u,v]:= f[u,v]+cf(p)
10 Set f[v,u]:= -f[u, v]
End Repeat
End Repeat
flow network G End
v1
12/12 v3
16 12/
12/ 20

S t
6

7
9

4
4/1
3 4/
v2 v4
4/14
Example - 13

Procedure Ford-Fulkerson (G)

(residual) network Gf Begin
12 Repeat for all (u, v) in E
v1 v3 Set f[u,v]:= 0
4 8
Set f[v,u]:= 0
12 End Repeat
12 Repeat while there exists a path p
S t
6

7 from s to t in Gf
4 Set cf(p):= min {cf(u,v)|(u,v)in p}
9

Repeat for all (u,v) in p

9 4 4
v2 v4 Set f[u,v]:= f[u,v]+cf(p)
10 Set f[v,u]:= -f[u, v]
End Repeat
End Repeat
flow network G End
v1
12/12 v3
16 12/
12/ 20 temporary variable:
cf (p) = 7
S t
6

7
9

4
4/1
3 4/
v2 v4
4/14
Example - 14

Procedure Ford-Fulkerson (G)

(residual) network Gf Begin
12 Repeat for all (u, v) in E
v1 v3 Set f[u,v]:= 0
4 8
Set f[v,u]:= 0
12 End Repeat
12 Repeat while there exists a path p
S t
6

7 from s to t in Gf
4 Set cf(p):= min {cf(u,v)|(u,v)in p}
9

Repeat for all (u,v) in p

9 4 4
v2 v4 Set f[u,v]:= f[u,v]+cf(p)
10 Set f[v,u]:= -f[u, v]
End Repeat
End Repeat
flow network G End
v1
12/12 v3
16 19/
12/ 20 temporary variable:
cf (p) = 7
7/7

S t
6

4
11 /1
3 4/
v2 v4
11/14
Example - 15

Procedure Ford-Fulkerson (G)

(residual) network Gf Begin
12 Repeat for all (u, v) in E
v1 v3 Set f[u,v]:= 0
4 1
Set f[v,u]:= 0
19 End Repeat
12 Repeat while there exists a path p
S t
6

7 from s to t in Gf
11 Set cf(p):= min {cf(u,v)|(u,v)in p}
9

Repeat for all (u,v) in p

2 11 4
v2 v4 Set f[u,v]:= f[u,v]+cf(p)
3 Set f[v,u]:= -f[u, v]
End Repeat
End Repeat
flow network G End
v1
12/12 v3
16 19/
12/ 20
No Forward Path available
7/7

S t
6

4
11 /1
3 4/
v2 v4
11/14
Example - 16

Procedure Ford-Fulkerson (G)

(residual) network Gf Begin
12 Repeat for all (u, v) in E
v1 v3 Set f[u,v]:= 0
4 1
Set f[v,u]:= 0
19 End Repeat
12 Repeat while there exists a path p
S t
6

7 from s to t in Gf
11 Set cf(p):= min {cf(u,v)|(u,v)in p}
9

Repeat for all (u,v) in p

2 11 4
v2 v4 Set f[u,v]:= f[u,v]+cf(p)
3 Set f[v,u]:= -f[u, v]
End Repeat
End Repeat
flow network G End
v1
12/12 v3
16 19/
12/ 20
Finally we have:
7/7

S t
| f | = f (s, t) = 12+4+7 = 23
6

4
11 / 1
3 4/
v2 v4
11/14
Example - 17

Procedure Ford-Fulkerson (G)

(residual) network Gf Begin
12 Repeat for all (u, v) in E
v1 v3 Set f[u,v]:= 0
4 1
Set f[v,u]:= 0
19 End Repeat
12 Repeat while there exists a path p
S t
6

7 from s to t in Gf
11 Set cf(p):= min {cf(u,v)|(u,v)in p}
9

Repeat for all (u,v) in p

2 11 4
v2 v4 Set f[u,v]:= f[u,v]+cf(p)
3 Set f[v,u]:= -f[u, v]
End Repeat
End Repeat
flow network G End
v1
12/12 v3
16 19/
12/ 20
B In the shaded area, we have:
7/7

S t
1. An s-t cut, (A, B), where
6

4 | f | = Cap(A, B) = 12+7+4 = 23
11 /1 4/
3 v2 v4 2. | f | = Max Flow = 23
11/14
Analysis of Algorithm

Procedure Ford-Fulkerson (G)

Begin
Repeat for all (u, v) in E
Set f[u,v]:= 0 O(|E|)
Set f[v,u]:= 0
End Repeat
Repeat while there exists a path p from s O(|E|)
to t in Gf
Set cf(p):= min {cf(u,v)|(u,v)in p}
Repeat for all (u,v) in p O(|E| |fmax|)
Set f[u,v]:= f[u,v]+cf(p) O(|E|)
Set f[v,u]:= -f[u, v]
End Repeat
End Repeat
End
running time: O ( |E| |fmax| )
with fmax as maximum flow

The augmenting path is chosen arbitrarily and all capacities are integers
Edmonds-Karp Enhancement
Edmonds-Karp Enhancement to
Ford-Fulkerson Algorithm:
(1) Each augmenting path is
4
found by Breadth-First Search v1 v3
6
(2) Each has to be a shortest-path 6

2
from s to t
S t

2
4 4
v2 v4
4

running time: O ( |V| |E|² )

The End