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
|
// Copyright ©2019 The Gonum Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package graph_test
import (
"fmt"
"testing"
"golang.org/x/exp/rand"
"gonum.org/v1/gonum/graph"
"gonum.org/v1/gonum/graph/graphs/gen"
"gonum.org/v1/gonum/graph/iterator"
"gonum.org/v1/gonum/graph/simple"
)
var complementTests = []struct {
g graph.Graph
}{
{g: gnp(100, 0, rand.NewSource(1))},
{g: gnp(100, 0.05, rand.NewSource(1))},
{g: gnp(100, 0.5, rand.NewSource(1))},
{g: gnp(100, 0.95, rand.NewSource(1))},
{g: gnp(100, 1, rand.NewSource(1))},
}
func TestComplement(t *testing.T) {
for _, test := range complementTests {
n := len(graph.NodesOf(test.g.Nodes()))
wantM := n * (n - 1) // Double counting edges, but no self-loops.
var gotM int
iter := test.g.Nodes()
for iter.Next() {
id := iter.Node().ID()
to := test.g.From(id)
for to.Next() {
gotM++
}
toC := graph.Complement{test.g}.From(id)
for toC.Next() {
gotM++
}
}
if gotM != wantM {
t.Errorf("unexpected number of edges in sum of input and complement: got:%d want:%d", gotM, wantM)
}
}
}
func gnp(n int, p float64, src rand.Source) *simple.UndirectedGraph {
g := simple.NewUndirectedGraph()
err := gen.Gnp(g, n, p, src)
if err != nil {
panic(fmt.Sprintf("gnp: bad test: %v", err))
}
return g
}
var nodeFilterIteratorTests = []struct {
src, filter graph.Nodes
root int64
len int
}{
{src: iterator.NewOrderedNodes([]graph.Node{simple.Node(0)}), filter: graph.Empty, root: 0, len: 0},
{src: iterator.NewOrderedNodes([]graph.Node{simple.Node(0), simple.Node(1)}), filter: graph.Empty, root: 0, len: 1},
{src: iterator.NewOrderedNodes([]graph.Node{simple.Node(0), simple.Node(1), simple.Node(2)}), filter: iterator.NewOrderedNodes([]graph.Node{simple.Node(1)}), root: 0, len: 1},
}
func TestNodeFilterIterator(t *testing.T) {
for _, test := range nodeFilterIteratorTests {
it := graph.NewNodeFilterIterator(test.src, test.filter, test.root)
if it.Len() < 0 {
t.Logf("don't test indeterminate iterators: %T", it)
continue
}
for i := 0; i < 2; i++ {
n := it.Len()
if n != test.len {
t.Errorf("unexpected length of iterator construction/reset: got:%d want:%d", n, test.len)
}
for it.Next() {
n--
}
if n != 0 {
t.Errorf("unexpected remaining nodes after iterator completion: got:%d want:0", n)
}
it.Reset()
}
}
}
|
