graph/internal/set: make Nodes creation a function
This allows us to alter the type that is returned and the
underlying implementation if necessary.
MODIFY
graph/community/k_communities.go
graph/community/k_communities.go
@@ -39,10 +39,10 @@ func KCliqueCommunities(k int, g graph.Undirected) [][]graph.Node {
// cliques smaller than k into separate
// single nodes.
var kcc [][]graph.Node
- single := make(set.Nodes)
- inCommunity := make(set.Nodes)
+ single := set.NewNodes()
+ inCommunity := set.NewNodes()
for _, c := range cc {
- nodes := make(set.Nodes, len(c))
+ nodes := set.NewNodesSize(len(c))
for _, cn := range c {
for _, n := range cn.(topo.Clique).Nodes() {
nodes.Add(n)

MODIFY
graph/graphs/gen/batagelj_brandes_test.go
graph/graphs/gen/batagelj_brandes_test.go
@@ -285,15 +285,15 @@ func TestBipartitePowerLawUndirected(t *testing.T) {
t.Errorf("unexpected number of nodes in p2: n=%d, d=%d: got:%d", n, d, len(p2))
}
- p1s := make(set.Nodes)
+ p1s := set.NewNodes()
for _, u := range p1 {
p1s.Add(u)
}
- p2s := make(set.Nodes)
+ p2s := set.NewNodes()
for _, u := range p2 {
p2s.Add(u)
}
- o := make(set.Nodes)
+ o := set.NewNodes()
if o.Intersect(p1s, p2s); len(o) != 0 {
t.Errorf("unexpected overlap in partition membership: n=%d, d=%d: got:%d", n, d, len(o))
}
@@ -334,15 +334,15 @@ func TestBipartitePowerLawDirected(t *testing.T) {
t.Errorf("unexpected number of nodes in p2: n=%d, d=%d: got:%d", n, d, len(p2))
}
- p1s := make(set.Nodes)
+ p1s := set.NewNodes()
for _, u := range p1 {
p1s.Add(u)
}
- p2s := make(set.Nodes)
+ p2s := set.NewNodes()
for _, u := range p2 {
p2s.Add(u)
}
- o := make(set.Nodes)
+ o := set.NewNodes()
if o.Intersect(p1s, p2s); len(o) != 0 {
t.Errorf("unexpected overlap in partition membership: n=%d, d=%d: got:%d", n, d, len(o))
}

MODIFY
graph/internal/set/set.go
graph/internal/set/set.go
@@ -103,6 +103,16 @@ func Int64sEqual(a, b Int64s) bool {
// Nodes is a set of nodes keyed in their integer identifiers.
type Nodes map[int64]graph.Node
+// NewNodes returns a new Nodes.
+func NewNodes() Nodes {
+ return make(Nodes)
+}
+
+// NewNodes returns a new Nodes with the given size hint, n.
+func NewNodesSize(n int) Nodes {
+ return make(Nodes, n)
+}
+
// The simple accessor methods for Nodes are provided to allow ease of
// implementation change should the need arise.

MODIFY
graph/internal/set/set_test.go
graph/internal/set/set_test.go
@@ -300,8 +300,8 @@ func TestEqualInts(t *testing.T) {
func TestSameNodes(t *testing.T) {
var (
- a = make(Nodes)
- b = make(Nodes)
+ a = NewNodes()
+ b = NewNodes()
c = a
)
@@ -324,7 +324,7 @@ func TestSameNodes(t *testing.T) {
}
func TestAddNodes(t *testing.T) {
- s := make(Nodes)
+ s := NewNodes()
if s == nil {
t.Fatal("Set cannot be created successfully")
}
@@ -369,7 +369,7 @@ func TestAddNodes(t *testing.T) {
}
func TestRemoveNodes(t *testing.T) {
- s := make(Nodes)
+ s := NewNodes()
s.Add(node(1))
s.Add(node(3))
@@ -403,7 +403,7 @@ func TestRemoveNodes(t *testing.T) {
}
func TestClearNodes(t *testing.T) {
- s := make(Nodes)
+ s := NewNodes()
s.Add(node(8))
s.Add(node(9))
@@ -417,7 +417,7 @@ func TestClearNodes(t *testing.T) {
}
func TestSelfEqualNodes(t *testing.T) {
- s := make(Nodes)
+ s := NewNodes()
if !Equal(s, s) {
t.Error("Set is not equal to itself")
@@ -431,8 +431,8 @@ func TestSelfEqualNodes(t *testing.T) {
}
func TestEqualNodes(t *testing.T) {
- a := make(Nodes)
- b := make(Nodes)
+ a := NewNodes()
+ b := NewNodes()
if !Equal(a, b) {
t.Error("Two different empty sets not equal")
@@ -456,8 +456,8 @@ func TestEqualNodes(t *testing.T) {
}
func TestCopyNodes(t *testing.T) {
- a := make(Nodes)
- b := make(Nodes)
+ a := NewNodes()
+ b := NewNodes()
a.Add(node(1))
a.Add(node(2))
@@ -483,7 +483,7 @@ func TestCopyNodes(t *testing.T) {
}
func TestSelfCopyNodes(t *testing.T) {
- a := make(Nodes)
+ a := NewNodes()
a.Add(node(1))
a.Add(node(2))
@@ -496,9 +496,9 @@ func TestSelfCopyNodes(t *testing.T) {
}
func TestUnionSameNodes(t *testing.T) {
- a := make(Nodes)
- b := make(Nodes)
- c := make(Nodes)
+ a := NewNodes()
+ b := NewNodes()
+ c := NewNodes()
a.Add(node(1))
a.Add(node(2))
@@ -526,9 +526,9 @@ func TestUnionSameNodes(t *testing.T) {
}
func TestUnionDiffNodes(t *testing.T) {
- a := make(Nodes)
- b := make(Nodes)
- c := make(Nodes)
+ a := NewNodes()
+ b := NewNodes()
+ c := NewNodes()
a.Add(node(1))
a.Add(node(2))
@@ -568,9 +568,9 @@ func TestUnionDiffNodes(t *testing.T) {
}
func TestUnionOverlappingNodes(t *testing.T) {
- a := make(Nodes)
- b := make(Nodes)
- c := make(Nodes)
+ a := NewNodes()
+ b := NewNodes()
+ c := NewNodes()
a.Add(node(1))
a.Add(node(2))
@@ -611,9 +611,9 @@ func TestUnionOverlappingNodes(t *testing.T) {
}
func TestIntersectSameNodes(t *testing.T) {
- a := make(Nodes)
- b := make(Nodes)
- c := make(Nodes)
+ a := NewNodes()
+ b := NewNodes()
+ c := NewNodes()
a.Add(node(2))
a.Add(node(3))
@@ -641,9 +641,9 @@ func TestIntersectSameNodes(t *testing.T) {
}
func TestIntersectDiffNodes(t *testing.T) {
- a := make(Nodes)
- b := make(Nodes)
- c := make(Nodes)
+ a := NewNodes()
+ b := NewNodes()
+ c := NewNodes()
a.Add(node(2))
a.Add(node(3))
@@ -675,9 +675,9 @@ func TestIntersectDiffNodes(t *testing.T) {
}
func TestIntersectOverlappingNodes(t *testing.T) {
- a := make(Nodes)
- b := make(Nodes)
- c := make(Nodes)
+ a := NewNodes()
+ b := NewNodes()
+ c := NewNodes()
a.Add(node(2))
a.Add(node(3))

MODIFY
graph/multi/directed_test.go
graph/multi/directed_test.go
@@ -18,7 +18,7 @@ import (
)
func directedBuilder(nodes []graph.Node, edges []testgraph.WeightedLine, _, _ float64) (g graph.Graph, n []graph.Node, e []testgraph.Edge, s, a float64, ok bool) {
- seen := make(set.Nodes)
+ seen := set.NewNodes()
dg := multi.NewDirectedGraph()
for _, n := range nodes {
seen.Add(n)

MODIFY
graph/multi/undirected_test.go
graph/multi/undirected_test.go
@@ -18,7 +18,7 @@ import (
)
func undirectedBuilder(nodes []graph.Node, edges []testgraph.WeightedLine, _, _ float64) (g graph.Graph, n []graph.Node, e []testgraph.Edge, s, a float64, ok bool) {
- seen := make(set.Nodes)
+ seen := set.NewNodes()
ug := multi.NewUndirectedGraph()
for _, n := range nodes {
seen.Add(n)

MODIFY
graph/multi/weighted_directed_test.go
graph/multi/weighted_directed_test.go
@@ -17,7 +17,7 @@ import (
)
func weightedDirectedBuilder(nodes []graph.Node, edges []testgraph.WeightedLine, self, absent float64) (g graph.Graph, n []graph.Node, e []testgraph.Edge, s, a float64, ok bool) {
- seen := make(set.Nodes)
+ seen := set.NewNodes()
dg := multi.NewWeightedDirectedGraph()
dg.EdgeWeightFunc = func(l graph.WeightedLines) float64 {
if l.Len() == 0 {

MODIFY
graph/multi/weighted_undirected_test.go
graph/multi/weighted_undirected_test.go
@@ -17,7 +17,7 @@ import (
)
func weightedUndirectedBuilder(nodes []graph.Node, edges []testgraph.WeightedLine, self, absent float64) (g graph.Graph, n []graph.Node, e []testgraph.Edge, s, a float64, ok bool) {
- seen := make(set.Nodes)
+ seen := set.NewNodes()
ug := multi.NewWeightedUndirectedGraph()
ug.EdgeWeightFunc = func(l graph.WeightedLines) float64 {
if l.Len() == 0 {

MODIFY
graph/simple/densegraph_test.go
graph/simple/densegraph_test.go
@@ -38,7 +38,7 @@ func directedMatrixBuilder(nodes []graph.Node, edges []testgraph.WeightedLine, s
if !isZeroContiguousSet(nodes) {
return
}
- seen := make(set.Nodes)
+ seen := set.NewNodes()
dg := simple.NewDirectedMatrix(len(nodes), absent, self, absent)
for i := range nodes {
seen.Add(simple.Node(i))
@@ -157,7 +157,7 @@ func directedMatrixFromBuilder(nodes []graph.Node, edges []testgraph.WeightedLin
if !isZeroContiguousSet(nodes) {
return
}
- seen := make(set.Nodes)
+ seen := set.NewNodes()
dg := simple.NewDirectedMatrixFrom(nodes, absent, self, absent)
for _, n := range nodes {
seen.Add(n)
@@ -289,7 +289,7 @@ func undirectedMatrixBuilder(nodes []graph.Node, edges []testgraph.WeightedLine,
if !isZeroContiguousSet(nodes) {
return
}
- seen := make(set.Nodes)
+ seen := set.NewNodes()
dg := simple.NewUndirectedMatrix(len(nodes), absent, self, absent)
for i := range nodes {
seen.Add(simple.Node(i))
@@ -408,7 +408,7 @@ func undirectedMatrixFromBuilder(nodes []graph.Node, edges []testgraph.WeightedL
if !isZeroContiguousSet(nodes) {
return
}
- seen := make(set.Nodes)
+ seen := set.NewNodes()
dg := simple.NewUndirectedMatrixFrom(nodes, absent, self, absent)
for _, n := range nodes {
seen.Add(n)

MODIFY
graph/simple/directed_test.go
graph/simple/directed_test.go
@@ -17,7 +17,7 @@ import (
)
func directedBuilder(nodes []graph.Node, edges []testgraph.WeightedLine, _, _ float64) (g graph.Graph, n []graph.Node, e []testgraph.Edge, s, a float64, ok bool) {
- seen := make(set.Nodes)
+ seen := set.NewNodes()
dg := simple.NewDirectedGraph()
for _, n := range nodes {
seen.Add(n)

MODIFY
graph/simple/undirected_test.go
graph/simple/undirected_test.go
@@ -17,7 +17,7 @@ import (
)
func undirectedBuilder(nodes []graph.Node, edges []testgraph.WeightedLine, _, _ float64) (g graph.Graph, n []graph.Node, e []testgraph.Edge, s, a float64, ok bool) {
- seen := make(set.Nodes)
+ seen := set.NewNodes()
ug := simple.NewUndirectedGraph()
for _, n := range nodes {
seen.Add(n)

MODIFY
graph/simple/weighted_directed_test.go
graph/simple/weighted_directed_test.go
@@ -17,7 +17,7 @@ import (
)
func weightedDirectedBuilder(nodes []graph.Node, edges []testgraph.WeightedLine, self, absent float64) (g graph.Graph, n []graph.Node, e []testgraph.Edge, s, a float64, ok bool) {
- seen := make(set.Nodes)
+ seen := set.NewNodes()
dg := simple.NewWeightedDirectedGraph(self, absent)
for _, n := range nodes {
seen.Add(n)

MODIFY
graph/simple/weighted_undirected_test.go
graph/simple/weighted_undirected_test.go
@@ -17,7 +17,7 @@ import (
)
func weightedUndirectedBuilder(nodes []graph.Node, edges []testgraph.WeightedLine, self, absent float64) (g graph.Graph, n []graph.Node, e []testgraph.Edge, s, a float64, ok bool) {
- seen := make(set.Nodes)
+ seen := set.NewNodes()
ug := simple.NewWeightedUndirectedGraph(self, absent)
for _, n := range nodes {
seen.Add(n)

MODIFY
graph/testgraph/testgraph.go
graph/testgraph/testgraph.go
@@ -180,7 +180,7 @@ func NodeExistence(t *testing.T, b Builder) {
continue
}
- seen := make(set.Nodes)
+ seen := set.NewNodes()
for _, exist := range want {
seen.Add(exist)
if g.Node(exist.ID()) == nil {

MODIFY
graph/topo/bron_kerbosch.go
graph/topo/bron_kerbosch.go
@@ -138,21 +138,21 @@ func BronKerbosch(g graph.Undirected) [][]graph.Node {
// The algorithm used here is essentially BronKerbosch3 as described at
// http://en.wikipedia.org/w/index.php?title=Bron%E2%80%93Kerbosch_algorithm&oldid=656805858
- p := make(set.Nodes, len(nodes))
+ p := set.NewNodesSize(len(nodes))
for _, n := range nodes {
p.Add(n)
}
- x := make(set.Nodes)
+ x := set.NewNodes()
var bk bronKerbosch
order, _ := degeneracyOrdering(g)
ordered.Reverse(order)
for _, v := range order {
neighbours := graph.NodesOf(g.From(v.ID()))
- nv := make(set.Nodes, len(neighbours))
+ nv := set.NewNodesSize(len(neighbours))
for _, n := range neighbours {
nv.Add(n)
}
- bk.maximalCliquePivot(g, []graph.Node{v}, make(set.Nodes).Intersect(p, nv), make(set.Nodes).Intersect(x, nv))
+ bk.maximalCliquePivot(g, []graph.Node{v}, set.NewNodes().Intersect(p, nv), set.NewNodes().Intersect(x, nv))
p.Remove(v)
x.Add(v)
}
@@ -168,7 +168,7 @@ func (bk *bronKerbosch) maximalCliquePivot(g graph.Undirected, r []graph.Node, p
}
neighbours := bk.choosePivotFrom(g, p, x)
- nu := make(set.Nodes, len(neighbours))
+ nu := set.NewNodesSize(len(neighbours))
for _, n := range neighbours {
nu.Add(n)
}
@@ -178,7 +178,7 @@ func (bk *bronKerbosch) maximalCliquePivot(g graph.Undirected, r []graph.Node, p
}
vid := v.ID()
neighbours := graph.NodesOf(g.From(vid))
- nv := make(set.Nodes, len(neighbours))
+ nv := set.NewNodesSize(len(neighbours))
for _, n := range neighbours {
nv.Add(n)
}
@@ -195,7 +195,7 @@ func (bk *bronKerbosch) maximalCliquePivot(g graph.Undirected, r []graph.Node, p
sr = append(r[:len(r):len(r)], v)
}
- bk.maximalCliquePivot(g, sr, make(set.Nodes).Intersect(p, nv), make(set.Nodes).Intersect(x, nv))
+ bk.maximalCliquePivot(g, sr, set.NewNodes().Intersect(p, nv), set.NewNodes().Intersect(x, nv))
p.Remove(v)
x.Add(v)
}

MODIFY
graph/topo/clique_graph.go
graph/topo/clique_graph.go
@@ -34,7 +34,7 @@ func CliqueGraph(dst Builder, g graph.Undirected) {
cliqueNodes := make(cliqueNodeSets, len(cliques))
for id, c := range cliques {
- s := make(set.Nodes, len(c))
+ s := set.NewNodesSize(len(c))
for _, n := range c {
s.Add(n)
}
@@ -58,7 +58,7 @@ func CliqueGraph(dst Builder, g graph.Undirected) {
case len(vc.Clique.nodes):
edgeNodes = []graph.Node{vc.Clique.nodes[0]}
default:
- for _, n := range make(set.Nodes).Intersect(uc.nodes, vc.nodes) {
+ for _, n := range set.NewNodes().Intersect(uc.nodes, vc.nodes) {
edgeNodes = append(edgeNodes, n)
}
sort.Sort(ordered.ByID(edgeNodes))

graph/internal/set: make Nodes creation a function

This allows us to alter the type that is returned and the
underlying implementation if necessary.