package gen
import "gonum.org/v1/gonum/graph/graphs/gen"
Package gen provides random graph generation functions.
Index ¶
- func BipartitePowerLaw(dst graph.MultigraphBuilder, n, d int, src rand.Source) (p1, p2 []graph.Node, err error)
- func Complete(dst NodeIDGraphBuilder, ids IDer)
- func Cycle(dst NodeIDGraphBuilder, cycle IDer)
- func Duplication(dst UndirectedMutator, n int, delta, alpha, sigma float64, src rand.Source) error
- func Gnm(dst GraphBuilder, n, m int, src rand.Source) error
- func Gnp(dst graph.Builder, n int, p float64, src rand.Source) error
- func NavigableSmallWorld(dst GraphBuilder, dims []int, p, q int, r float64, src rand.Source) (err error)
- func Path(dst NodeIDGraphBuilder, path IDer)
- func PowerLaw(dst graph.MultigraphBuilder, n, d int, src rand.Source) error
- func PreferentialAttachment(dst graph.UndirectedBuilder, n, m int, src rand.Source) error
- func SmallWorldsBB(dst GraphBuilder, n, d int, p float64, src rand.Source) error
- func Star(dst NodeIDGraphBuilder, center int64, leaves IDer)
- func Tree(dst NodeIDGraphBuilder, n int, nodes IDer)
- func TunableClusteringScaleFree(dst graph.UndirectedBuilder, n, m int, p float64, src rand.Source) error
- func Wheel(dst NodeIDGraphBuilder, center int64, cycle IDer)
- type GraphBuilder
- type IDRange
- type IDSet
- type IDer
- type NodeIDGraphBuilder
- type UndirectedMutator
Examples ¶
- Complete (BiDirectedSet)
- Complete (DirectedSet)
- Complete (UndirectedSet)
- Path (DirectedSet)
- Star (UndirectedRange)
- Tree (UndirectedRange)
- Wheel (DirectedRange)
Functions ¶
func BipartitePowerLaw ¶
func BipartitePowerLaw(dst graph.MultigraphBuilder, n, d int, src rand.Source) (p1, p2 []graph.Node, err error)
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 Complete ¶
func Complete(dst NodeIDGraphBuilder, ids IDer)
Complete constructs a complete graph in dst using nodes with the given IDs.
If any ID appears twice in ids, Complete will panic.
Code:play
Output: Code:play
Output: Code:play
Output:Example (BiDirectedSet)¶
package main
import (
"fmt"
"log"
"gonum.org/v1/gonum/graph"
"gonum.org/v1/gonum/graph/encoding/dot"
"gonum.org/v1/gonum/graph/graphs/gen"
"gonum.org/v1/gonum/graph/simple"
)
// Bidirected allows bidirectional directed graph construction.
type Bidirected struct {
*simple.DirectedGraph
}
func (g Bidirected) SetEdge(e graph.Edge) {
g.DirectedGraph.SetEdge(e)
g.DirectedGraph.SetEdge(e.ReversedEdge())
}
func main() {
dst := simple.NewDirectedGraph()
gen.Complete(Bidirected{dst}, gen.IDSet{2, 4, 5, 9})
b, err := dot.Marshal(dst, "complete", "", "\t")
if err != nil {
log.Fatal(err)
}
fmt.Printf("%s\n", b)
}
strict digraph complete {
// Node definitions.
2;
4;
5;
9;
// Edge definitions.
2 -> 4;
2 -> 5;
2 -> 9;
4 -> 2;
4 -> 5;
4 -> 9;
5 -> 2;
5 -> 4;
5 -> 9;
9 -> 2;
9 -> 4;
9 -> 5;
}
Example (DirectedSet)¶
package main
import (
"fmt"
"log"
"gonum.org/v1/gonum/graph/encoding/dot"
"gonum.org/v1/gonum/graph/graphs/gen"
"gonum.org/v1/gonum/graph/simple"
)
func main() {
dst := simple.NewDirectedGraph()
gen.Complete(dst, gen.IDSet{2, 4, 5, 9})
b, err := dot.Marshal(dst, "complete", "", "\t")
if err != nil {
log.Fatal(err)
}
fmt.Printf("%s\n", b)
}
strict digraph complete {
// Node definitions.
2;
4;
5;
9;
// Edge definitions.
2 -> 4;
2 -> 5;
2 -> 9;
4 -> 5;
4 -> 9;
5 -> 9;
}
Example (UndirectedSet)¶
package main
import (
"fmt"
"log"
"gonum.org/v1/gonum/graph/encoding/dot"
"gonum.org/v1/gonum/graph/graphs/gen"
"gonum.org/v1/gonum/graph/simple"
)
func main() {
dst := simple.NewUndirectedGraph()
gen.Complete(dst, gen.IDSet{2, 4, 5, 9})
b, err := dot.Marshal(dst, "complete", "", "\t")
if err != nil {
log.Fatal(err)
}
fmt.Printf("%s\n", b)
}
strict graph complete {
// Node definitions.
2;
4;
5;
9;
// Edge definitions.
2 -- 4;
2 -- 5;
2 -- 9;
4 -- 5;
4 -- 9;
5 -- 9;
}
func Cycle ¶
func Cycle(dst NodeIDGraphBuilder, cycle IDer)
Cycle constructs a cycle in dst using the node IDs in cycle. If dst is a directed graph, edges are directed from earlier nodes to later nodes in cycle. If any ID appears twice in cycle, Cycle will panic.
func Duplication ¶
Duplication constructs a graph in the destination, dst, of order n. New nodes are created by duplicating an existing node and all its edges. Each new edge is deleted with probability delta. Additional edges are added between the new node and existing nodes with probability alpha/|V|. An exception to this addition rule is made for the parent node when sigma is not NaN; in this case an edge is created with probability sigma. With the exception of the sigma parameter, this corresponds to the completely correlated case in doi:10.1016/S0022-5193(03)00028-6. If src is not nil it is used as the random source, otherwise rand.Float64 is used.
func Gnm ¶
func Gnm(dst GraphBuilder, n, m int, src rand.Source) error
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 Gnp ¶
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 NavigableSmallWorld ¶
func NavigableSmallWorld(dst GraphBuilder, dims []int, p, q int, r float64, src rand.Source) (err error)
NavigableSmallWorld constructs an N-dimensional grid with guaranteed local connectivity and random long-range connectivity as a subgraph in the destination, dst. The dims parameters specifies the length of each of the N dimensions, p defines the Manhattan distance between local nodes, and q defines the number of out-going long-range connections from each node. Long-range connections are made with a probability proportional to |d(u,v)|^-r where d is the Manhattan distance between non-local nodes.
The algorithm is essentially as described on p4 of http://www.cs.cornell.edu/home/kleinber/swn.pdf.
func Path ¶
func Path(dst NodeIDGraphBuilder, path IDer)
Path constructs a path graph in dst with
If dst is a directed graph, edges are directed from earlier nodes to later
nodes in path. If any ID appears twice in path, Path will panic.
Code:play
Output:Example (DirectedSet)¶
package main
import (
"fmt"
"log"
"gonum.org/v1/gonum/graph/encoding/dot"
"gonum.org/v1/gonum/graph/graphs/gen"
"gonum.org/v1/gonum/graph/simple"
)
func main() {
dst := simple.NewDirectedGraph()
gen.Path(dst, gen.IDSet{2, 4, 5, 9})
b, err := dot.Marshal(dst, "path", "", "\t")
if err != nil {
log.Fatal(err)
}
fmt.Printf("%s\n", b)
}
strict digraph path {
// Node definitions.
2;
4;
5;
9;
// Edge definitions.
2 -> 4;
4 -> 5;
5 -> 9;
}
func PowerLaw ¶
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 PreferentialAttachment ¶
PreferentialAttachment constructs a graph 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' degrees. If src is not nil it is used as the random source, otherwise rand.Float64 is used for the random number generator.
The algorithm is essentially as described in http://arxiv.org/abs/cond-mat/0110452 after 10.1126/science.286.5439.509.
func SmallWorldsBB ¶
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 Star ¶
func Star(dst NodeIDGraphBuilder, center int64, leaves IDer)
Star constructs a star graph in dst with edges between the center node ID to
node with IDs specified in leaves.
If dst is a directed graph, edges are directed from the center node to the
leaves. If any ID appears twice in leaves and center, Star will panic.
Code:play
Output:Example (UndirectedRange)¶
package main
import (
"fmt"
"log"
"gonum.org/v1/gonum/graph/encoding/dot"
"gonum.org/v1/gonum/graph/graphs/gen"
"gonum.org/v1/gonum/graph/simple"
)
func main() {
dst := simple.NewUndirectedGraph()
gen.Star(dst, 0, gen.IDRange{First: 1, Last: 6})
b, err := dot.Marshal(dst, "star", "", "\t")
if err != nil {
log.Fatal(err)
}
fmt.Printf("%s\n", b)
}
strict graph star {
// Node definitions.
0;
1;
2;
3;
4;
5;
6;
// Edge definitions.
0 -- 1;
0 -- 2;
0 -- 3;
0 -- 4;
0 -- 5;
0 -- 6;
}
func Tree ¶
func Tree(dst NodeIDGraphBuilder, n int, nodes IDer)
Tree constructs an n-ary tree breadth-first in dst with the given fan-out, n.
If the number of nodes does not equal \sum_{i=0}^h n^i, where h is an integer
indicating the height of the tree, a partial tree will be constructed with not
all nodes having zero or n children, and not all leaves being h from the root.
If the number of nodes is greater than one, n must be non-zero and
less than the number of nodes, otherwise Tree will panic.
If dst is a directed graph, edges are directed from the root to the leaves.
If any ID appears more than once in nodes, Tree will panic.
Code:play
Output:Example (UndirectedRange)¶
package main
import (
"fmt"
"log"
"gonum.org/v1/gonum/graph/encoding/dot"
"gonum.org/v1/gonum/graph/graphs/gen"
"gonum.org/v1/gonum/graph/simple"
)
func main() {
dst := simple.NewUndirectedGraph()
gen.Tree(dst, 2, gen.IDRange{First: 0, Last: 14})
b, err := dot.Marshal(dst, "full_binary_tree_undirected", "", "\t")
if err != nil {
log.Fatal(err)
}
fmt.Printf("%s\n", b)
}
strict graph full_binary_tree_undirected {
// Node definitions.
0;
1;
2;
3;
4;
5;
6;
7;
8;
9;
10;
11;
12;
13;
14;
// Edge definitions.
0 -- 1;
0 -- 2;
1 -- 3;
1 -- 4;
2 -- 5;
2 -- 6;
3 -- 7;
3 -- 8;
4 -- 9;
4 -- 10;
5 -- 11;
5 -- 12;
6 -- 13;
6 -- 14;
}
func TunableClusteringScaleFree ¶
func TunableClusteringScaleFree(dst graph.UndirectedBuilder, n, m int, p float64, src rand.Source) error
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' degrees. The edges are formed as a triad with probability, p. If src is not nil it is used as the random source, otherwise rand.Float64 and rand.Intn are used for the random number generators.
The algorithm is essentially as described in http://arxiv.org/abs/cond-mat/0110452.
func Wheel ¶
func Wheel(dst NodeIDGraphBuilder, center int64, cycle IDer)
Wheel constructs a wheel graph in dst with edges from the center
node ID to node with IDs specified in cycle and between nodes with IDs
adjacent in the cycle.
If dst is a directed graph, edges are directed from the center node to the
cycle and from earlier nodes to later nodes in cycle. If any ID appears
twice in cycle and center, Wheel will panic.
Code:play
Output:Example (DirectedRange)¶
package main
import (
"fmt"
"log"
"gonum.org/v1/gonum/graph/encoding/dot"
"gonum.org/v1/gonum/graph/graphs/gen"
"gonum.org/v1/gonum/graph/simple"
)
func main() {
dst := simple.NewDirectedGraph()
gen.Wheel(dst, 0, gen.IDRange{First: 1, Last: 6})
b, err := dot.Marshal(dst, "wheel", "", "\t")
if err != nil {
log.Fatal(err)
}
fmt.Printf("%s\n", b)
}
strict digraph wheel {
// Node definitions.
0;
1;
2;
3;
4;
5;
6;
// Edge definitions.
0 -> 1;
0 -> 2;
0 -> 3;
0 -> 4;
0 -> 5;
0 -> 6;
1 -> 2;
2 -> 3;
3 -> 4;
4 -> 5;
5 -> 6;
6 -> 1;
}
Types ¶
type GraphBuilder ¶
GraphBuilder is a graph that can have nodes and edges added.
type IDRange ¶
type IDRange struct{ First, Last int64 }
IDRange is an IDer that provides a set of IDs in [First, Last].
func (IDRange) ID ¶
func (IDRange) Len ¶
type IDSet ¶
type IDSet []int64
IDSet is an IDer providing an explicit set of IDs.
func (IDSet) ID ¶
func (IDSet) Len ¶
type IDer ¶
type IDer interface { // Len returns the length of the set of node IDs. Len() int // ID returns the ID of the indexed node. // ID must be a bijective function. No check // is made for this property. ID(int) int64 }
IDer is a mapping from an index to a node ID.
type NodeIDGraphBuilder ¶
type NodeIDGraphBuilder interface { graph.Builder graph.NodeWithIDer }
NodeIDGraphBuilder is a graph that can create new nodes with specified IDs.
type UndirectedMutator ¶
type UndirectedMutator interface { graph.UndirectedBuilder graph.EdgeRemover }
UndirectedMutator is an undirected graph builder that can remove edges.
Source Files ¶
batagelj_brandes.go doc.go duplication.go gen.go holme_kim.go small_world.go
- Version
- v0.15.1 (latest)
- Published
- Aug 16, 2024
- Platform
- linux/amd64
- Imports
- 8 packages
- Last checked
- 9 hours ago –
Tools for package owners.