graph/traverse: update for int64 IDs
MODIFY
graph/traverse/traverse.go
graph/traverse/traverse.go
@@ -16,7 +16,7 @@ type BreadthFirst struct {
EdgeFilter func(graph.Edge) bool
Visit func(u, v graph.Node)
queue linear.NodeQueue
- visited set.Ints
+ visited set.Int64s
}
// Walk performs a breadth-first traversal of the graph g starting from the given node,
@@ -26,7 +26,7 @@ type BreadthFirst struct {
// non-nil, it is called with the nodes joined by each followed edge.
func (b *BreadthFirst) Walk(g graph.Graph, from graph.Node, until func(n graph.Node, d int) bool) graph.Node {
if b.visited == nil {
- b.visited = make(set.Ints)
+ b.visited = make(set.Int64s)
}
b.queue.Enqueue(from)
b.visited.Add(from.ID())
@@ -106,7 +106,7 @@ type DepthFirst struct {
EdgeFilter func(graph.Edge) bool
Visit func(u, v graph.Node)
stack linear.NodeStack
- visited set.Ints
+ visited set.Int64s
}
// Walk performs a depth-first traversal of the graph g starting from the given node,
@@ -116,7 +116,7 @@ type DepthFirst struct {
// is called with the nodes joined by each followed edge.
func (d *DepthFirst) Walk(g graph.Graph, from graph.Node, until func(graph.Node) bool) graph.Node {
if d.visited == nil {
- d.visited = make(set.Ints)
+ d.visited = make(set.Int64s)
}
d.stack.Push(from)
d.visited.Add(from.ID())

MODIFY
graph/traverse/traverse_test.go
graph/traverse/traverse_test.go
@@ -64,13 +64,13 @@ var breadthFirstTests = []struct {
edge func(graph.Edge) bool
until func(graph.Node, int) bool
final map[graph.Node]bool
- want [][]int
+ want [][]int64
}{
{
g: wpBronKerboschGraph,
from: simple.Node(1),
final: map[graph.Node]bool{nil: true},
- want: [][]int{
+ want: [][]int64{
{1},
{0, 2, 4},
{3},
@@ -85,7 +85,7 @@ var breadthFirstTests = []struct {
},
from: simple.Node(1),
final: map[graph.Node]bool{nil: true},
- want: [][]int{
+ want: [][]int64{
{1},
{0, 2, 4},
{3},
@@ -96,7 +96,7 @@ var breadthFirstTests = []struct {
from: simple.Node(1),
until: func(n graph.Node, _ int) bool { return n == simple.Node(3) },
final: map[graph.Node]bool{simple.Node(3): true},
- want: [][]int{
+ want: [][]int64{
{1},
{0, 2, 4},
},
@@ -105,7 +105,7 @@ var breadthFirstTests = []struct {
g: batageljZaversnikGraph,
from: simple.Node(13),
final: map[graph.Node]bool{nil: true},
- want: [][]int{
+ want: [][]int64{
{13},
{14, 15},
{6, 7, 8, 16, 17},
@@ -124,7 +124,7 @@ var breadthFirstTests = []struct {
simple.Node(19): true,
simple.Node(20): true,
},
- want: [][]int{
+ want: [][]int64{
{13},
{14, 15},
{6, 7, 8, 16, 17},
@@ -147,13 +147,13 @@ func TestBreadthFirst(t *testing.T) {
w := BreadthFirst{
EdgeFilter: test.edge,
}
- var got [][]int
+ var got [][]int64
final := w.Walk(g, test.from, func(n graph.Node, d int) bool {
if test.until != nil && test.until(n, d) {
return true
}
if d >= len(got) {
- got = append(got, []int(nil))
+ got = append(got, []int64(nil))
}
got[d] = append(got[d], n.ID())
return false
@@ -162,7 +162,7 @@ func TestBreadthFirst(t *testing.T) {
t.Errorf("unexepected final node for test %d:\ngot: %v\nwant: %v", i, final, test.final)
}
for _, l := range got {
- sort.Ints(l)
+ sort.Sort(ordered.Int64s(l))
}
if !reflect.DeepEqual(got, test.want) {
t.Errorf("unexepected BFS level structure for test %d:\ngot: %v\nwant: %v", i, got, test.want)
@@ -176,13 +176,13 @@ var depthFirstTests = []struct {
edge func(graph.Edge) bool
until func(graph.Node) bool
final map[graph.Node]bool
- want []int
+ want []int64
}{
{
g: wpBronKerboschGraph,
from: simple.Node(1),
final: map[graph.Node]bool{nil: true},
- want: []int{0, 1, 2, 3, 4, 5},
+ want: []int64{0, 1, 2, 3, 4, 5},
},
{
g: wpBronKerboschGraph,
@@ -192,7 +192,7 @@ var depthFirstTests = []struct {
},
from: simple.Node(1),
final: map[graph.Node]bool{nil: true},
- want: []int{0, 1, 2, 3, 4},
+ want: []int64{0, 1, 2, 3, 4},
},
{
g: wpBronKerboschGraph,
@@ -204,19 +204,19 @@ var depthFirstTests = []struct {
g: batageljZaversnikGraph,
from: simple.Node(0),
final: map[graph.Node]bool{nil: true},
- want: []int{0},
+ want: []int64{0},
},
{
g: batageljZaversnikGraph,
from: simple.Node(3),
final: map[graph.Node]bool{nil: true},
- want: []int{1, 2, 3, 4, 5},
+ want: []int64{1, 2, 3, 4, 5},
},
{
g: batageljZaversnikGraph,
from: simple.Node(13),
final: map[graph.Node]bool{nil: true},
- want: []int{6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20},
+ want: []int64{6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20},
},
}
@@ -235,7 +235,7 @@ func TestDepthFirst(t *testing.T) {
w := DepthFirst{
EdgeFilter: test.edge,
}
- var got []int
+ var got []int64
final := w.Walk(g, test.from, func(n graph.Node) bool {
if test.until != nil && test.until(n) {
return true
@@ -246,7 +246,7 @@ func TestDepthFirst(t *testing.T) {
if !test.final[final] {
t.Errorf("unexepected final node for test %d:\ngot: %v\nwant: %v", i, final, test.final)
}
- sort.Ints(got)
+ sort.Sort(ordered.Int64s(got))
if test.want != nil && !reflect.DeepEqual(got, test.want) {
t.Errorf("unexepected DFS traversed nodes for test %d:\ngot: %v\nwant: %v", i, got, test.want)
}
@@ -256,11 +256,11 @@ func TestDepthFirst(t *testing.T) {
var walkAllTests = []struct {
g []intset
edge func(graph.Edge) bool
- want [][]int
+ want [][]int64
}{
{
g: batageljZaversnikGraph,
- want: [][]int{
+ want: [][]int64{
{0},
{1, 2, 3, 4, 5},
{6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20},
@@ -272,7 +272,7 @@ var walkAllTests = []struct {
// Do not traverse an edge between 3 and 5.
return (e.From().ID() != 4 || e.To().ID() != 5) && (e.From().ID() != 5 || e.To().ID() != 4)
},
- want: [][]int{
+ want: [][]int64{
{0},
{1, 2, 3, 4},
{5},
@@ -325,13 +325,13 @@ func TestWalkAll(t *testing.T) {
}
w.WalkAll(g, nil, after, during)
- got := make([][]int, len(cc))
+ got := make([][]int64, len(cc))
for j, c := range cc {
- ids := make([]int, len(c))
+ ids := make([]int64, len(c))
for k, n := range c {
ids[k] = n.ID()
}
- sort.Ints(ids)
+ sort.Sort(ordered.Int64s(ids))
got[j] = ids
}
sort.Sort(ordered.BySliceValues(got))

graph/traverse: update for int64 IDs