graph/graphs/gen: make TunableClusteringScaleFree use dst's edge and node constructors
This changes the behaviour of the function to create the scale free graph as
a disconnected subgraph in g rather than applying the algorithm to potentially
already existing nodes in g.
MODIFY
graph/graphs/gen/holme_kim.go
graph/graphs/gen/holme_kim.go
@@ -15,7 +15,7 @@ import (
"gonum.org/v1/gonum/stat/sampleuv"
)
-// TunableClusteringScaleFree constructs a graph in the destination, dst, of order n.
+// TunableClusteringScaleFree constructs a subgraph in the destination, dst, of order n.
// The graph is constructed successively starting from an m order graph with one node
// having degree m-1. At each iteration of graph addition, one node is added with m
// additional edges joining existing nodes with probability proportional to the nodes'
@@ -47,10 +47,11 @@ func TunableClusteringScaleFree(dst graph.UndirectedBuilder, n, m int, p float64
// Initial condition.
wt := make([]float64, n)
+ id := make([]int64, n)
for u := 0; u < m; u++ {
- if dst.Node(int64(u)) == nil {
- dst.AddNode(simple.Node(u))
- }
+ un := dst.NewNode()
+ dst.AddNode(un)
+ id[u] = un.ID()
// We need to give equal probability for
// adding the first generation of edges.
wt[u] = 1
@@ -64,17 +65,24 @@ func TunableClusteringScaleFree(dst graph.UndirectedBuilder, n, m int, p float64
// Growth.
for v := m; v < n; v++ {
+ vn := dst.NewNode()
+ dst.AddNode(vn)
+ id[v] = vn.ID()
var u int
pa:
for i := 0; i < m; i++ {
// Triad formation.
if i != 0 && rnd() < p {
- for _, w := range permute(graph.NodesOf(dst.From(int64(u))), rndN) {
+ // TODO(kortschak): Decide whether the node
+ // order in this input to permute should be
+ // sorted first to allow repeatable runs.
+ for _, w := range permute(graph.NodesOf(dst.From(id[u])), rndN) {
wid := w.ID()
- if wid == int64(v) || dst.HasEdgeBetween(wid, int64(v)) {
+ if wid == id[v] || dst.HasEdgeBetween(wid, id[v]) {
continue
}
- dst.SetEdge(simple.Edge{F: w, T: simple.Node(v)})
+
+ dst.SetEdge(dst.NewEdge(w, vn))
wt[wid]++
wt[v]++
continue pa
@@ -88,10 +96,10 @@ func TunableClusteringScaleFree(dst graph.UndirectedBuilder, n, m int, p float64
if !ok {
return errors.New("gen: depleted distribution")
}
- if u == v || dst.HasEdgeBetween(int64(u), int64(v)) {
+ if u == v || dst.HasEdgeBetween(id[u], id[v]) {
continue
}
- dst.SetEdge(simple.Edge{F: simple.Node(u), T: simple.Node(v)})
+ dst.SetEdge(dst.NewEdge(dst.Node(id[u]), vn))
wt[u]++
wt[v]++
break

MODIFY
graph/graphs/gen/holme_kim_test.go
graph/graphs/gen/holme_kim_test.go
@@ -15,10 +15,15 @@ func TestTunableClusteringScaleFree(t *testing.T) {
for m := 0; m < n; m++ {
for p := 0.; p <= 1; p += 0.1 {
g := &gnUndirected{UndirectedBuilder: simple.NewUndirectedGraph()}
+ orig := g.NewNode()
+ g.AddNode(orig)
err := TunableClusteringScaleFree(g, n, m, p, nil)
if err != nil {
t.Fatalf("unexpected error: n=%d, m=%d, p=%v: %v", n, m, p, err)
}
+ if g.From(orig.ID()).Len() != 0 {
+ t.Errorf("edge added from already existing node: n=%d, m=%d, p=%v", n, m, p)
+ }
if g.addBackwards {
t.Errorf("edge added with From.ID > To.ID: n=%d, m=%d, p=%v", n, m, p)
}

graph/graphs/gen: make TunableClusteringScaleFree use dst's edge and node constructors

This changes the behaviour of the function to create the scale free graph as
a disconnected subgraph in g rather than applying the algorithm to potentially
already existing nodes in g.