-
Notifications
You must be signed in to change notification settings - Fork 13
/
dual_ascent.go
121 lines (114 loc) · 2.76 KB
/
dual_ascent.go
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
package dapcstp
// Implements the dual ascent algorithm from page 6. (Algorithm 1.)
// Puts each terminal into a priority queue with constant 1 priority.
func getInitialQueue(g *Graph) PriorityQueue {
pq := PriorityQueue{}
for i := 0; i < g.Nodes; i++ {
if g.Fixed[i] || g.Prize[i] > 0 {
pq.Push(&Item{value: i, priority: 1})
}
}
return pq
}
// Returns a slice of length g.Nodes. Its elements are 1 for vertices from which
// v is reachable on edges with cr = 0 and 0 otherwise.
func activeComponent(g *Graph, cr []Value, v int) []bool {
seen := make([]bool, g.Nodes)
seen[v] = true
pq := PriorityQueue{}
pq.Push(&Item{value: v})
for pq.Len() != 0 {
toExplore := pq.Pop().value
for _, uv := range g.Incoming[toExplore] {
if cr[uv] == 0 {
u := g.Src[uv]
if seen[u] == false {
pq.Push(&Item{value: u})
seen[u] = true
}
}
}
}
return seen
}
// Return the edges entering component.
func componentInArcs(g *Graph, component []bool) map[int]bool {
inArcs := make(map[int]bool)
for v := 0; v < g.Nodes; v++ {
if component[v] {
for _, ij := range g.Incoming[v] {
i := g.Src[ij]
if !component[i] {
inArcs[ij] = true
}
}
}
}
return inArcs
}
// Returns the minimum reduced cost among edges in componentInArcs.
func maxPossibleIncrease(g *Graph, cr []Value, componentInArcs map[int]bool) Value {
min := ValueMax
for arc := range componentInArcs {
if cr[arc] < min {
min = cr[arc]
}
}
return min
}
// Update the score of the chosen active terminal.
func updateActiveQueue(g *Graph, cr []Value, activeQueue *PriorityQueue, v int,
activeComponent []bool, feasiblePrimal []bool, inArcs map[int]bool) {
score := 0
size := 0
for i := 0; i < g.Nodes; i++ {
if activeComponent[i] {
score += len(g.Incoming[i])
size += 1
}
}
score -= (size - 1)
augmentation := 0
for arc := range inArcs {
if feasiblePrimal[arc] {
augmentation += 1
}
}
augmentation = (augmentation - 1) * g.Nodes
if augmentation > 0 {
score += augmentation
}
activeQueue.Push(&Item{value: int(v), priority: Value(score)})
return
}
func DualAscent(g *Graph, feasiblePrimal []bool) (lowerBound Value, cr []Value, pi []Value) {
lowerBound = 0
cr = make([]Value, g.Arcs)
copy(cr, g.Cost)
pi = make([]Value, g.Nodes)
copy(pi, g.Prize)
activeQueue := getInitialQueue(g)
for activeQueue.Len() > 0 {
k := activeQueue.Pop().value
w := activeComponent(g, cr, k)
if w[g.Root] {
continue
}
inArcs := componentInArcs(g, w)
delta := maxPossibleIncrease(g, cr, inArcs)
if !g.Fixed[k] {
if delta > pi[k] {
delta = pi[k]
}
pi[k] -= delta
}
for arc := range inArcs {
cr[arc] -= delta
}
if pi[k] != 0 {
updateActiveQueue(g, cr, &activeQueue, k, w, feasiblePrimal, inArcs)
}
lowerBound += delta
}
return
}