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
|
package build
// Connect connects g1 and g2 by making v1 in g1 a common vertex
// with 0 in g2. The vertices in g2 are renumbered: 0 becomes v1
// in the new graph; and w, with w > 0, becomes w + g1.Order() - 1.
//
func (g1 *Virtual) Connect(v1 int, g2 *Virtual) *Virtual {
if g1.order == 0 || g2.order == 0 || v1 < 0 || v1 >= g1.order {
return nil
}
n := g1.order + g2.order - 1
t := g1.order - 1 // transpose
if n == 1 {
return singleton()
}
newCost := func(v, w int) int64 {
switch {
case v <= t && w <= t:
return g1.cost(v, w)
case v > t && w > t:
return g2.cost(v-t, w-t)
case v == v1:
return g2.cost(0, w-t)
case w == v1:
return g2.cost(v-t, 0)
default:
return 0
}
}
res := generic(n, newCost, func(v, w int) bool {
switch {
case v <= t && w <= t:
return g1.edge(v, w)
case v > t && w > t:
return g2.edge(v-t, w-t)
case v == v1:
return g2.edge(0, w-t)
case w == v1:
return g2.edge(v-t, 0)
default:
return false
}
})
res.degree = func(v int) (deg int) {
switch {
case v == v1:
return g1.degree(v) + g2.degree(0)
case v <= t:
return g1.degree(v)
default:
return g2.degree(v - t)
}
}
res.visit = func(v int, a int, do func(w int, c int64) bool) (aborted bool) {
switch {
case v > t:
return g2.visit(v-t, max(0, a-t), func(w int, c int64) (skip bool) {
if w == 0 {
return v1 >= a && do(v1, c)
}
return do(w+t, c)
})
case g1.visit(v, a, do):
return true
case v == v1:
return g2.visit(0, max(0, a-t), func(w int, c int64) (skip bool) {
return do(w+t, c)
})
default:
return
}
}
return res
}
|
