Documentation
¶
Overview ¶
Package graph implements general-purpose graph algorithms.
This includes some "online algorithms" for dynamic graphs i.e. algorithms that can efficiently give new results as a graph changes.
This package does not implement any specific graph data structures: bring your own implementation!
In general, this package is written & composed in such a way as to reduce runtime memory (re)allocations by encouraging the caller to reuse buffers.
References ¶
Many of the algorithms and definitions are thanks to CLRS "Introduction to Algorithms", 3rd edition.
The slides from Danupon Nanongkai (KTH, Sweden)'s ADFOCS 2018 talk, "Introduction to Dynamic Graph Algorithms", were also helpful.
The dynamic BFS algorithm is from "Semi-dynamic breadth-first search in digraphs", Franciosa, Frigioni & Giaccio, Theoretical Computer Science, Vol. 250, Issue 1-2, Jan 6 2001, pp 201–217.
To do
Example (SolarSystem) ¶
package main import ( "fmt" stdslices "slices" "strings" "github.com/tawesoft/golib/v2/ds/graph" "github.com/tawesoft/golib/v2/fun/slices" "github.com/tawesoft/golib/v2/iter" "github.com/tawesoft/golib/v2/must" ) type Distance int type Body struct { Name string Orbits map[graph.VertexIndex]Distance } // Universe is a multigraph. type Universe struct { Bodies map[graph.VertexIndex]Body } // Vertexes implements the graph.Iterator interface. func (u Universe) Vertexes() func() (graph.VertexIndex, bool) { return iter.Keys(iter.FromMap(u.Bodies)) } // Edges implements the graph.Iterator interface. func (u Universe) Edges(source graph.VertexIndex) func() (target graph.VertexIndex, count int, ok bool) { vertex := u.Bodies[source] it := iter.Keys(iter.FromMap(vertex.Orbits)) return func() (_ graph.VertexIndex, _ int, _ bool) { target, ok := it() if !ok { return } return target, 1, true } } func (u Universe) Weight(source, target graph.VertexIndex) graph.Weight { return graph.Weight(u.Bodies[source].Orbits[target]) } func (u *Universe) AddVertex() graph.VertexIndex { index := graph.VertexIndex(len(u.Bodies)) if u.Bodies == nil { u.Bodies = make(map[graph.VertexIndex]Body) } u.Bodies[index] = Body{} return index } func (u *Universe) AddEdge(from graph.VertexIndex, to graph.VertexIndex) { u.Bodies[from].Orbits[to] = Distance(0) } func (u *Universe) AddBody(name string) graph.VertexIndex { index := u.AddVertex() u.Bodies[index] = Body{ Name: name, Orbits: make(map[graph.VertexIndex]Distance), } return index } func (u *Universe) AddOrbit(center graph.VertexIndex, body graph.VertexIndex, distance Distance) { u.AddEdge(center, body) u.Bodies[center].Orbits[body] = distance } func main() { // define a custom multigraph of orbit distances and solar irradiation var d Universe // Alpha Centuri is trinary star system with a binary star center alphaCentauri := d.AddBody("Alpha Centauri") // Alpha Centauri AB barycenter proximaCentauri := d.AddBody("Proxima Centauri") // Alpha Centauri C sun := d.AddBody("Sol") mercury := d.AddBody("Mercury") venus := d.AddBody("Venus") earth := d.AddBody("The Earth") mars := d.AddBody("Mars") jupiter := d.AddBody("Jupiter") saturn := d.AddBody("Saturn") uranus := d.AddBody("Uranus") neptune := d.AddBody("Neptune") moon := d.AddBody("The Moon") demos := d.AddBody("Demos") phobos := d.AddBody("Phobos") // Average orbit distance (kilometres) // (figures from NASA) d.AddOrbit(alphaCentauri, proximaCentauri, 1_937_292_425_565) d.AddOrbit(sun, mercury, 57_000_000) d.AddOrbit(sun, venus, 108_000_000) d.AddOrbit(sun, earth, 149_000_000) d.AddOrbit(sun, mars, 228_000_000) d.AddOrbit(sun, jupiter, 780_000_000) d.AddOrbit(sun, saturn, 1_437_000_000) d.AddOrbit(sun, uranus, 2_871_000_000) d.AddOrbit(sun, neptune, 4_530_000_000) d.AddOrbit(earth, moon, 384_400) d.AddOrbit(mars, demos, 23_460) d.AddOrbit(mars, phobos, 6_000) // construct an adjacency matrix for efficient adjacency lookup orbitMatrix := graph.NewAdjacencyMatrix() orbitMatrix.Calculate(d) // construct degree matrices for efficient in-/out- degree lookup indegreeMatrix := graph.NewDegreeMatrix() outdegreeMatrix := graph.NewDegreeMatrix() indegreeMatrix.Calculate(d.Vertexes, orbitMatrix.Indegree) outdegreeMatrix.Calculate(d.Vertexes, orbitMatrix.Outdegree) // construct a breadth-first search tree of everything reachable from the // sun i.e. all the solar system planets, and all their moons. solSystem := graph.NewBfsTree() solSystem.CalculateUnweighted(d, sun) // efficiently returns true iff a orbits b orbits := func(a graph.VertexIndex, b graph.VertexIndex) bool { return orbitMatrix.Get(b, a) > 0 } // efficiently returns the number of satellites orbiting a numSatellites := func(a graph.VertexIndex) int { return outdegreeMatrix.Get(a) } // produces target vertexes from orbit edges satellites := func(source graph.VertexIndex) func() (graph.VertexIndex, bool) { edges := d.Edges(source) return func() (graph.VertexIndex, bool) { for { targetIdx, _, ok := edges() return targetIdx, ok } } } must.Truef(orbits(earth, sun), "expected: earth orbits the sun") must.Truef(orbits(moon, earth), "expected: moon orbits the earth") must.Falsef(orbits(sun, earth), "expected: sun does not orbit the earth") // efficiently find all graph roots roots := iter.ToSlice(graph.Roots(orbitMatrix.Vertexes, indegreeMatrix.Get)) vertexName := func(x graph.VertexIndex) string { vertex := d.Bodies[x] return vertex.Name } sorted := func(xs []string) []string { stdslices.Sort(xs) return xs } fmt.Printf("The graph contains data for %d solar systems: %s.\n", len(roots), strings.Join(sorted(slices.Map(vertexName, roots)), " and ")) fmt.Printf("The sun is orbited by %d satellites.\n", numSatellites(sun)) fmt.Printf("Mars is orbited by %d satellites: %s.\n", numSatellites(mars), strings.Join(sorted(slices.Map(vertexName, iter.ToSlice(satellites(mars)))), " and ")) if solSystem.Reachable(phobos) { fmt.Println("The solar system contains Phobos.") } if !solSystem.Reachable(proximaCentauri) { fmt.Println("The solar system does not contain Proxima Centauri.") } fmt.Printf("Phobos orbits %s.\n", vertexName(must.Ok(solSystem.Predecessor(phobos)))) }
Output: The graph contains data for 2 solar systems: Alpha Centauri and Sol. The sun is orbited by 8 satellites. Mars is orbited by 2 satellites: Demos and Phobos. The solar system contains Phobos. The solar system does not contain Proxima Centauri. Phobos orbits Mars.
Index ¶
- type AdjacencyMatrix
- func (m *AdjacencyMatrix) Calculate(g Iterator)
- func (m AdjacencyMatrix) Clear()
- func (m AdjacencyMatrix) CountEdges() int
- func (m AdjacencyMatrix) Degree(source VertexIndex) int
- func (m AdjacencyMatrix) Edges(source VertexIndex) func() (VertexIndex, int, bool)
- func (m AdjacencyMatrix) Get(source, target VertexIndex) int
- func (m AdjacencyMatrix) Indegree(target VertexIndex) int
- func (m AdjacencyMatrix) Matrix() matrix.M[int]
- func (m AdjacencyMatrix) Outdegree(source VertexIndex) int
- func (m *AdjacencyMatrix) Resize(width int)
- func (m *AdjacencyMatrix) Set(source, target VertexIndex, count int)
- func (m AdjacencyMatrix) Vertexes() func() (VertexIndex, bool)
- func (m AdjacencyMatrix) Weight(source, target VertexIndex) Weight
- type BfsTree
- func (t *BfsTree) CalculateUnweighted(graph Iterator, start VertexIndex)
- func (t *BfsTree) CalculateWeightedGeneral(graph Iterator, start VertexIndex, weight WeightFunc)
- func (t *BfsTree) Clear()
- func (t BfsTree) Distance(vertex VertexIndex) (Weight, bool)
- func (t BfsTree) Edges(source VertexIndex) EdgeIterator
- func (t BfsTree) Predecessor(vertex VertexIndex) (VertexIndex, bool)
- func (t BfsTree) Reachable(vertex VertexIndex) bool
- func (t *BfsTree) Resize(n int)
- func (t BfsTree) Vertexes() VertexIterator
- type Decremental
- type DegreeMatrix
- func (m *DegreeMatrix) Calculate(g func() VertexIterator, degree func(index VertexIndex) int)
- func (m DegreeMatrix) Clear()
- func (m DegreeMatrix) CountEdges() int
- func (m DegreeMatrix) Get(source VertexIndex) int
- func (m DegreeMatrix) Matrix() matrix.M[int]
- func (m *DegreeMatrix) Resize(width int)
- func (m *DegreeMatrix) Set(source VertexIndex, count int)
- type Dynamic
- type EdgeIterator
- type FilterEdges
- type FilterVertexes
- type Incremental
- type Iterator
- type VertexIndex
- type VertexIterator
- type Weight
- type WeightFunc
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type AdjacencyMatrix ¶
type AdjacencyMatrix struct {
// contains filtered or unexported fields
}
AdjacencyMatrix represents the number of directed edges from a source vertex (along the x-axis) to a target vertex (along the y-axis), including self-loops, if any.
As a representation of a graph itself, AdjacencyMatrix implements the graph Iterator interface. As it can be updated incrementally, AdjacencyMatrix also implements the Dynamic interface.
func NewAdjacencyMatrix ¶
func NewAdjacencyMatrix() AdjacencyMatrix
NewAdjacencyMatrix returns an AdjacencyMatrix. Each vertex pair can only have one edge. For a multigraph, where vertex pairs can store a count of multiple edges, use NewMultiAdjacencyMatrix.
func NewMultiAdjacencyMatrix ¶ added in v2.16.0
func NewMultiAdjacencyMatrix() AdjacencyMatrix
NewMultiAdjacencyMatrix returns an AdjacencyMatrix. Each vertex pair can have a count of multiple edges. For a simple graph, where each vertex pair can have at most one edge, use NewAdjacencyMatrix.
func (*AdjacencyMatrix) Calculate ¶
func (m *AdjacencyMatrix) Calculate(g Iterator)
Calculate computes the adjacency matrix for a finite graph g. The created adjacency matrix is itself a graph implementing Iterator and Dynamic, containing only the vertexes of g with at least one inward or outward edge.
Each vertex index in the adjacency matrix corresponds to a matching index in graph g. Once an adjacency matrix has been constructed, it is not affected by future changes to graph g.
func (AdjacencyMatrix) Clear ¶
func (m AdjacencyMatrix) Clear()
func (AdjacencyMatrix) CountEdges ¶
func (m AdjacencyMatrix) CountEdges() int
CountEdges returns the total number of edges in the adjacency matrix.
func (AdjacencyMatrix) Degree ¶
func (m AdjacencyMatrix) Degree(source VertexIndex) int
Degree returns the number of edges either to or from a specific vertex, including self-loops which are counted (by definition) as two edges.
This is computed with O(n) complexity; construct a DegreeMatrix for constant time.
func (AdjacencyMatrix) Edges ¶
func (m AdjacencyMatrix) Edges(source VertexIndex) func() (VertexIndex, int, bool)
Edges implements the graph Iterator Edges method.
func (AdjacencyMatrix) Get ¶
func (m AdjacencyMatrix) Get(source, target VertexIndex) int
Get returns the number of directed edges from a source vertex to a target vertex (including self-loops, if any).
func (AdjacencyMatrix) Indegree ¶
func (m AdjacencyMatrix) Indegree(target VertexIndex) int
Indegree returns the number of directed edges from any vertex to the specific target vertex (including self-loops from the target to itself).
This is computed with O(n) complexity; construct a DegreeMatrix for constant time.
func (AdjacencyMatrix) Matrix ¶
func (m AdjacencyMatrix) Matrix() matrix.M[int]
Matrix returns a pointer to the underlying matrix.M (of type int). Note that if the matrix is resized, this value may become an old reference.
func (AdjacencyMatrix) Outdegree ¶
func (m AdjacencyMatrix) Outdegree(source VertexIndex) int
Outdegree returns the number of directed edges from a specific source vertex to any other vertex (including self-loops from the source to itself).
This is computed with O(n) complexity; construct a DegreeMatrix for constant time.
func (*AdjacencyMatrix) Resize ¶
func (m *AdjacencyMatrix) Resize(width int)
Resize updates the adjacency matrix, if necessary, so that it has at least capacity for width elements in each dimension.
func (*AdjacencyMatrix) Set ¶
func (m *AdjacencyMatrix) Set(source, target VertexIndex, count int)
Set stores the number of directed edges from a source vertex to a target vertex (including self-loops, if any).
THe matrix is automatically resized, if necessary.
func (AdjacencyMatrix) Vertexes ¶
func (m AdjacencyMatrix) Vertexes() func() (VertexIndex, bool)
Vertexes implements the graph Iterator Vertexes method. An AdjacencyMatrix is a graph of every vertex that has at least one edge (in either direction).
func (AdjacencyMatrix) Weight ¶ added in v2.16.0
func (m AdjacencyMatrix) Weight(source, target VertexIndex) Weight
Weight implements the graph Iterator Weight method. The weight of each edge in an adjacency matrix is defined as the number of edges from source to target in the input matrix (including self-loops, if any). If the graph is not a multigraph, this is always exactly one for any existing edge in the matrix.
type BfsTree ¶ added in v2.14.0
type BfsTree struct {
// contains filtered or unexported fields
}
BfsTree represents a (unweighted) breadth-first tree of the reachable graph from a given start vertex, taking the shortest number of edges.
A BfsTree is itself a graph (the predecessor subgraph of the graph it was constructed from), and implements the Iterator interface.
func NewBfsTree ¶ added in v2.14.0
func NewBfsTree() *BfsTree
NewBfsTree returns a new (empty) breadth-first search tree object for storing results.
func (*BfsTree) CalculateUnweighted ¶ added in v2.15.0
func (t *BfsTree) CalculateUnweighted(graph Iterator, start VertexIndex)
CalculateUnweighted computes an unweighted breadth-first tree of the reachable graph from a given start vertex, taking the shortest number of edges. This is equivalent to a weighted search where every edge has a unit weight of one. The resulting search tree has useful properties.
The search stores a result in the provided result object, resizing its underlying buffer if necessary.
There may be many possible breadth-first trees of an input graph. This procedure always visits vertexes in the order given by a graph's EdgeIterator.
func (*BfsTree) CalculateWeightedGeneral ¶ added in v2.15.0
func (t *BfsTree) CalculateWeightedGeneral( graph Iterator, start VertexIndex, weight WeightFunc, )
CalculateWeightedGeneral computes a weighted breadth-first tree of the reachable graph from a given start vertex, taking the shortest distance calculated as a cumulative sum of weights along a path. The resulting search tree has useful properties.
This search is performed in the "general case" where edges may have negative weights, but not negative-weight cycles. [CalculateWeighted] is more efficient, but does not support negative edge weights.
The search stores a result in the provided result object, resizing its underlying buffer if necessary.
There may be many possible breadth-first trees of an input graph. The order taken by this procedure, when two paths have the same weight, is arbitrary and subject to change.
func (BfsTree) Distance ¶ added in v2.14.0
func (t BfsTree) Distance(vertex VertexIndex) (Weight, bool)
Distance returns the cumulative number of edges crossed from the search start vertex to the given target. If the vertex is not reachable, the boolean return value is false.
func (BfsTree) Edges ¶ added in v2.15.0
func (t BfsTree) Edges(source VertexIndex) EdgeIterator
Edges implements the graph Iterator Edges method.
Each vertex has exactly one directed edge, to its predecessor, except the root vertex, which has none.
func (BfsTree) Predecessor ¶ added in v2.14.0
func (t BfsTree) Predecessor(vertex VertexIndex) (VertexIndex, bool)
Predecessor returns the predecessor of the vertex in the search tree. If the vertex is not reachable, or if the vertex is the search start vertex, the boolean return value is false.
func (BfsTree) Reachable ¶ added in v2.14.0
func (t BfsTree) Reachable(vertex VertexIndex) bool
Reachable returns true if the given vertex is reachable from the root of the BfsTree.
func (*BfsTree) Resize ¶ added in v2.14.0
Resize updates the BfsTree, if necessary, so that it has at least capacity for n vertexes. It reuses underlying memory from the existing tree where possible. Note that this will clear the tree.
func (BfsTree) Vertexes ¶ added in v2.14.0
func (t BfsTree) Vertexes() VertexIterator
Vertexes implements the graph Iterator Vertexes method.
type Decremental ¶ added in v2.16.0
type Decremental interface { RemoveVertex(VertexIndex) RemoveEdge(source VertexIndex, target VertexIndex) IncreaseWeight(source VertexIndex, weight Weight) }
Decremental is an interface for any dynamic graph implementation or online algorithm that can efficiently update to give a useful result if a graph changes by the removal of a vertex or edge, or if an edge weight increases.
Multiple related graph representations can be kept in-sync with TeeDecremental.
func TeeDecremental ¶ added in v2.16.0
func TeeDecremental(a, b Decremental) Decremental
TeeDecremental returns a new Decremental interface whose methods, when called, are also called on `a` and `b`. This can be used to keep two related graph implementations in sync with each-other.
type DegreeMatrix ¶
type DegreeMatrix struct {
// contains filtered or unexported fields
}
DegreeMatrix represents the number of edges on a vertex (to or from any other vertex in aggregate). This may be the in-, out-, or undirected-, degree.
Once built, a degree matrix can be queried in constant time.
Values are indexed by VertexIndex. A DegreeMatrix is a diagonal-matrix; values off the diagonal are zero.
func NewDegreeMatrix ¶
func NewDegreeMatrix() DegreeMatrix
NewDegreeMatrix returns a new degree matrix of undefined size.
func (*DegreeMatrix) Calculate ¶
func (m *DegreeMatrix) Calculate(g func() VertexIterator, degree func(index VertexIndex) int)
Calculate computes the degree matrix from any vertex iterator and any degree function.
For example, an in-, out-, or undirected degree matrix may be constructed from an AdjacencyMatrix using its Vertexes method and its Indegree, Outdegree, and Degree methods respectively.
Each vertex index in the degree matrix corresponds to the matching index in the input graph g. Once a degree matrix has been constructed, it is not affected by future changes to g.
func (DegreeMatrix) Clear ¶
func (m DegreeMatrix) Clear()
func (DegreeMatrix) CountEdges ¶
func (m DegreeMatrix) CountEdges() int
CountEdges returns the total number of edges in the degree matrix.
func (DegreeMatrix) Get ¶
func (m DegreeMatrix) Get(source VertexIndex) int
Get returns the (in-, out-, or undirected) degree of the given vertex.
func (DegreeMatrix) Matrix ¶
func (m DegreeMatrix) Matrix() matrix.M[int]
Matrix returns a pointer to the underlying matrix.M (of type int).
func (*DegreeMatrix) Resize ¶
func (m *DegreeMatrix) Resize(width int)
Resize updates the degree matrix, if necessary, so that it has at least capacity for width elements in each dimension.
func (*DegreeMatrix) Set ¶
func (m *DegreeMatrix) Set(source VertexIndex, count int)
Set stores the (in-, out-, or undirected) degree of the given vertex.
type Dynamic ¶ added in v2.16.0
type Dynamic interface { Incremental Decremental }
Dynamic is an interface for any dynamic graph implementation or online algorithm that can efficiently update to give a useful result if a graph changes.
Multiple related graph representations can be kept in-sync with TeeDynamic.
func TeeDynamic ¶ added in v2.16.0
TeeDynamic returns a new Dynamic interface whose methods, when called, are also called on `a` and `b`. This can be used to keep two related graph implementations in-sync with each-other.
type EdgeIterator ¶
type EdgeIterator = func() (target VertexIndex, count int, ok bool)
EdgeIterator is the type of a generator function that, for some particular source vertex, generates each target vertex connected by at least one directed edge, and a count of the number of edges between them. If the graph is not a multigraph, this count will always be one.
The last return value controls the iteration - if false, the iteration has finished and the other return values are not useful.
type FilterEdges ¶
type FilterEdges struct { Parent Iterator Filter func(source VertexIndex, target VertexIndex) bool }
FilterEdges implements the graph Iterator interface and represents a subgraph of a parent graph of only edges that satisfy the given filter function.
The Iterator implemented by FilterEdges is only a view of the parent graph and is computed on-the-fly as the parent changes.
func (FilterEdges) Edges ¶
func (f FilterEdges) Edges(source VertexIndex) EdgeIterator
func (FilterEdges) Vertexes ¶
func (f FilterEdges) Vertexes() VertexIterator
type FilterVertexes ¶
type FilterVertexes struct { Parent Iterator Filter func(vertex VertexIndex) bool }
FilterVertexes implements the graph Iterator interface and represents a subgraph of a parent graph of only vertexes that satisfy the given filter function.
The Iterator implemented by FilterVertexes is only a view of the parent graph and is computed on-the-fly as the parent changes.
func (FilterVertexes) Edges ¶
func (f FilterVertexes) Edges(source VertexIndex) EdgeIterator
func (FilterVertexes) Vertexes ¶
func (f FilterVertexes) Vertexes() VertexIterator
type Incremental ¶ added in v2.16.0
type Incremental interface { AddVertex(VertexIndex) AddEdge(source VertexIndex, target VertexIndex) DecreaseWeight(source VertexIndex, weight Weight) }
Incremental is an interface for any dynamic graph implementation or online algorithm that can efficiently update to give a useful result if a graph changes by the addition of a vertex or edge, or if an edge weight decreases.
Multiple related graph representations can be kept in-sync with TeeIncremental.
func TeeIncremental ¶ added in v2.16.0
func TeeIncremental(a, b Incremental) Incremental
TeeIncremental returns a new Incremental interface whose methods, when called, are also called on `a` and `b`. This can be used to keep two related graph implementations in sync with each-other.
Multiple related graph representations can be kept in-sync with TeeIncremental.
type Iterator ¶
type Iterator interface { Vertexes() VertexIterator Edges(source VertexIndex) EdgeIterator Weight(source, target VertexIndex) Weight }
Iterator is the basic interface that a graph data type must implement to be able to use many of the algorithms in this package.
A graph can have many equivalent implementations: a data structure, perhaps an adjacency list or an adjacency matrix; or an algorithm. The mapping between this general-purpose graph interface and a given graph implementation is achieved through two iterator-style functions.
Graphs may contain cycles, loops, be disjoint, be multigraphs, etc. without restriction except where noted. In general, algorithms in this package operate on finite graphs only.
Edges are directed, but an undirected graph can always be implemented efficiently from a directed graph - e.g. from its adjacency matrix.
The Weight method calculates a weight of the edge between source and target. In the case of a multigraph, multiple edges must be reduced by some appropriate method e.g. by picking the minimum edge weight, by calculating the sum of edge weights, or by the count of edges, etc. Algorithms will only call Weight if a directed edge already exists from the source to the target vertex, so it is not necessary to validate the arguments again. If the graph is unweighted, you can return a unit Weight of 1.
type VertexIndex ¶
type VertexIndex int
VertexIndex is a non-negative index that uniquely identifies each vertex in a graph. Vertex indexes do not have to be consecutive or sorted, may be sparse, and do not have to start at zero, but it may be more efficient where that is the case.
Many algorithms in this package will have computational complexity proportionate to the maximum VertexIndex, and require memory proportionate to the maximum VertexIndex squared.
The optimum assignment of a VertexIndex to each vertex is called the Minimum Linear Arrangement, but in the general case this is NP-Hard and even an approximation has quadratic complexity. You can get decent results just using the indexes of a generational array (see the `genarray` sibling package).
type VertexIterator ¶
type VertexIterator = func() (vertex VertexIndex, ok bool)
VertexIterator is the type of a generator function that, for some particular graph, generates a VertexIndex for each vertex in the graph.
The last return value controls the iteration - if false, the iteration has finished and the other return value is not useful.
func Leaves ¶
func Leaves( vertexes func() VertexIterator, indegree func(VertexIndex) int, outdegree func(VertexIndex) int, ) VertexIterator
Leaves returns an iterator that generates indexes of vertexes that have exactly one parent and exactly zero children in a directed graph.
A degree function can be made by passing an appropriate method from an AdjacencyMatrix or DegreeMatrix.
func Roots ¶
func Roots( vertexes func() VertexIterator, indegree func(VertexIndex) int, ) VertexIterator
Roots returns an iterator that generates only the indexes of vertexes that have no parents i.e. root vertexes in a directed graph.
A degree function can be made by passing an appropriate method from an AdjacencyMatrix or DegreeMatrix.
type Weight ¶ added in v2.15.0
type Weight int
Weight represents the "cost" of a weighted edge from one vertex to another. Weights may be negative, except where indicated by certain algorithms.
Real number (floating point) weights should be scaled to an integer range, for example by multiplying by some constant and rounding.
type WeightFunc ¶ added in v2.15.0
type WeightFunc func(source, target VertexIndex) Weight
WeightFunc is the type of a function that gives a weight between two vertexes in a graph. Algorithms will only call this if a directed edge already exists from the source to the target vertex, so it is not necessary to validate the arguments again.