gen

package
v0.11.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Mar 16, 2022 License: BSD-3-Clause Imports: 8 Imported by: 0

Documentation

Overview

Package gen provides random graph generation functions.

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

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 added in v0.11.0 

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.

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)

}

Output:

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)

}

Output:

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)

}

Output:

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 added in v0.11.0 

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 

func Duplication(dst UndirectedMutator, n int, delta, alpha, sigma float64, src rand.Source) error

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 

func Gnp(dst graph.Builder, n int, p float64, src rand.Source) error

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(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 added in v0.11.0 

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.

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)

}

Output:

strict digraph path {
	// Node definitions.
	2;
	4;
	5;
	9;

	// Edge definitions.
	2 -> 4;
	4 -> 5;
	5 -> 9;
}

func PowerLaw 

func PowerLaw(dst graph.MultigraphBuilder, n, d int, src rand.Source) error

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 

func PreferentialAttachment(dst graph.UndirectedBuilder, n, m int, src rand.Source) error

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 

func SmallWorldsBB(dst GraphBuilder, n, d int, p float64, src rand.Source) error

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 added in v0.11.0 

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.

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)

}

Output:

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 added in v0.11.0 

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.

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)

}

Output:

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 added in v0.11.0 

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.

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)

}

Output:

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 

type GraphBuilder interface {
	HasEdgeBetween(xid, yid int64) bool
	graph.Builder
}

GraphBuilder is a graph that can have nodes and edges added.

type IDRange added in v0.11.0 

type IDRange struct{ First, Last int64 }

IDRange is an IDer that provides a set of IDs in [First, Last].

func (IDRange) ID added in v0.11.0 

func (r IDRange) ID(i int) int64

func (IDRange) Len added in v0.11.0 

func (r IDRange) Len() int

type IDSet added in v0.11.0 

type IDSet []int64

IDSet is an IDer providing an explicit set of IDs.

func (IDSet) ID added in v0.11.0 

func (s IDSet) ID(i int) int64

func (IDSet) Len added in v0.11.0 

func (s IDSet) Len() int

type IDer added in v0.11.0 

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 added in v0.11.0 

type NodeIDGraphBuilder interface {
	graph.Builder
	graph.NodeWithIDer
}

NodeIDGraphBuild 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

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.