-
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathgraph_test.go
111 lines (91 loc) · 3.17 KB
/
graph_test.go
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
package go_directed_acyclic_graph
import (
"fmt"
"math"
"testing"
"github.com/stretchr/testify/assert"
)
func TestNewGraph(t *testing.T) {
graph := newGraph()
assert.NotNil(t, graph, "graph should not be nil")
assert.Zero(t, graph.NodeCount(), "graph.NodeCount() should equal zero")
assert.Empty(t, graph.Nodes(), "graph.Nodes() should equal empty")
}
func TestGraphAddNode(t *testing.T) {
graph := newGraph()
graph.AddNode("A")
graph.AddNode("B")
graph.AddNode("C")
assert.Equal(t, 3, graph.NodeCount(), "graph.NodeCount() should equal 3")
assert.Equal(t, []interface{}{"A", "B", "C"}, graph.Nodes(), "graph.Nodes() should equal [A, B, C]")
}
func TestGraphAddNodeDuplicate(t *testing.T) {
graph := newGraph()
graph.AddNode("A")
graph.AddNode("B")
graph.AddNode("C")
graph.AddNode("A")
assert.Equal(t, 3, graph.NodeCount(), "graph.NodeCount() should equal 3")
assert.Equal(t, []interface{}{"A", "B", "C"}, graph.Nodes(), "graph.Nodes() should equal [A, B, C]")
}
func BenchmarkGraphAddNodes(b *testing.B) {
for i := 12.0; i <= 20; i++ {
count := int(math.Pow(2, i))
b.Run(fmt.Sprintf("%d", count), func(b *testing.B) {
graph := newGraph()
for i := 0; i < count; i++ {
graph.AddNode(i)
}
})
}
}
func TestGraphAddNodes(t *testing.T) {
graph := newGraph()
graph.AddNodes("A", "B", "C")
assert.Equal(t, 3, graph.NodeCount(), "graph.NodeCount() should equal 3")
assert.Equal(t, []interface{}{"A", "B", "C"}, graph.Nodes(), "graph.Nodes() should equal [A, B, C]")
}
func TestGraphRemoveNode(t *testing.T) {
graph := newGraph()
graph.AddNode("A")
graph.AddNode("B")
graph.AddNode("C")
graph.AddNode("D")
graph.RemoveNode("A")
graph.RemoveNode("C")
assert.Equal(t, 2, graph.NodeCount(), "graph.NodeCount() should equal 2")
assert.Equal(t, []interface{}{"B", "D"}, graph.Nodes(), "graph.Nodes() should equal [B, D]")
}
func TestGraphRemoveNodeMissing(t *testing.T) {
graph := newGraph()
graph.AddNode("A")
graph.AddNode("B")
graph.AddNode("C")
graph.AddNode("D")
graph.RemoveNode("A")
graph.RemoveNode("A")
graph.RemoveNode("E")
assert.Equal(t, 3, graph.NodeCount(), "graph.NodeCount() should equal 2")
assert.Equal(t, []interface{}{"B", "C", "D"}, graph.Nodes(), "graph.Nodes() should equal [B, C, D]")
}
func TestGraphRemoveNodes(t *testing.T) {
graph := newGraph()
graph.AddNode("A")
graph.AddNode("B")
graph.AddNode("C")
graph.AddNode("D")
graph.RemoveNodes("A", "C")
assert.Equal(t, 2, graph.NodeCount(), "graph.NodeCount() should equal 2")
assert.Equal(t, []interface{}{"B", "D"}, graph.Nodes(), "graph.Nodes() should equal [B, D]")
}
func TestGraphNodeExists(t *testing.T) {
graph := newGraph()
assert.False(t, graph.NodeExists("A"), "graph.NodeExists(\"A\") should equal false")
assert.False(t, graph.NodeExists("B"), "graph.NodeExists(\"B\") should equal false")
graph.AddNode("A")
assert.True(t, graph.NodeExists("A"), "graph.NodeExists(\"A\") should equal true")
assert.False(t, graph.NodeExists("B"), "graph.NodeExists(\"B\") should equal false")
graph.RemoveNode("A")
assert.False(t, graph.NodeExists("A"), "graph.NodeExists(\"A\") should equal false")
assert.False(t, graph.NodeExists("B"), "graph.NodeExists(\"B\") should equal false")
}