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
|
package build
import "strconv"
// Kmn returns a virtual complete bipartite graph with m+n vertices.
// The vertices are divided into two subsets U = [0..m) and V = [m..m+n),
// and the edge set consists of all edges {u, v}, where u ∊ U and v ∊ V.
func Kmn(m, n int) *Virtual {
switch {
case m < 0 || n < 0:
return nil
case m == 0 && n == 0:
return null
case m == 0 && n == 1 || m == 1 && n == 0:
return singleton()
case m == 1 && n == 1:
return edge()
case m+n <= 0:
panic("too large m=" + strconv.Itoa(m) + " n=" + strconv.Itoa(n))
}
res := generic0(m+n, func(v, w int) bool {
return v < m && w >= m || v >= m && w < m
})
res.degree = func(v int) int {
if v < m {
return n
}
return m
}
res.visit = func(v int, a int, do func(w int, c int64) bool) (aborted bool) {
if v < m {
for w := max(a, m); w < m+n; w++ {
if do(w, 0) {
return true
}
}
return
}
for w := a; w < m; w++ {
if do(w, 0) {
return true
}
}
return
}
return res
}
|
