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
|
package build
import "strconv"
// Tensor returns the tensor product of g1 and g2:
// a graph whose vertices correspond to ordered pairs (v1, v2),
// where v1 and v2 are vertices in g1 and g2, respectively.
// The vertices (v1, v2) and (w1, w2) are connected by an edge whenever
// both of the edges {v1, w1} and {v2, w2} exist in the original graphs.
//
// In the new graph, vertex (v1, v2) gets index n⋅v1 + v2, where n = g2.Order(),
// and index i corresponds to the vertice (i/n, i%n).
func (g1 *Virtual) Tensor(g2 *Virtual) *Virtual {
m, n := g1.Order(), g2.Order()
switch {
case m < 0 || n < 0:
return nil
case m == 0 || n == 0:
return null
case m*n/m != n:
panic("too large m=" + strconv.Itoa(m) + " n=" + strconv.Itoa(n))
}
g := generic0(m*n, func(v, w int) (edge bool) {
v1, v2 := v/n, v%n
w1, w2 := w/n, w%n
return g1.Edge(v1, w1) && g2.Edge(v2, w2)
})
g.degree = func(v int) (deg int) {
v1, v2 := v/n, v%n
return g1.degree(v1) * g2.degree(v2)
}
g.visit = func(v int, a int, do func(w int, c int64) bool) (aborted bool) {
v1, v2 := v/n, v%n
a1, a2 := a/n, a%n
return g1.visit(v1, a1, func(w1 int, c int64) (skip bool) {
if w1 == a1 {
return g2.visit(v2, a2, func(w2 int, c int64) (skip bool) {
return do(n*w1+w2, 0)
})
}
return g2.visit(v2, 0, func(w2 int, c int64) (skip bool) {
return do(n*w1+w2, 0)
})
})
}
return g
}
|
