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
|
package build
import "sort"
// Circulant returns a virtual circulant graph with n vertices
// in which vertex i is adjacent to vertex (i + j) mod n and vertex (i - j) mod n
// for each j in the list s.
func Circulant(n int, s ...int) *Virtual {
switch {
case n < 0:
return nil
case n == 0:
return null
case n == 1:
return singleton()
}
s1 := make([]int, 0, 2*len(s))
for _, j := range s {
j %= n
if j < 0 {
j += n
}
s1 = append(s1, j)
s1 = append(s1, n-j)
}
sort.Ints(s1)
var t []int
prev := -1
for _, j := range s1 {
// Remove zeroes and duplicates.
if j == prev || j == 0 || j == n {
continue
}
prev = j
t = append(t, j)
}
deg := len(t)
switch {
case deg == 0:
return Empty(n)
case deg == 1 && t[0] == 1:
return Cycle(n)
case deg == n-1:
return Kn(n)
}
g := generic0(n, func(v, w int) (edge bool) {
d := v - w
if d < 0 {
d = -d
}
i := sort.SearchInts(t, d)
return i < deg && t[i] == d
})
g.degree = func(v int) int { return deg }
g.visit = func(v int, a int, do func(w int, c int64) bool) (aborted bool) {
start := sort.SearchInts(t, n-v+a)
for i := start; i < deg; i++ {
if do(v+t[i]-n, 0) {
return true
}
}
start = sort.SearchInts(t, a-v)
stop := sort.SearchInts(t, n-v)
for i := start; i < stop; i++ {
if do(v+t[i], 0) {
return true
}
}
return
}
return g
}
|
