graph/topo: update for int64 IDs
Also rename CyclesIn to DirectedCyclesIn to allow for the undirected
case to be added.
MODIFY
graph/topo/bron_kerbosch.go
graph/topo/bron_kerbosch.go
@@ -23,10 +23,10 @@ func VertexOrdering(g graph.Undirected) (order []graph.Node, cores [][]graph.Nod
// Compute a number d_v for each vertex v in G,
// the number of neighbors of v that are not already in L.
// Initially, these numbers are just the degrees of the vertices.
- dv := make(map[int]int, len(nodes))
+ dv := make(map[int64]int, len(nodes))
var (
maxDegree int
- neighbours = make(map[int][]graph.Node)
+ neighbours = make(map[int64][]graph.Node)
)
for _, n := range nodes {
adj := g.From(n)
@@ -203,7 +203,7 @@ func (*bronKerbosch) choosePivotFrom(g graph.Undirected, p, x set.Nodes) (neighb
continue
}
for n := range nb {
- if _, ok := p[n]; ok {
+ if _, ok := p[int64(n)]; ok {
continue
}
c--

MODIFY
graph/topo/bron_kerbosch_test.go
graph/topo/bron_kerbosch_test.go
@@ -16,7 +16,7 @@ import (
var vOrderTests = []struct {
g []intset
- wantCore [][]int
+ wantCore [][]int64
wantK int
}{
{
@@ -29,7 +29,7 @@ var vOrderTests = []struct {
5: nil,
6: nil,
},
- wantCore: [][]int{
+ wantCore: [][]int64{
{},
{5},
{3},
@@ -39,7 +39,7 @@ var vOrderTests = []struct {
},
{
g: batageljZaversnikGraph,
- wantCore: [][]int{
+ wantCore: [][]int64{
{0},
{5, 9, 10, 16},
{1, 2, 3, 4, 11, 12, 13, 15},
@@ -67,12 +67,12 @@ func TestVertexOrdering(t *testing.T) {
}
var offset int
for k, want := range test.wantCore {
- sort.Ints(want)
- got := make([]int, len(want))
+ sort.Sort(ordered.Int64s(want))
+ got := make([]int64, len(want))
for j, n := range order[len(order)-len(want)-offset : len(order)-offset] {
got[j] = n.ID()
}
- sort.Ints(got)
+ sort.Sort(ordered.Int64s(got))
if !reflect.DeepEqual(got, want) {
t.Errorf("unexpected %d-core for test %d:\ngot: %v\nwant:%v", k, i, got, test.wantCore)
}
@@ -80,7 +80,7 @@ func TestVertexOrdering(t *testing.T) {
for j, n := range core[k] {
got[j] = n.ID()
}
- sort.Ints(got)
+ sort.Sort(ordered.Int64s(got))
if !reflect.DeepEqual(got, want) {
t.Errorf("unexpected %d-core for test %d:\ngot: %v\nwant:%v", k, i, got, test.wantCore)
}
@@ -91,7 +91,7 @@ func TestVertexOrdering(t *testing.T) {
var bronKerboschTests = []struct {
g []intset
- want [][]int
+ want [][]int64
}{
{
// This is the example given in the Bron-Kerbosch article on wikipedia (renumbered).
@@ -104,7 +104,7 @@ var bronKerboschTests = []struct {
4: nil,
5: nil,
},
- want: [][]int{
+ want: [][]int64{
{0, 1, 4},
{1, 2},
{2, 3},
@@ -114,7 +114,7 @@ var bronKerboschTests = []struct {
},
{
g: batageljZaversnikGraph,
- want: [][]int{
+ want: [][]int64{
{0},
{1, 2},
{1, 3},
@@ -147,13 +147,13 @@ func TestBronKerbosch(t *testing.T) {
}
}
cliques := BronKerbosch(g)
- got := make([][]int, len(cliques))
+ got := make([][]int64, len(cliques))
for j, c := range cliques {
- 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))

MODIFY
graph/topo/common_test.go
graph/topo/common_test.go
@@ -33,9 +33,9 @@ var batageljZaversnikGraph = []intset{
}
// intset is an integer set.
-type intset map[int]struct{}
+type intset map[int64]struct{}
-func linksTo(i ...int) intset {
+func linksTo(i ...int64) intset {
if len(i) == 0 {
return nil
}

MODIFY
graph/topo/johnson_cycles.go
graph/topo/johnson_cycles.go
@@ -28,8 +28,8 @@ type johnson struct {
result [][]graph.Node
}
-// CyclesIn returns the set of elementary cycles in the graph g.
-func CyclesIn(g graph.Directed) [][]graph.Node {
+// DirectedCyclesIn returns the set of elementary cycles in the graph g.
+func DirectedCyclesIn(g graph.Directed) [][]graph.Node {
jg := johnsonGraphFrom(g)
j := johnson{
adjacent: jg,
@@ -78,7 +78,7 @@ func (j *johnson) circuit(v int) bool {
//L1:
for w := range j.adjacent.succ[n.ID()] {
- w = j.adjacent.indexOf(w)
+ w := j.adjacent.indexOf(w)
if w == j.s {
// Output circuit composed of stack followed by s.
r := make([]graph.Node, len(j.stack)+1)
@@ -124,10 +124,10 @@ type johnsonGraph struct {
// look-up to into the non-sparse
// collection of potentially sparse IDs.
orig []graph.Node
- index map[int]int
+ index map[int64]int
- nodes set.Ints
- succ map[int]set.Ints
+ nodes set.Int64s
+ succ map[int64]set.Int64s
}
// johnsonGraphFrom returns a deep copy of the graph g.
@@ -136,16 +136,16 @@ func johnsonGraphFrom(g graph.Directed) johnsonGraph {
sort.Sort(ordered.ByID(nodes))
c := johnsonGraph{
orig: nodes,
- index: make(map[int]int, len(nodes)),
+ index: make(map[int64]int, len(nodes)),
- nodes: make(set.Ints, len(nodes)),
- succ: make(map[int]set.Ints),
+ nodes: make(set.Int64s, len(nodes)),
+ succ: make(map[int64]set.Int64s),
}
for i, u := range nodes {
c.index[u.ID()] = i
for _, v := range g.From(u) {
if c.succ[u.ID()] == nil {
- c.succ[u.ID()] = make(set.Ints)
+ c.succ[u.ID()] = make(set.Int64s)
c.nodes.Add(u.ID())
}
c.nodes.Add(v.ID())
@@ -159,7 +159,7 @@ func johnsonGraphFrom(g graph.Directed) johnsonGraph {
func (g johnsonGraph) order() int { return g.nodes.Count() }
// indexOf returns the index of the retained node for the given node ID.
-func (g johnsonGraph) indexOf(id int) int {
+func (g johnsonGraph) indexOf(id int64) int {
return g.index[id]
}
@@ -205,8 +205,8 @@ func (g johnsonGraph) sccSubGraph(sccs [][]graph.Node, min int) johnsonGraph {
sub := johnsonGraph{
orig: g.orig,
index: g.index,
- nodes: make(set.Ints),
- succ: make(map[int]set.Ints),
+ nodes: make(set.Int64s),
+ succ: make(map[int64]set.Int64s),
}
var n int
@@ -219,7 +219,7 @@ func (g johnsonGraph) sccSubGraph(sccs [][]graph.Node, min int) johnsonGraph {
for _, v := range scc {
if _, ok := g.succ[u.ID()][v.ID()]; ok {
if sub.succ[u.ID()] == nil {
- sub.succ[u.ID()] = make(set.Ints)
+ sub.succ[u.ID()] = make(set.Int64s)
sub.nodes.Add(u.ID())
}
sub.nodes.Add(v.ID())
@@ -275,6 +275,6 @@ func (johnsonGraph) To(graph.Node) []graph.Node {
panic("topo: unintended use of johnsonGraph")
}
-type johnsonGraphNode int
+type johnsonGraphNode int64
-func (n johnsonGraphNode) ID() int { return int(n) }
+func (n johnsonGraphNode) ID() int64 { return int64(n) }

MODIFY
graph/topo/johnson_cycles_test.go
graph/topo/johnson_cycles_test.go
@@ -16,7 +16,7 @@ import (
var cyclesInTests = []struct {
g []intset
- want [][]int
+ want [][]int64
}{
{
g: []intset{
@@ -28,7 +28,7 @@ var cyclesInTests = []struct {
6: linksTo(3, 5),
7: linksTo(0, 6),
},
- want: [][]int{
+ want: [][]int64{
{0, 1, 7, 0},
{2, 3, 4, 2},
{2, 6, 3, 4, 2},
@@ -41,7 +41,7 @@ var cyclesInTests = []struct {
2: linksTo(3),
3: linksTo(1),
},
- want: [][]int{
+ want: [][]int64{
{1, 2, 3, 1},
},
},
@@ -51,7 +51,7 @@ var cyclesInTests = []struct {
1: linksTo(0, 2),
2: linksTo(1),
},
- want: [][]int{
+ want: [][]int64{
{0, 1, 0},
{1, 2, 1},
},
@@ -76,14 +76,14 @@ var cyclesInTests = []struct {
3: linksTo(4),
4: linksTo(3),
},
- want: [][]int{
+ want: [][]int64{
{0, 1, 2, 0},
{3, 4, 3},
},
},
}
-func TestCyclesIn(t *testing.T) {
+func TestDirectedCyclesIn(t *testing.T) {
for i, test := range cyclesInTests {
g := simple.NewDirectedGraph(0, math.Inf(1))
g.AddNode(simple.Node(-10)) // Make sure we test graphs with sparse IDs.
@@ -96,15 +96,15 @@ func TestCyclesIn(t *testing.T) {
g.SetEdge(simple.Edge{F: simple.Node(u), T: simple.Node(v)})
}
}
- cycles := CyclesIn(g)
- var got [][]int
+ cycles := DirectedCyclesIn(g)
+ var got [][]int64
if cycles != nil {
- got = make([][]int, len(cycles))
+ got = make([][]int64, len(cycles))
}
// johnson.circuit does range iteration over maps,
// so sort to ensure consistent ordering.
for j, c := range cycles {
- ids := make([]int, len(c))
+ ids := make([]int64, len(c))
for k, n := range c {
ids[k] = n.ID()
}

MODIFY
graph/topo/tarjan.go
graph/topo/tarjan.go
@@ -119,9 +119,9 @@ func tarjanSCCstabilized(g graph.Directed, order func([]graph.Node)) [][]graph.N
t := tarjan{
succ: succ,
- indexTable: make(map[int]int, len(nodes)),
- lowLink: make(map[int]int, len(nodes)),
- onStack: make(set.Ints),
+ indexTable: make(map[int64]int, len(nodes)),
+ lowLink: make(map[int64]int, len(nodes)),
+ onStack: make(set.Int64s),
}
for _, v := range nodes {
if t.indexTable[v.ID()] == 0 {
@@ -140,9 +140,9 @@ type tarjan struct {
succ func(graph.Node) []graph.Node
index int
- indexTable map[int]int
- lowLink map[int]int
- onStack set.Ints
+ indexTable map[int64]int
+ lowLink map[int64]int
+ onStack set.Int64s
stack []graph.Node

MODIFY
graph/topo/tarjan_test.go
graph/topo/tarjan_test.go
@@ -21,7 +21,7 @@ var tarjanTests = []struct {
g []intset
ambiguousOrder []interval
- want [][]int
+ want [][]int64
sortedLength int
unorderableLength int
@@ -38,7 +38,7 @@ var tarjanTests = []struct {
7: linksTo(0, 6),
},
- want: [][]int{
+ want: [][]int64{
{5},
{2, 3, 4, 6},
{0, 1, 7},
@@ -56,7 +56,7 @@ var tarjanTests = []struct {
3: linksTo(1),
},
- want: [][]int{
+ want: [][]int64{
{1, 2, 3},
{0},
},
@@ -72,7 +72,7 @@ var tarjanTests = []struct {
2: linksTo(1),
},
- want: [][]int{
+ want: [][]int64{
{0, 1, 2},
},
@@ -97,7 +97,7 @@ var tarjanTests = []struct {
{0, 3}, // This includes node 6 since it only needs to be before 4 in topo sort.
{3, 5},
},
- want: [][]int{
+ want: [][]int64{
{6}, {5}, {4}, {3}, {2}, {1}, {0},
},
@@ -117,7 +117,7 @@ var tarjanTests = []struct {
ambiguousOrder: []interval{
{0, 2},
},
- want: [][]int{
+ want: [][]int64{
{0, 1, 2},
{3, 4},
},
@@ -174,13 +174,13 @@ func TestTarjanSCC(t *testing.T) {
gotSCCs := TarjanSCC(g)
// tarjan.strongconnect does range iteration over maps,
// so sort SCC members to ensure consistent ordering.
- gotIDs := make([][]int, len(gotSCCs))
+ gotIDs := make([][]int64, len(gotSCCs))
for i, scc := range gotSCCs {
- gotIDs[i] = make([]int, len(scc))
+ gotIDs[i] = make([]int64, len(scc))
for j, id := range scc {
gotIDs[i][j] = id.ID()
}
- sort.Ints(gotIDs[i])
+ sort.Sort(ordered.Int64s(gotIDs[i]))
}
for _, iv := range test.ambiguousOrder {
sort.Sort(ordered.BySliceValues(test.want[iv.start:iv.end]))

MODIFY
graph/topo/topo_test.go
graph/topo/topo_test.go
@@ -131,11 +131,11 @@ func TestPathExistsInDirected(t *testing.T) {
var connectedComponentTests = []struct {
g []intset
- 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},
@@ -159,13 +159,13 @@ func TestConnectedComponents(t *testing.T) {
}
}
cc := ConnectedComponents(g)
- 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/topo: update for int64 IDs

Also rename CyclesIn to DirectedCyclesIn to allow for the undirected
case to be added.