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
|
package graph
// MaxFlow computes a maximum flow from s to t in a graph
// with nonnegative edge capacities.
// The time complexity is O(|E|²⋅|V|), where |E| is the number of edges
// and |V| the number of vertices in the graph.
func MaxFlow(g Iterator, s, t int) (flow int64, graph Iterator) {
// Edmonds-Karp's algorithm
n := g.Order()
prev := make([]int, n)
residual := Copy(g)
for residualFlow(residual, s, t, prev) && flow < Max {
pathFlow := Max
for v := t; v != s; {
u := prev[v]
if c := residual.Cost(u, v); c < pathFlow {
pathFlow = c
}
v = u
}
flow += pathFlow
for v := t; v != s; {
u := prev[v]
residual.AddCost(u, v, residual.Cost(u, v)-pathFlow)
residual.AddCost(v, u, residual.Cost(v, u)+pathFlow)
v = u
}
}
res := New(n)
for v := 0; v < n; v++ {
g.Visit(v, func(w int, c int64) (skip bool) {
if flow := c - residual.Cost(v, w); flow > 0 {
res.AddCost(v, w, flow)
}
return
})
}
return flow, Sort(res)
}
func residualFlow(g *Mutable, s, t int, prev []int) bool {
visited := make([]bool, g.Order())
prev[s], visited[s] = -1, true
for queue := []int{s}; len(queue) > 0; {
v := queue[0]
queue = queue[1:]
g.Visit(v, func(w int, c int64) (skip bool) {
if !visited[w] && c > 0 {
prev[w] = v
visited[w] = true
queue = append(queue, w)
}
return
})
}
return visited[t]
}
|
