graph/network: update for int64 IDs
MODIFY
graph/network/betweenness.go
graph/network/betweenness.go
@@ -18,7 +18,7 @@ import (
//
// where \sigma_{st} and \sigma_{st}(v) are the number of shortest paths from s to t,
// and the subset of those paths containing v respectively.
-func Betweenness(g graph.Graph) map[int]float64 {
+func Betweenness(g graph.Graph) map[int64]float64 {
// Brandes' algorithm for finding betweenness centrality for nodes in
// and unweighted graph:
//
@@ -32,8 +32,8 @@ func Betweenness(g graph.Graph) map[int]float64 {
// Also note special case for sparse networks:
// http://wwwold.iit.cnr.it/staff/marco.pellegrini/papiri/asonam-final.pdf
- cb := make(map[int]float64)
- brandes(g, func(s graph.Node, stack linear.NodeStack, p map[int][]graph.Node, delta, sigma map[int]float64) {
+ cb := make(map[int64]float64)
+ brandes(g, func(s graph.Node, stack linear.NodeStack, p map[int64][]graph.Node, delta, sigma map[int64]float64) {
for stack.Len() != 0 {
w := stack.Pop()
for _, v := range p[w.ID()] {
@@ -59,15 +59,15 @@ func Betweenness(g graph.Graph) map[int]float64 {
//
// If g is undirected, edges are retained such that u.ID < v.ID where u and v are
// the nodes of e.
-func EdgeBetweenness(g graph.Graph) map[[2]int]float64 {
+func EdgeBetweenness(g graph.Graph) map[[2]int64]float64 {
// Modified from Brandes' original algorithm as described in Algorithm 7
// with the exception that node betweenness is not calculated:
//
// http://algo.uni-konstanz.de/publications/b-vspbc-08.pdf
_, isUndirected := g.(graph.Undirected)
- cb := make(map[[2]int]float64)
- brandes(g, func(s graph.Node, stack linear.NodeStack, p map[int][]graph.Node, delta, sigma map[int]float64) {
+ cb := make(map[[2]int64]float64)
+ brandes(g, func(s graph.Node, stack linear.NodeStack, p map[int64][]graph.Node, delta, sigma map[int64]float64) {
for stack.Len() != 0 {
w := stack.Pop()
for _, v := range p[w.ID()] {
@@ -77,7 +77,7 @@ func EdgeBetweenness(g graph.Graph) map[[2]int]float64 {
if isUndirected && wid < vid {
vid, wid = wid, vid
}
- cb[[2]int{vid, wid}] += c
+ cb[[2]int64{vid, wid}] += c
delta[v.ID()] += c
}
}
@@ -88,14 +88,14 @@ func EdgeBetweenness(g graph.Graph) map[[2]int]float64 {
// brandes is the common code for Betweenness and EdgeBetweenness. It corresponds
// to algorithm 1 in http://algo.uni-konstanz.de/publications/b-vspbc-08.pdf with
// the accumulation loop provided by the accumulate closure.
-func brandes(g graph.Graph, accumulate func(s graph.Node, stack linear.NodeStack, p map[int][]graph.Node, delta, sigma map[int]float64)) {
+func brandes(g graph.Graph, accumulate func(s graph.Node, stack linear.NodeStack, p map[int64][]graph.Node, delta, sigma map[int64]float64)) {
var (
nodes = g.Nodes()
stack linear.NodeStack
- p = make(map[int][]graph.Node, len(nodes))
- sigma = make(map[int]float64, len(nodes))
- d = make(map[int]int, len(nodes))
- delta = make(map[int]float64, len(nodes))
+ p = make(map[int64][]graph.Node, len(nodes))
+ sigma = make(map[int64]float64, len(nodes))
+ d = make(map[int64]int, len(nodes))
+ delta = make(map[int64]float64, len(nodes))
queue linear.NodeQueue
)
for _, s := range nodes {
@@ -152,8 +152,8 @@ type WeightedGraph interface {
//
// where \sigma_{st} and \sigma_{st}(v) are the number of shortest paths from s to t,
// and the subset of those paths containing v respectively.
-func BetweennessWeighted(g WeightedGraph, p path.AllShortest) map[int]float64 {
- cb := make(map[int]float64)
+func BetweennessWeighted(g WeightedGraph, p path.AllShortest) map[int64]float64 {
+ cb := make(map[int64]float64)
nodes := g.Nodes()
for i, s := range nodes {
@@ -203,8 +203,8 @@ func BetweennessWeighted(g WeightedGraph, p path.AllShortest) map[int]float64 {
//
// If g is undirected, edges are retained such that u.ID < v.ID where u and v are
// the nodes of e.
-func EdgeBetweennessWeighted(g WeightedGraph, p path.AllShortest) map[[2]int]float64 {
- cb := make(map[[2]int]float64)
+func EdgeBetweennessWeighted(g WeightedGraph, p path.AllShortest) map[[2]int64]float64 {
+ cb := make(map[[2]int64]float64)
_, isUndirected := g.(graph.Undirected)
nodes := g.Nodes()
@@ -231,7 +231,7 @@ func EdgeBetweennessWeighted(g WeightedGraph, p path.AllShortest) map[[2]int]flo
if isUndirected && vid < uid {
uid, vid = vid, uid
}
- cb[[2]int{uid, vid}]++
+ cb[[2]int64{uid, vid}]++
}
continue
}
@@ -246,7 +246,7 @@ func EdgeBetweennessWeighted(g WeightedGraph, p path.AllShortest) map[[2]int]flo
if isUndirected && vid < uid {
uid, vid = vid, uid
}
- cb[[2]int{uid, vid}] += stFrac
+ cb[[2]int64{uid, vid}] += stFrac
}
}
}

MODIFY
graph/network/betweenness_test.go
graph/network/betweenness_test.go
@@ -19,8 +19,8 @@ var betweennessTests = []struct {
g []set
wantTol float64
- want map[int]float64
- wantEdges map[[2]int]float64
+ want map[int64]float64
+ wantEdges map[[2]int64]float64
}{
{
// Example graph from http://en.wikipedia.org/wiki/File:PageRanks-Example.svg 16:17, 8 July 2009
@@ -39,12 +39,12 @@ var betweennessTests = []struct {
},
wantTol: 1e-1,
- want: map[int]float64{
+ want: map[int64]float64{
B: 32,
D: 18,
E: 48,
},
- wantEdges: map[[2]int]float64{
+ wantEdges: map[[2]int64]float64{
{A, D}: 20,
{B, C}: 20,
{B, D}: 16,
@@ -73,14 +73,14 @@ var betweennessTests = []struct {
},
wantTol: 1e-3,
- want: map[int]float64{
+ want: map[int64]float64{
A: 2,
B: 0.6667,
C: 0.6667,
D: 2,
E: 0.6667,
},
- wantEdges: map[[2]int]float64{
+ wantEdges: map[[2]int64]float64{
{A, B}: 2 + 2/3. + 4/2.,
{A, C}: 2 + 2/3. + 2/2.,
{A, E}: 2 + 2/3. + 2/2.,
@@ -98,10 +98,10 @@ var betweennessTests = []struct {
},
wantTol: 1e-3,
- want: map[int]float64{
+ want: map[int64]float64{
B: 2,
},
- wantEdges: map[[2]int]float64{
+ wantEdges: map[[2]int64]float64{
{A, B}: 4,
{B, C}: 4,
},
@@ -116,12 +116,12 @@ var betweennessTests = []struct {
},
wantTol: 1e-3,
- want: map[int]float64{
+ want: map[int64]float64{
B: 6,
C: 8,
D: 6,
},
- wantEdges: map[[2]int]float64{
+ wantEdges: map[[2]int64]float64{
{A, B}: 8,
{B, C}: 12,
{C, D}: 12,
@@ -138,10 +138,10 @@ var betweennessTests = []struct {
},
wantTol: 1e-3,
- want: map[int]float64{
+ want: map[int64]float64{
C: 12,
},
- wantEdges: map[[2]int]float64{
+ wantEdges: map[[2]int64]float64{
{A, C}: 8,
{B, C}: 8,
{C, D}: 8,
@@ -158,8 +158,8 @@ var betweennessTests = []struct {
},
wantTol: 1e-3,
- want: map[int]float64{},
- wantEdges: map[[2]int]float64{
+ want: map[int64]float64{},
+ wantEdges: map[[2]int64]float64{
{A, B}: 2,
{A, C}: 2,
{A, D}: 2,
@@ -190,8 +190,8 @@ func TestBetweenness(t *testing.T) {
got := Betweenness(g)
prec := 1 - int(math.Log10(test.wantTol))
for n := range test.g {
- wantN, gotOK := got[n]
- gotN, wantOK := test.want[n]
+ wantN, gotOK := got[int64(n)]
+ gotN, wantOK := test.want[int64(n)]
if gotOK != wantOK {
t.Errorf("unexpected betweenness result for test %d, node %c", i, n+'A')
}
@@ -222,8 +222,8 @@ func TestEdgeBetweenness(t *testing.T) {
outer:
for u := range test.g {
for v := range test.g {
- wantQ, gotOK := got[[2]int{u, v}]
- gotQ, wantOK := test.wantEdges[[2]int{u, v}]
+ wantQ, gotOK := got[[2]int64{int64(u), int64(v)}]
+ gotQ, wantOK := test.wantEdges[[2]int64{int64(u), int64(v)}]
if gotOK != wantOK {
t.Errorf("unexpected betweenness result for test %d, edge (%c,%c)", i, u+'A', v+'A')
}
@@ -259,8 +259,8 @@ func TestBetweennessWeighted(t *testing.T) {
got := BetweennessWeighted(g, p)
prec := 1 - int(math.Log10(test.wantTol))
for n := range test.g {
- gotN, gotOK := got[n]
- wantN, wantOK := test.want[n]
+ gotN, gotOK := got[int64(n)]
+ wantN, wantOK := test.want[int64(n)]
if gotOK != wantOK {
t.Errorf("unexpected betweenness existence for test %d, node %c", i, n+'A')
}
@@ -297,8 +297,8 @@ func TestEdgeBetweennessWeighted(t *testing.T) {
outer:
for u := range test.g {
for v := range test.g {
- wantQ, gotOK := got[[2]int{u, v}]
- gotQ, wantOK := test.wantEdges[[2]int{u, v}]
+ wantQ, gotOK := got[[2]int64{int64(u), int64(v)}]
+ gotQ, wantOK := test.wantEdges[[2]int64{int64(u), int64(v)}]
if gotOK != wantOK {
t.Errorf("unexpected betweenness result for test %d, edge (%c,%c)", i, u+'A', v+'A')
}
@@ -312,7 +312,7 @@ func TestEdgeBetweennessWeighted(t *testing.T) {
}
}
-func orderedPairFloats(w map[[2]int]float64, prec int) []pairKeyFloatVal {
+func orderedPairFloats(w map[[2]int64]float64, prec int) []pairKeyFloatVal {
o := make(orderedPairFloatsMap, 0, len(w))
for k, v := range w {
o = append(o, pairKeyFloatVal{prec: prec, key: k, val: v})
@@ -323,7 +323,7 @@ func orderedPairFloats(w map[[2]int]float64, prec int) []pairKeyFloatVal {
type pairKeyFloatVal struct {
prec int
- key [2]int
+ key [2]int64
val float64
}

MODIFY
graph/network/distance.go
graph/network/distance.go
@@ -18,9 +18,9 @@ import (
//
// For directed graphs the incoming paths are used. Infinite distances are
// not considered.
-func Closeness(g graph.Graph, p path.AllShortest) map[int]float64 {
+func Closeness(g graph.Graph, p path.AllShortest) map[int64]float64 {
nodes := g.Nodes()
- c := make(map[int]float64, len(nodes))
+ c := make(map[int64]float64, len(nodes))
for _, u := range nodes {
var sum float64
for _, v := range nodes {
@@ -45,9 +45,9 @@ func Closeness(g graph.Graph, p path.AllShortest) map[int]float64 {
//
// For directed graphs the incoming paths are used. Infinite distances are
// not considered.
-func Farness(g graph.Graph, p path.AllShortest) map[int]float64 {
+func Farness(g graph.Graph, p path.AllShortest) map[int64]float64 {
nodes := g.Nodes()
- f := make(map[int]float64, len(nodes))
+ f := make(map[int64]float64, len(nodes))
for _, u := range nodes {
var sum float64
for _, v := range nodes {
@@ -72,9 +72,9 @@ func Farness(g graph.Graph, p path.AllShortest) map[int]float64 {
//
// For directed graphs the incoming paths are used. Infinite distances are
// not considered.
-func Harmonic(g graph.Graph, p path.AllShortest) map[int]float64 {
+func Harmonic(g graph.Graph, p path.AllShortest) map[int64]float64 {
nodes := g.Nodes()
- h := make(map[int]float64, len(nodes))
+ h := make(map[int64]float64, len(nodes))
for i, u := range nodes {
var sum float64
for j, v := range nodes {
@@ -101,9 +101,9 @@ func Harmonic(g graph.Graph, p path.AllShortest) map[int]float64 {
//
// For directed graphs the incoming paths are used. Infinite distances are
// not considered.
-func Residual(g graph.Graph, p path.AllShortest) map[int]float64 {
+func Residual(g graph.Graph, p path.AllShortest) map[int64]float64 {
nodes := g.Nodes()
- r := make(map[int]float64, len(nodes))
+ r := make(map[int64]float64, len(nodes))
for i, u := range nodes {
var sum float64
for j, v := range nodes {

MODIFY
graph/network/distance_test.go
graph/network/distance_test.go
@@ -16,9 +16,9 @@ import (
var undirectedCentralityTests = []struct {
g []set
- farness map[int]float64
- harmonic map[int]float64
- residual map[int]float64
+ farness map[int64]float64
+ harmonic map[int64]float64
+ residual map[int64]float64
}{
{
g: []set{
@@ -27,17 +27,17 @@ var undirectedCentralityTests = []struct {
C: nil,
},
- farness: map[int]float64{
+ farness: map[int64]float64{
A: 1 + 2,
B: 1 + 1,
C: 2 + 1,
},
- harmonic: map[int]float64{
+ harmonic: map[int64]float64{
A: 1 + 1.0/2.0,
B: 1 + 1,
C: 1.0/2.0 + 1,
},
- residual: map[int]float64{
+ residual: map[int64]float64{
A: 1/math.Exp2(1) + 1/math.Exp2(2),
B: 1/math.Exp2(1) + 1/math.Exp2(1),
C: 1/math.Exp2(2) + 1/math.Exp2(1),
@@ -52,21 +52,21 @@ var undirectedCentralityTests = []struct {
E: nil,
},
- farness: map[int]float64{
+ farness: map[int64]float64{
A: 1 + 2 + 3 + 4,
B: 1 + 1 + 2 + 3,
C: 2 + 1 + 1 + 2,
D: 3 + 2 + 1 + 1,
E: 4 + 3 + 2 + 1,
},
- harmonic: map[int]float64{
+ harmonic: map[int64]float64{
A: 1 + 1.0/2.0 + 1.0/3.0 + 1.0/4.0,
B: 1 + 1 + 1.0/2.0 + 1.0/3.0,
C: 1.0/2.0 + 1 + 1 + 1.0/2.0,
D: 1.0/3.0 + 1.0/2.0 + 1 + 1,
E: 1.0/4.0 + 1.0/3.0 + 1.0/2.0 + 1,
},
- residual: map[int]float64{
+ residual: map[int64]float64{
A: 1/math.Exp2(1) + 1/math.Exp2(2) + 1/math.Exp2(3) + 1/math.Exp2(4),
B: 1/math.Exp2(1) + 1/math.Exp2(1) + 1/math.Exp2(2) + 1/math.Exp2(3),
C: 1/math.Exp2(2) + 1/math.Exp2(1) + 1/math.Exp2(1) + 1/math.Exp2(2),
@@ -83,21 +83,21 @@ var undirectedCentralityTests = []struct {
E: linksTo(C),
},
- farness: map[int]float64{
+ farness: map[int64]float64{
A: 2 + 2 + 1 + 2,
B: 2 + 1 + 2 + 2,
C: 1 + 1 + 1 + 1,
D: 2 + 1 + 2 + 2,
E: 2 + 2 + 1 + 2,
},
- harmonic: map[int]float64{
+ harmonic: map[int64]float64{
A: 1.0/2.0 + 1.0/2.0 + 1 + 1.0/2.0,
B: 1.0/2.0 + 1 + 1.0/2.0 + 1.0/2.0,
C: 1 + 1 + 1 + 1,
D: 1.0/2.0 + 1 + 1.0/2.0 + 1.0/2.0,
E: 1.0/2.0 + 1.0/2.0 + 1 + 1.0/2.0,
},
- residual: map[int]float64{
+ residual: map[int64]float64{
A: 1/math.Exp2(2) + 1/math.Exp2(2) + 1/math.Exp2(1) + 1/math.Exp2(2),
B: 1/math.Exp2(2) + 1/math.Exp2(1) + 1/math.Exp2(2) + 1/math.Exp2(2),
C: 1/math.Exp2(1) + 1/math.Exp2(1) + 1/math.Exp2(1) + 1/math.Exp2(1),
@@ -114,21 +114,21 @@ var undirectedCentralityTests = []struct {
E: nil,
},
- farness: map[int]float64{
+ farness: map[int64]float64{
A: 1 + 1 + 1 + 1,
B: 1 + 1 + 1 + 1,
C: 1 + 1 + 1 + 1,
D: 1 + 1 + 1 + 1,
E: 1 + 1 + 1 + 1,
},
- harmonic: map[int]float64{
+ harmonic: map[int64]float64{
A: 1 + 1 + 1 + 1,
B: 1 + 1 + 1 + 1,
C: 1 + 1 + 1 + 1,
D: 1 + 1 + 1 + 1,
E: 1 + 1 + 1 + 1,
},
- residual: map[int]float64{
+ residual: map[int64]float64{
A: 1/math.Exp2(1) + 1/math.Exp2(1) + 1/math.Exp2(1) + 1/math.Exp2(1),
B: 1/math.Exp2(1) + 1/math.Exp2(1) + 1/math.Exp2(1) + 1/math.Exp2(1),
C: 1/math.Exp2(1) + 1/math.Exp2(1) + 1/math.Exp2(1) + 1/math.Exp2(1),
@@ -159,12 +159,12 @@ func TestDistanceCentralityUndirected(t *testing.T) {
continue
}
- var got map[int]float64
+ var got map[int64]float64
got = Closeness(g, p)
for n := range test.g {
- if !floats.EqualWithinAbsOrRel(got[n], 1/test.farness[n], tol, tol) {
- want := make(map[int]float64)
+ if !floats.EqualWithinAbsOrRel(got[int64(n)], 1/test.farness[int64(n)], tol, tol) {
+ want := make(map[int64]float64)
for n, v := range test.farness {
want[n] = 1 / v
}
@@ -176,7 +176,7 @@ func TestDistanceCentralityUndirected(t *testing.T) {
got = Farness(g, p)
for n := range test.g {
- if !floats.EqualWithinAbsOrRel(got[n], test.farness[n], tol, tol) {
+ if !floats.EqualWithinAbsOrRel(got[int64(n)], test.farness[int64(n)], tol, tol) {
t.Errorf("unexpected farness for test %d:\ngot: %v\nwant:%v",
i, orderedFloats(got, prec), orderedFloats(test.farness, prec))
break
@@ -185,7 +185,7 @@ func TestDistanceCentralityUndirected(t *testing.T) {
got = Harmonic(g, p)
for n := range test.g {
- if !floats.EqualWithinAbsOrRel(got[n], test.harmonic[n], tol, tol) {
+ if !floats.EqualWithinAbsOrRel(got[int64(n)], test.harmonic[int64(n)], tol, tol) {
t.Errorf("unexpected harmonic centrality for test %d:\ngot: %v\nwant:%v",
i, orderedFloats(got, prec), orderedFloats(test.harmonic, prec))
break
@@ -194,7 +194,7 @@ func TestDistanceCentralityUndirected(t *testing.T) {
got = Residual(g, p)
for n := range test.g {
- if !floats.EqualWithinAbsOrRel(got[n], test.residual[n], tol, tol) {
+ if !floats.EqualWithinAbsOrRel(got[int64(n)], test.residual[int64(n)], tol, tol) {
t.Errorf("unexpected residual closeness for test %d:\ngot: %v\nwant:%v",
i, orderedFloats(got, prec), orderedFloats(test.residual, prec))
break
@@ -206,9 +206,9 @@ func TestDistanceCentralityUndirected(t *testing.T) {
var directedCentralityTests = []struct {
g []set
- farness map[int]float64
- harmonic map[int]float64
- residual map[int]float64
+ farness map[int64]float64
+ harmonic map[int64]float64
+ residual map[int64]float64
}{
{
g: []set{
@@ -217,17 +217,17 @@ var directedCentralityTests = []struct {
C: nil,
},
- farness: map[int]float64{
+ farness: map[int64]float64{
A: 0,
B: 1,
C: 2 + 1,
},
- harmonic: map[int]float64{
+ harmonic: map[int64]float64{
A: 0,
B: 1,
C: 1.0/2.0 + 1,
},
- residual: map[int]float64{
+ residual: map[int64]float64{
A: 0,
B: 1 / math.Exp2(1),
C: 1/math.Exp2(2) + 1/math.Exp2(1),
@@ -242,21 +242,21 @@ var directedCentralityTests = []struct {
E: nil,
},
- farness: map[int]float64{
+ farness: map[int64]float64{
A: 0,
B: 1,
C: 2 + 1,
D: 3 + 2 + 1,
E: 4 + 3 + 2 + 1,
},
- harmonic: map[int]float64{
+ harmonic: map[int64]float64{
A: 0,
B: 1,
C: 1.0/2.0 + 1,
D: 1.0/3.0 + 1.0/2.0 + 1,
E: 1.0/4.0 + 1.0/3.0 + 1.0/2.0 + 1,
},
- residual: map[int]float64{
+ residual: map[int64]float64{
A: 0,
B: 1 / math.Exp2(1),
C: 1/math.Exp2(2) + 1/math.Exp2(1),
@@ -273,21 +273,21 @@ var directedCentralityTests = []struct {
E: linksTo(C),
},
- farness: map[int]float64{
+ farness: map[int64]float64{
A: 0,
B: 0,
C: 1 + 1 + 1 + 1,
D: 0,
E: 0,
},
- harmonic: map[int]float64{
+ harmonic: map[int64]float64{
A: 0,
B: 0,
C: 1 + 1 + 1 + 1,
D: 0,
E: 0,
},
- residual: map[int]float64{
+ residual: map[int64]float64{
A: 0,
B: 0,
C: 1/math.Exp2(1) + 1/math.Exp2(1) + 1/math.Exp2(1) + 1/math.Exp2(1),
@@ -304,21 +304,21 @@ var directedCentralityTests = []struct {
E: nil,
},
- farness: map[int]float64{
+ farness: map[int64]float64{
A: 0,
B: 1,
C: 1 + 1,
D: 1 + 1 + 1,
E: 1 + 1 + 1 + 1,
},
- harmonic: map[int]float64{
+ harmonic: map[int64]float64{
A: 0,
B: 1,
C: 1 + 1,
D: 1 + 1 + 1,
E: 1 + 1 + 1 + 1,
},
- residual: map[int]float64{
+ residual: map[int64]float64{
A: 0,
B: 1 / math.Exp2(1),
C: 1/math.Exp2(1) + 1/math.Exp2(1),
@@ -349,14 +349,14 @@ func TestDistanceCentralityDirected(t *testing.T) {
continue
}
- var got map[int]float64
+ var got map[int64]float64
got = Closeness(g, p)
for n := range test.g {
- if !floats.EqualWithinAbsOrRel(got[n], 1/test.farness[n], tol, tol) {
- want := make(map[int]float64)
+ if !floats.EqualWithinAbsOrRel(got[int64(n)], 1/test.farness[int64(n)], tol, tol) {
+ want := make(map[int64]float64)
for n, v := range test.farness {
- want[n] = 1 / v
+ want[int64(n)] = 1 / v
}
t.Errorf("unexpected closeness centrality for test %d:\ngot: %v\nwant:%v",
i, orderedFloats(got, prec), orderedFloats(want, prec))
@@ -366,7 +366,7 @@ func TestDistanceCentralityDirected(t *testing.T) {
got = Farness(g, p)
for n := range test.g {
- if !floats.EqualWithinAbsOrRel(got[n], test.farness[n], tol, tol) {
+ if !floats.EqualWithinAbsOrRel(got[int64(n)], test.farness[int64(n)], tol, tol) {
t.Errorf("unexpected farness for test %d:\ngot: %v\nwant:%v",
i, orderedFloats(got, prec), orderedFloats(test.farness, prec))
break
@@ -375,7 +375,7 @@ func TestDistanceCentralityDirected(t *testing.T) {
got = Harmonic(g, p)
for n := range test.g {
- if !floats.EqualWithinAbsOrRel(got[n], test.harmonic[n], tol, tol) {
+ if !floats.EqualWithinAbsOrRel(got[int64(n)], test.harmonic[int64(n)], tol, tol) {
t.Errorf("unexpected harmonic centrality for test %d:\ngot: %v\nwant:%v",
i, orderedFloats(got, prec), orderedFloats(test.harmonic, prec))
break
@@ -384,7 +384,7 @@ func TestDistanceCentralityDirected(t *testing.T) {
got = Residual(g, p)
for n := range test.g {
- if !floats.EqualWithinAbsOrRel(got[n], test.residual[n], tol, tol) {
+ if !floats.EqualWithinAbsOrRel(got[int64(n)], test.residual[int64(n)], tol, tol) {
t.Errorf("unexpected residual closeness for test %d:\ngot: %v\nwant:%v",
i, orderedFloats(got, prec), orderedFloats(test.residual, prec))
break

MODIFY
graph/network/hits.go
graph/network/hits.go
@@ -21,11 +21,11 @@ type HubAuthority struct {
// nodes of the directed graph g. HITS terminates when the 2-norm of the
// vector difference between iterations is below tol. The returned map is
// keyed on the graph node IDs.
-func HITS(g graph.Directed, tol float64) map[int]HubAuthority {
+func HITS(g graph.Directed, tol float64) map[int64]HubAuthority {
nodes := g.Nodes()
// Make a topological copy of g with dense node IDs.
- indexOf := make(map[int]int, len(nodes))
+ indexOf := make(map[int64]int, len(nodes))
for i, n := range nodes {
indexOf[n.ID()] = i
}
@@ -92,7 +92,7 @@ func HITS(g graph.Directed, tol float64) map[int]HubAuthority {
}
}
- hubAuth := make(map[int]HubAuthority, len(nodes))
+ hubAuth := make(map[int64]HubAuthority, len(nodes))
for i, n := range nodes {
hubAuth[n.ID()] = HubAuthority{Hub: hub[i], Authority: auth[i]}
}

MODIFY
graph/network/hits_test.go
graph/network/hits_test.go
@@ -19,7 +19,7 @@ var hitsTests = []struct {
tol float64
wantTol float64
- want map[int]HubAuthority
+ want map[int64]HubAuthority
}{
{
// Example graph from http://www.cis.hut.fi/Opinnot/T-61.6020/2008/pagerank_hits.pdf page 8.
@@ -32,7 +32,7 @@ var hitsTests = []struct {
tol: 1e-4,
wantTol: 1e-4,
- want: map[int]HubAuthority{
+ want: map[int64]HubAuthority{
A: {Hub: 0.7887, Authority: 0},
B: {Hub: 0.5774, Authority: 0.4597},
C: {Hub: 0.2113, Authority: 0.6280},
@@ -56,12 +56,12 @@ func TestHITS(t *testing.T) {
got := HITS(g, test.tol)
prec := 1 - int(math.Log10(test.wantTol))
for n := range test.g {
- if !floats.EqualWithinAbsOrRel(got[n].Hub, test.want[n].Hub, test.wantTol, test.wantTol) {
+ if !floats.EqualWithinAbsOrRel(got[int64(n)].Hub, test.want[int64(n)].Hub, test.wantTol, test.wantTol) {
t.Errorf("unexpected HITS result for test %d:\ngot: %v\nwant:%v",
i, orderedHubAuth(got, prec), orderedHubAuth(test.want, prec))
break
}
- if !floats.EqualWithinAbsOrRel(got[n].Authority, test.want[n].Authority, test.wantTol, test.wantTol) {
+ if !floats.EqualWithinAbsOrRel(got[int64(n)].Authority, test.want[int64(n)].Authority, test.wantTol, test.wantTol) {
t.Errorf("unexpected HITS result for test %d:\ngot: %v\nwant:%v",
i, orderedHubAuth(got, prec), orderedHubAuth(test.want, prec))
break
@@ -70,7 +70,7 @@ func TestHITS(t *testing.T) {
}
}
-func orderedHubAuth(w map[int]HubAuthority, prec int) []keyHubAuthVal {
+func orderedHubAuth(w map[int64]HubAuthority, prec int) []keyHubAuthVal {
o := make(orderedHubAuthMap, 0, len(w))
for k, v := range w {
o = append(o, keyHubAuthVal{prec: prec, key: k, val: v})
@@ -81,7 +81,7 @@ func orderedHubAuth(w map[int]HubAuthority, prec int) []keyHubAuthVal {
type keyHubAuthVal struct {
prec int
- key int
+ key int64
val HubAuthority
}

MODIFY
graph/network/network_test.go
graph/network/network_test.go
@@ -19,9 +19,9 @@ const (
)
// set is an integer set.
-type set map[int]struct{}
+type set map[int64]struct{}
-func linksTo(i ...int) set {
+func linksTo(i ...int64) set {
if len(i) == 0 {
return nil
}

MODIFY
graph/network/page.go
graph/network/page.go
@@ -17,7 +17,7 @@ import (
// using the given damping factor and terminating when the 2-norm of the
// vector difference between iterations is below tol. The returned map is
// keyed on the graph node IDs.
-func PageRank(g graph.Directed, damp, tol float64) map[int]float64 {
+func PageRank(g graph.Directed, damp, tol float64) map[int64]float64 {
// PageRank is implemented according to "How Google Finds Your Needle
// in the Web's Haystack".
//
@@ -26,7 +26,7 @@ func PageRank(g graph.Directed, damp, tol float64) map[int]float64 {
// http://www.ams.org/samplings/feature-column/fcarc-pagerank
nodes := g.Nodes()
- indexOf := make(map[int]int, len(nodes))
+ indexOf := make(map[int64]int, len(nodes))
for i, n := range nodes {
indexOf[n.ID()] = i
}
@@ -78,7 +78,7 @@ func PageRank(g graph.Directed, damp, tol float64) map[int]float64 {
}
}
- ranks := make(map[int]float64, len(nodes))
+ ranks := make(map[int64]float64, len(nodes))
for i, r := range v.RawVector().Data {
ranks[nodes[i].ID()] = r
}
@@ -90,7 +90,7 @@ func PageRank(g graph.Directed, damp, tol float64) map[int]float64 {
// graph g using the given damping factor and terminating when the 2-norm of the
// vector difference between iterations is below tol. The returned map is
// keyed on the graph node IDs.
-func PageRankSparse(g graph.Directed, damp, tol float64) map[int]float64 {
+func PageRankSparse(g graph.Directed, damp, tol float64) map[int64]float64 {
// PageRankSparse is implemented according to "How Google Finds Your Needle
// in the Web's Haystack".
//
@@ -99,7 +99,7 @@ func PageRankSparse(g graph.Directed, damp, tol float64) map[int]float64 {
// http://www.ams.org/samplings/feature-column/fcarc-pagerank
nodes := g.Nodes()
- indexOf := make(map[int]int, len(nodes))
+ indexOf := make(map[int64]int, len(nodes))
for i, n := range nodes {
indexOf[n.ID()] = i
}
@@ -151,7 +151,7 @@ func PageRankSparse(g graph.Directed, damp, tol float64) map[int]float64 {
}
}
- ranks := make(map[int]float64, len(nodes))
+ ranks := make(map[int64]float64, len(nodes))
for i, r := range v.RawVector().Data {
ranks[nodes[i].ID()] = r
}

MODIFY
graph/network/page_test.go
graph/network/page_test.go
@@ -20,7 +20,7 @@ var pageRankTests = []struct {
tol float64
wantTol float64
- want map[int]float64
+ want map[int64]float64
}{
{
// Example graph from http://en.wikipedia.org/wiki/File:PageRanks-Example.svg 16:17, 8 July 2009
@@ -41,7 +41,7 @@ var pageRankTests = []struct {
tol: 1e-8,
wantTol: 1e-8,
- want: map[int]float64{
+ want: map[int64]float64{
A: 0.03278149,
B: 0.38440095,
C: 0.34291029,
@@ -69,7 +69,7 @@ var pageRankTests = []struct {
tol: 1e-3,
wantTol: 1e-3,
- want: map[int]float64{
+ want: map[int64]float64{
A: 0.250,
B: 0.140,
C: 0.140,
@@ -94,7 +94,7 @@ func TestPageRank(t *testing.T) {
got := PageRank(g, test.damp, test.tol)
prec := 1 - int(math.Log10(test.wantTol))
for n := range test.g {
- if !floats.EqualWithinAbsOrRel(got[n], test.want[n], test.wantTol, test.wantTol) {
+ if !floats.EqualWithinAbsOrRel(got[int64(n)], test.want[int64(n)], test.wantTol, test.wantTol) {
t.Errorf("unexpected PageRank result for test %d:\ngot: %v\nwant:%v",
i, orderedFloats(got, prec), orderedFloats(test.want, prec))
break
@@ -118,7 +118,7 @@ func TestPageRankSparse(t *testing.T) {
got := PageRankSparse(g, test.damp, test.tol)
prec := 1 - int(math.Log10(test.wantTol))
for n := range test.g {
- if !floats.EqualWithinAbsOrRel(got[n], test.want[n], test.wantTol, test.wantTol) {
+ if !floats.EqualWithinAbsOrRel(got[int64(n)], test.want[int64(n)], test.wantTol, test.wantTol) {
t.Errorf("unexpected PageRank result for test %d:\ngot: %v\nwant:%v",
i, orderedFloats(got, prec), orderedFloats(test.want, prec))
break
@@ -127,7 +127,7 @@ func TestPageRankSparse(t *testing.T) {
}
}
-func orderedFloats(w map[int]float64, prec int) []keyFloatVal {
+func orderedFloats(w map[int64]float64, prec int) []keyFloatVal {
o := make(orderedFloatsMap, 0, len(w))
for k, v := range w {
o = append(o, keyFloatVal{prec: prec, key: k, val: v})
@@ -138,7 +138,7 @@ func orderedFloats(w map[int]float64, prec int) []keyFloatVal {
type keyFloatVal struct {
prec int
- key int
+ key int64
val float64
}

graph/network: update for int64 IDs