#13. Network Flow

#13.1 Concept

#What is a Flow Graph?

A flow graph is a directed, where each edge (also called an arc) has a certain capacity

#What is an Augmenting Path?

Augmenting path is a path of edges in the residual graph with remaining capacity greater than 0 from the source s to the destination t.

  • How to find the augmenting path is flexible in Ford-Fulkerson algorithm, there are multiple ways.
  • Every augmenting path has a bottle-neck, which is the smallest (capacity - flow) on the path.
    • In the above example, the bottle-neck is edge (3, 0)
  • Augmenting the flow means updating the flow values along the augmenting path.
    • For forward edge, increasing the flow by the bottle-neck value.
    • For backward edge, also called residual edge, decreasing the flow by the bottle-neck value
  • Residual edge exist to undo bad augmenting paths that do not lead to a maximum flow

#What is Residual Graph?

  • Think every edge in the original graph as also having a residual edge with a flow/capacity of 0/0
  • The resulting graph is a residual graph
    • Example of residual graph

#13.2 Ford-Fulkerson Algorithm

Algorithm

  • Keep finding augmenting path, then augments the flow until no more augmenting path from s to t
  • The sum of the bottle-necks found in each augmenting path is equal to the max flow.
  • The flow into the destination is also the max flow

Assuming the method of finding augmenting paths is by using DFS, then the Ford-Fulkerson algorithm runs in O(fE), where f is the maximum flow and E is the number of Edges.

1
Time Complexity: O(fE), where f is the maximum flow and E is the number of Edges.

There are other ways to find the augmenting path, Edmonds-Karp is the famous one.

Python Ford-Fulkerson Algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
import math
import flowgraph
# Problem: Ford-Fulkerson is used to find the maximum flow on a flow graph
# Performance: O(fE) time, where f is the maximum flow and E is the number of edges in the graph
# Notes:
# A flow graph is a `directed graph` with each edge has a flow and capacity.
def fordfulkerson(g):
"""
:type g: a FlowGraph
:rtype: int
"""
res = 0
flow = augmenting_path(g)
while flow != 0:
res += flow
flow = augmenting_path(g)
return res
def augmenting_path(g):
"""
:type g: a FlowGraph
:rtype: int
"""
visited = set()
return dfs(g, g.s, visited, math.inf)
def dfs(g, v, visited, flow):
"""
:type g: a FlowGraph
:type v: int
:type visited: set
:type flow: int
:rtype: int
"""
if v == g.t:
return flow
graph = g.graph
visited.add(v)
for adj in graph[v]:
if adj not in visited:
edge = graph[v][adj]
if edge.remaining_capacity() > 0:
bottleneck = dfs(g, adj, visited, min(flow, edge.remaining_capacity()))
if bottleneck > 0:
edge.augment(bottleneck)
return bottleneck
visited.remove(v)
return 0
def main():
n = 12
s, t = n - 2, n - 1
graph = flowgraph.FlowGraph(n, s, t)
print(graph.t)
# Set up edges from source
graph.add_edge(graph.s, 0, 10)
graph.add_edge(graph.s, 1, 5)
graph.add_edge(graph.s, 2, 10)
# Set up middle edges
graph.add_edge(0, 3, 10)
graph.add_edge(1, 2, 10)
graph.add_edge(2, 5, 15)
graph.add_edge(3, 1, 20)
graph.add_edge(3, 6, 15)
graph.add_edge(4, 1, 15)
graph.add_edge(4, 3, 3)
graph.add_edge(5, 4, 4)
graph.add_edge(5, 8, 10)
graph.add_edge(6, 7, 10)
graph.add_edge(7, 5, 7)
# Set up edges to destination
graph.add_edge(6, graph.t, 15)
graph.add_edge(8, graph.t, 10)
# Expected result of the above graph
expected_flow = 23
maxflow = fordfulkerson(graph)
print('expected result is %d, actual result is %d' % (expected_flow, maxflow))
main()

#13.3 Edmonds Karp Algorithm

  • Using BFS instead of DFS to find the augmenting path.
  • Takes O(VE^2 ) time, the difference is this time complexity no longer depends on the capacity value of any edge.
1
Time Complexity: O(VE^2 ), where V is the number of vertices and E is the number of Edges.

Python Ford-Fulkerson with Edmonds Karp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
import collections
import math
import flowgraph
# Problem: Ford-Fulkerson is used to find the maximum flow on a flow graph
# Performance: O(VE^2) time
def edmondskarp(g):
"""
:type g: a flow graph
:rtype: int
"""
res = 0
flow = augmenting_path(g)
while flow != 0:
res += flow
flow = augmenting_path(g)
return res
def augmenting_path(g):
"""
:type g: a flow graph
:rtype: int
"""
visited = set()
queue = collections.deque()
prev = {} # node -> edge poiting to it
queue.append(g.s)
visited.add(g.s)
while queue:
curr = queue.popleft()
if curr == g.t:
break
for adj in g.graph[curr]:
if adj not in visited:
edge = g.graph[curr][adj]
if edge.remaining_capacity() > 0:
queue.append(adj)
visited.add(adj)
prev[adj] = edge
if g.t not in prev:
return 0
bottleneck = math.inf
node = g.t
while node != g.s:
bottleneck = min(bottleneck, prev[node].remaining_capacity())
node = prev[node].s
node = g.t
while node != g.s:
prev[node].augment(bottleneck)
node = prev[node].s
return bottleneck
def main():
n = 12
s, t = n - 2, n - 1
graph = flowgraph.FlowGraph(n, s, t)
# Set up edges from source
graph.add_edge(graph.s, 0, 10)
graph.add_edge(graph.s, 1, 5)
graph.add_edge(graph.s, 2, 10)
# Set up middle edges
graph.add_edge(0, 3, 10)
graph.add_edge(1, 2, 10)
graph.add_edge(2, 5, 15)
graph.add_edge(3, 1, 20)
graph.add_edge(3, 6, 15)
graph.add_edge(4, 1, 15)
graph.add_edge(4, 3, 3)
graph.add_edge(5, 4, 4)
graph.add_edge(5, 8, 10)
graph.add_edge(6, 7, 10)
graph.add_edge(7, 5, 7)
# Set up edges to destination
graph.add_edge(6, graph.t, 15)
graph.add_edge(8, graph.t, 10)
# Expected result of the above graph
expected_flow = 23
maxflow = edmondskarp(graph)
print('expected result is %d, actual result is %d' % (expected_flow, maxflow))
main()

#13.4 Capacity Scaling

capacity scaling is another technique to use heuristic to efficiently find augmenting path.

  1. Find the largest capacity in the flow graph, call it U
  2. Find the delta, which is the largest 2^x that’s less or equal to U
  3. Find augmenting path with capacity > than delta
  4. If no more augmenting path has capacity greater than delta, then delta /= 2
  5. Repeat until delta <= 0
1
Time Complexity: O(log(U) * E^2), where U is the largest capacity in the flow graph.

#13.5 Dinic Algorithm

Another heuristic to efficiently find augmenting path. 太难了.

Comments

01/03/2020