Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
397 lines (354 sloc) 9.44 KB
// Copyright ©2015 The Gonum Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
// The functions in this file are random graph generators from the paper
// by Batagelj and Brandes http://algo.uni-konstanz.de/publications/bb-eglrn-05.pdf
package gen
import (
"fmt"
"math"
"golang.org/x/exp/rand"
"gonum.org/v1/gonum/graph"
)
// Gnp constructs a Gilbert’s model subgraph in the destination, dst, of order n. Edges
// between nodes are formed with the probability, p. If src is not nil it is used
// as the random source, otherwise rand.Float64 is used. The graph is constructed
// in O(n+m) time where m is the number of edges added.
func Gnp(dst graph.Builder, n int, p float64, src rand.Source) error {
if p == 0 {
for i := 0; i < n; i++ {
dst.AddNode(dst.NewNode())
}
return nil
}
if p < 0 || p > 1 {
return fmt.Errorf("gen: bad probability: p=%v", p)
}
var r func() float64
if src == nil {
r = rand.Float64
} else {
r = rand.New(src).Float64
}
nodes := make([]graph.Node, n)
for i := range nodes {
u := dst.NewNode()
dst.AddNode(u)
nodes[i] = u
}
lp := math.Log(1 - p)
// Add forward edges for all graphs.
for v, w := 1, -1; v < n; {
w += 1 + int(math.Log(1-r())/lp)
for w >= v && v < n {
w -= v
v++
}
if v < n {
dst.SetEdge(dst.NewEdge(nodes[w], nodes[v]))
}
}
// Add backward edges for directed graphs.
if _, ok := dst.(graph.Directed); !ok {
return nil
}
for v, w := 1, -1; v < n; {
w += 1 + int(math.Log(1-r())/lp)
for w >= v && v < n {
w -= v
v++
}
if v < n {
dst.SetEdge(dst.NewEdge(nodes[v], nodes[w]))
}
}
return nil
}
// Gnm constructs a Erdős-Rényi model subgraph in the destination, dst, of
// order n and size m. If src is not nil it is used as the random source,
// otherwise rand.Intn is used. The graph is constructed in O(m) expected
// time for m ≤ (n choose 2)/2.
func Gnm(dst GraphBuilder, n, m int, src rand.Source) error {
if m == 0 {
for i := 0; i < n; i++ {
dst.AddNode(dst.NewNode())
}
return nil
}
hasEdge := dst.HasEdgeBetween
d, isDirected := dst.(graph.Directed)
if isDirected {
m /= 2
hasEdge = d.HasEdgeFromTo
}
nChoose2 := (n - 1) * n / 2
if m < 0 || m > nChoose2 {
return fmt.Errorf("gen: bad size: m=%d", m)
}
var rnd func(int) int
if src == nil {
rnd = rand.Intn
} else {
rnd = rand.New(src).Intn
}
nodes := make([]graph.Node, n)
for i := range nodes {
u := dst.NewNode()
dst.AddNode(u)
nodes[i] = u
}
// Add forward edges for all graphs.
for i := 0; i < m; i++ {
for {
v, w := edgeNodesFor(rnd(nChoose2), nodes)
if !hasEdge(w.ID(), v.ID()) {
dst.SetEdge(dst.NewEdge(w, v))
break
}
}
}
// Add backward edges for directed graphs.
if !isDirected {
return nil
}
for i := 0; i < m; i++ {
for {
v, w := edgeNodesFor(rnd(nChoose2), nodes)
if !hasEdge(v.ID(), w.ID()) {
dst.SetEdge(dst.NewEdge(v, w))
break
}
}
}
return nil
}
// SmallWorldsBB constructs a small worlds subgraph of order n in the destination, dst.
// Node degree is specified by d and edge replacement by the probability, p.
// If src is not nil it is used as the random source, otherwise rand.Float64 is used.
// The graph is constructed in O(nd) time.
//
// The algorithm used is described in http://algo.uni-konstanz.de/publications/bb-eglrn-05.pdf
func SmallWorldsBB(dst GraphBuilder, n, d int, p float64, src rand.Source) error {
if d < 1 || d > (n-1)/2 {
return fmt.Errorf("gen: bad degree: d=%d", d)
}
if p == 0 {
for i := 0; i < n; i++ {
dst.AddNode(dst.NewNode())
}
return nil
}
if p < 0 || p >= 1 {
return fmt.Errorf("gen: bad replacement: p=%v", p)
}
var (
rnd func() float64
rndN func(int) int
)
if src == nil {
rnd = rand.Float64
rndN = rand.Intn
} else {
r := rand.New(src)
rnd = r.Float64
rndN = r.Intn
}
hasEdge := dst.HasEdgeBetween
dg, isDirected := dst.(graph.Directed)
if isDirected {
hasEdge = dg.HasEdgeFromTo
}
nodes := make([]graph.Node, n)
for i := range nodes {
u := dst.NewNode()
dst.AddNode(u)
nodes[i] = u
}
nChoose2 := (n - 1) * n / 2
lp := math.Log(1 - p)
// Add forward edges for all graphs.
k := int(math.Log(1-rnd()) / lp)
m := 0
replace := make(map[int]int)
for v := 0; v < n; v++ {
for i := 1; i <= d; i++ {
if k > 0 {
j := v*(v-1)/2 + (v+i)%n
if v, u := edgeNodesFor(j, nodes); !hasEdge(u.ID(), v.ID()) {
dst.SetEdge(dst.NewEdge(u, v))
}
k--
m++
// For small graphs, m may be an
// edge that has an end that is
// not in the subgraph.
if m >= nChoose2 {
// Since m is monotonically
// increasing, no m edges from
// here on are valid, so don't
// add them to replace.
continue
}
if v, u := edgeNodesFor(m, nodes); !hasEdge(u.ID(), v.ID()) {
replace[j] = m
} else {
replace[j] = replace[m]
}
} else {
k = int(math.Log(1-rnd()) / lp)
}
}
}
for i := m + 1; i <= n*d && i < nChoose2; i++ {
r := rndN(nChoose2-i) + i
if v, u := edgeNodesFor(r, nodes); !hasEdge(u.ID(), v.ID()) {
dst.SetEdge(dst.NewEdge(u, v))
} else if v, u = edgeNodesFor(replace[r], nodes); !hasEdge(u.ID(), v.ID()) {
dst.SetEdge(dst.NewEdge(u, v))
}
if v, u := edgeNodesFor(i, nodes); !hasEdge(u.ID(), v.ID()) {
replace[r] = i
} else {
replace[r] = replace[i]
}
}
// Add backward edges for directed graphs.
if !isDirected {
return nil
}
k = int(math.Log(1-rnd()) / lp)
m = 0
replace = make(map[int]int)
for v := 0; v < n; v++ {
for i := 1; i <= d; i++ {
if k > 0 {
j := v*(v-1)/2 + (v+i)%n
if u, v := edgeNodesFor(j, nodes); !hasEdge(u.ID(), v.ID()) {
dst.SetEdge(dst.NewEdge(u, v))
}
k--
m++
// For small graphs, m may be an
// edge that has an end that is
// not in the subgraph.
if m >= nChoose2 {
// Since m is monotonically
// increasing, no m edges from
// here on are valid, so don't
// add them to replace.
continue
}
if u, v := edgeNodesFor(m, nodes); !hasEdge(u.ID(), v.ID()) {
replace[j] = m
} else {
replace[j] = replace[m]
}
} else {
k = int(math.Log(1-rnd()) / lp)
}
}
}
for i := m + 1; i <= n*d && i < nChoose2; i++ {
r := rndN(nChoose2-i) + i
if u, v := edgeNodesFor(r, nodes); !hasEdge(u.ID(), v.ID()) {
dst.SetEdge(dst.NewEdge(u, v))
} else if u, v = edgeNodesFor(replace[r], nodes); !hasEdge(u.ID(), v.ID()) {
dst.SetEdge(dst.NewEdge(u, v))
}
if u, v := edgeNodesFor(i, nodes); !hasEdge(u.ID(), v.ID()) {
replace[r] = i
} else {
replace[r] = replace[i]
}
}
return nil
}
// edgeNodesFor returns the pair of nodes for the ith edge in a simple
// undirected graph. The pair is returned such that the index of w in
// nodes is less than the index of v in nodes.
func edgeNodesFor(i int, nodes []graph.Node) (v, w graph.Node) {
// This is an algebraic simplification of the expressions described
// on p3 of http://algo.uni-konstanz.de/publications/bb-eglrn-05.pdf
vi := int(0.5 + math.Sqrt(float64(1+8*i))/2)
wi := i - vi*(vi-1)/2
return nodes[vi], nodes[wi]
}
// Multigraph generators.
// PowerLaw constructs a power-law degree graph by preferential attachment in dst
// with n nodes and minimum degree d. PowerLaw does not consider nodes in dst prior
// to the call. If src is not nil it is used as the random source, otherwise rand.Intn
// is used.
// The graph is constructed in O(nd) — O(n+m) — time.
//
// The algorithm used is described in http://algo.uni-konstanz.de/publications/bb-eglrn-05.pdf
func PowerLaw(dst graph.MultigraphBuilder, n, d int, src rand.Source) error {
if d < 1 {
return fmt.Errorf("gen: bad minimum degree: d=%d", d)
}
var rnd func(int) int
if src == nil {
rnd = rand.Intn
} else {
rnd = rand.New(src).Intn
}
m := make([]graph.Node, 2*n*d)
for v := 0; v < n; v++ {
x := dst.NewNode()
dst.AddNode(x)
for i := 0; i < d; i++ {
m[2*(v*d+i)] = x
m[2*(v*d+i)+1] = m[rnd(2*v*d+i+1)]
}
}
for i := 0; i < n*d; i++ {
dst.SetLine(dst.NewLine(m[2*i], m[2*i+1]))
}
return nil
}
// BipartitePowerLaw constructs a bipartite power-law degree graph by preferential attachment
// in dst with 2×n nodes and minimum degree d. BipartitePowerLaw does not consider nodes in
// dst prior to the call. The two partitions are returned in p1 and p2. If src is not nil it is
// used as the random source, otherwise rand.Intn is used.
// The graph is constructed in O(nd) — O(n+m) — time.
//
// The algorithm used is described in http://algo.uni-konstanz.de/publications/bb-eglrn-05.pdf
func BipartitePowerLaw(dst graph.MultigraphBuilder, n, d int, src rand.Source) (p1, p2 []graph.Node, err error) {
if d < 1 {
return nil, nil, fmt.Errorf("gen: bad minimum degree: d=%d", d)
}
var rnd func(int) int
if src == nil {
rnd = rand.Intn
} else {
rnd = rand.New(src).Intn
}
p := make([]graph.Node, 2*n)
for i := range p {
u := dst.NewNode()
dst.AddNode(u)
p[i] = u
}
m1 := make([]graph.Node, 2*n*d)
m2 := make([]graph.Node, 2*n*d)
for v := 0; v < n; v++ {
for i := 0; i < d; i++ {
m1[2*(v*d+i)] = p[v]
m2[2*(v*d+i)] = p[n+v]
if r := rnd(2*v*d + i + 1); r&0x1 == 0 {
m1[2*(v*d+i)+1] = m2[r]
} else {
m1[2*(v*d+i)+1] = m1[r]
}
if r := rnd(2*v*d + i + 1); r&0x1 == 0 {
m2[2*(v*d+i)+1] = m1[r]
} else {
m2[2*(v*d+i)+1] = m2[r]
}
}
}
for i := 0; i < n*d; i++ {
dst.SetLine(dst.NewLine(m1[2*i], m1[2*i+1]))
dst.SetLine(dst.NewLine(m2[2*i], m2[2*i+1]))
}
return p[:n], p[n:], nil
}
You can’t perform that action at this time.