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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
|
package main
import (
"testing"
)
type IntEdge struct {
source *IntNode
target *IntNode
length int
}
func (ie *IntEdge) Source() Node {
return ie.source
}
func (ie *IntEdge) Target() Node {
return ie.target
}
func (ie *IntEdge) Length() int {
return ie.length
}
func test_conversion() {
var _ Edge = &IntEdge{}
var _ Node = &IntNode{}
}
type IntNode struct {
Val int
edges []IntEdge
}
func (in *IntNode) Edges() []Edge {
var res []Edge
for i := range in.edges {
res = append(res, &in.edges[i])
}
return res
}
func (in *IntNode) Index() interface{} {
return in.Val
}
func NewIntNode(v int) *IntNode {
in := &IntNode{}
in.Val = v
return in
}
func TestBFS_Add(t *testing.T) {
bfs := NewBFS()
bfs.Add(NewIntNode(1), nil, 0)
if bfs.queue.Len() != 1 {
t.Fatalf("1 did not get put into the queue")
}
if val := bfs.queue.Front().Value.(*IntNode).Val; val != 1 {
t.Fatalf("the first entry is not 1: is %v", val)
}
if _, present := bfs.entries[1]; !present {
t.Fatalf("the entry 1 was not properly put into the entries set")
}
bfs.Add(NewIntNode(2), nil, 0)
if bfs.queue.Len() != 2 {
t.Fatalf("2 did not get put into the queue")
}
if bfs.queue.Front().Next().Value.(*IntNode).Val != 2 {
t.Fatalf("the second entry is not 2")
}
if _, present := bfs.entries[2]; !present {
t.Fatalf("the entry 2 was not properly put into the entries set")
}
// should be a no-op
bfs.Add(NewIntNode(1), nil, 0)
if bfs.queue.Len() != 2 {
t.Fatalf("1 was not properly ignored being added a second time")
}
}
func TestBFS_AddShorterDistance(t *testing.T) {
bfs := NewBFS()
node1 := NewIntNode(1)
node2 := NewIntNode(2)
bfs.Add(node1, nil, 5)
bfs.Add(node1, node2, 2)
if bfs.queue.Len() != 1 {
t.Fatalf("1 either wasn't in the queue or was added twice")
}
if bfs.entries[1].distance != 2 {
t.Fatalf("Distance to [1] was not properly updated")
}
if n, s, d := bfs.Next(); n.(*IntNode).Val != 1 || s.(*IntNode).Val != 2 ||
d != 2 {
t.Fatalf("Node or distance was not correct: %v %v %d", n, s, d)
}
}
func TestBFS_Next_simple(t *testing.T) {
bfs := NewBFS()
bfs.Add(NewIntNode(1), nil, 0)
bfs.Add(NewIntNode(2), nil, 0)
if bfs.queue.Len() != 2 || len(bfs.entries) != 2 {
t.Fatalf("1 and 2 were not properly added to the queue.")
}
if first, _, _ := bfs.Next(); first.(*IntNode).Val != 1 {
t.Fatalf("1 was not the first entry in the bfs")
}
if bfs.queue.Len() != 1 {
t.Fatalf("1 was not removed from the queue")
}
// We remember all entries we've walked, so we don't walk them a second time
if _, ok := bfs.entries[1]; !ok {
t.Fatalf("1 was removed from the entries list")
}
if second, _, _ := bfs.Next(); second.(*IntNode).Val != 2 {
t.Fatalf("2 was not the second entry in the bfs")
}
if last, _, _ := bfs.Next(); last != nil {
t.Fatalf("we didn't get nil when the queue was empty.")
}
}
func TestBFS_Next(t *testing.T) {
bfs := NewBFS()
node1 := NewIntNode(1)
node2 := NewIntNode(2)
node3 := NewIntNode(3)
node4 := NewIntNode(4)
edge12 := IntEdge{source: node1, target: node2, length: 1}
edge13 := IntEdge{source: node1, target: node3, length: 1}
edge24 := IntEdge{source: node2, target: node4, length: 1}
edge32 := IntEdge{source: node3, target: node2, length: 1}
node1.edges = append(node1.edges, edge12, edge13)
node2.edges = append(node2.edges, edge24)
node3.edges = append(node3.edges, edge32)
bfs.Add(node1, nil, 0)
if n, s, d := bfs.Next(); n.(*IntNode) != node1 || s != nil ||
d != 0 {
t.Fatalf("Next did not return first node and distance"+
", returned: %v, %d not %v, %d",
n, d, node1, 0)
}
if bfs.queue.Len() != 2 {
t.Fatalf("did not add new nodes to the queue")
}
if n, s, d := bfs.Next(); n.(*IntNode) != node2 || s.(*IntNode) != node1 ||
d != 1 {
t.Fatalf("expected the second node to be node2 (%v) not %v",
node2, n)
}
if n, s, d := bfs.Next(); n.(*IntNode) != node3 || s.(*IntNode) != node1 ||
d != 1 {
t.Fatalf("expected the third node to be node3 (%v) not %v",
node3, n)
}
if n, s, d := bfs.Next(); n.(*IntNode) != node4 || s.(*IntNode) != node2 ||
d != 2 {
t.Fatalf("expected the fourth node to be node4 (%v) not %v",
node4, n)
}
if n, s, d := bfs.Next(); n != nil || s != nil || d != 0 {
t.Fatalf("expected the final node to be nil not %v", n)
}
}
|