digraph

package
v2.8.2 Latest Latest
Warning

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

 Go to latest Published: Feb 17, 2023 License: MIT Imports: 4 Imported by: 0

Documentation

Overview

Package digraph implements a directed graph (a "digraph") and related operations.

Many of the algorithms and definitions are thanks to CLRS "Introduction to Algorithms", 3rd edition.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func InfWeight 

func InfWeight[N Number, S Number](sign S) N

InfWeight returns an "infinite" value for a weight of a given type, with a given sign (i.e. positive or negative infinity). For signed integer values, this is the largest and smallest possible values. For unsigned integer values, this is the largest possible value minus one (for positive infinity) and the largest possible value (for negative infinity). For floating point values, this is the appropriate floating-point infinity from math.Inf.

func MaxWeight 

func MaxWeight[N Number]() N

MaxWeights returns a maximum value for a weight of a given type. Useful for e.g. the initial value in a `min` reducer function. Not to be confused with the InfWeight function.

Types

type AdjacencyMatrix 

type AdjacencyMatrix = Matrix[DistanceT]

type BFSResult 

type BFSResult[VertexT any, EdgeT any, WeightT Number] struct {
	// contains filtered or unexported fields
}

BFSResult is the annotated result of a breadth-first search

Changing the structure of a graph, such as sorting, adding, or removing vertexes and edges, changing edge weights (for a weighted search),or changing edge values (for a search constructed using a filter) will invalidate the search result.

func (*BFSResult[V, E, W]) Distance 

func (bfs *BFSResult[V, E, W]) Distance(v *Vertex[V, E, W]) DistanceT

Distance returns the distance of the shortest path from the source vertex to the given destination vertex, using the result of a breadth-first search from the source vertex as an input, in terms of the number of edges crossed (i.e. NOT the weighted distance). If the search was weighted this may not be the shortest path in terms of edges, but is instead the number of edges on the shortest path by distance. If no path exists, the distance is infinite (represented by [maths.MaxInt32]) - see Digraph.IsInfiniteDistance.

func (*BFSResult[V, E, W]) Predecessor 

func (bfs *BFSResult[V, E, W]) Predecessor(v *Vertex[V, E, W]) *Vertex[V, E, W]

Predecessor returns, from a search starting at the source vertex (forming a breadth-first search tree), the parent of a given vertex. If the given vertex is not reachable from search, returns nil. If the given vertex is the source vertex (and has no predecessor), returns nil.

func (*BFSResult[V, E, W]) ShortestPath 

func (bfs *BFSResult[V, E, W]) ShortestPath(
	result []*Vertex[V, E, W],
	v *Vertex[V, E, W],
) []*Vertex[V, E, W]

ShortestPath returns a list of the vertexes along the shortest path from the source vertex to the given destination vertex, using the result of a breadth-first search from the source vertex as an input. If the search was a weighted search, the shortest path is a path with the smallest weight. Otherwise, the shortest path is the path with the fewest number of edges.

Multiple shortest paths may exist, so if you want a specific ordering, see the notes on Digraph.BreadthFirstSearch. Every vertex is reachable by itself with a path of zero edges, so if `a == b`, then the shortest path is simply a list containing only vertex `a`. Every valid path will begin with `a` and end with `b`. If no path exists, the result will be an empty list (not nil).

The function stores the vertexes encountered in the provided result object, resizes the underlying buffer if necessary, and returns that result object (or, if nil, creates and returns a new result object).

func (*BFSResult[V, E, W]) WeightedDistance 

func (bfs *BFSResult[V, E, W]) WeightedDistance(v *Vertex[V, E, W]) W

WeightedDistance returns the distance of the shortest path from the source vertex to the given destination vertex, in terms of the minimum weight, using the result of a breadth-first search from the source vertex as an input. If no path exists, or if the search was not weighted, the distance is infinite ([Digraph.IsInfiniteWeight] returns true).

type DAGSearchResult 

type DAGSearchResult[VertexT any, EdgeT any, WeightT Number] struct {
	// contains filtered or unexported fields
}

DAGSearchResult is the annotated result of a directed acyclic graph (a DAG).

Changing the structure of a graph, such as sorting, adding, or removing vertexes and edges, changing edge weights (for a weighted search),or changing edge values (for a search constructed using a filter) will invalidate the search result.

func (*DAGSearchResult[V, E, W]) ShortestPath 

func (dags *DAGSearchResult[V, E, W]) ShortestPath(
	result []*Vertex[V, E, W],
	v *Vertex[V, E, W],
) []*Vertex[V, E, W]

ShortestPath returns a list of the vertexes along the shortest path from the source vertex to the given destination vertex, using the result of a DAG search from the source vertex as an input. If the search was a weighted search, the shortest path is a path with the smallest weight. Otherwise, the shortest path is the path with the fewest number of edges.

Multiple shortest paths may exist, so if you want a specific ordering, use Digraph.SortRoots or Digraph.SortEdges. Every vertex is reachable by itself with a path of zero edges, so if `a == b`, then the shortest path is simply a list containing only vertex `a`. Every valid path will begin with `a` and end with `b`. If no path exists, the result will be an empty list (not nil).

The function stores the vertexes encountered in the provided result object, resizes the underlying buffer if necessary, and returns that result object (or, if nil, creates and returns a new result object).

type DFSResult 

type DFSResult[VertexT any, EdgeT any, WeightT Number] struct {
	// contains filtered or unexported fields
}

DFSResult is the annotated result of a depth first search.

Changing the structure of a graph, such as sorting, adding, or removing vertexes and edges, changing edge weights (for a weighted search),or changing edge values (for a search constructed using a filter) will invalidate the search result.

func (*DFSResult[V, E, W]) TopologicalSort 

func (dfs *DFSResult[V, E, W]) TopologicalSort(result []*Vertex[V, E, W]) []*Vertex[V, E, W]

TopologicalSort returns the vertexes in topological ordering, using the result of a depth-first search as an input. Multiple topological orderings may exist, so if you want a specific ordering, see the notes on Digraph.DepthFirstSearch. Note that only acyclic digraphs (DAGs) have a valid topological sort (see Digraph.ContainsCycles). This function may panic if the input graph contains cycles.

It stores the topological ordering of vertexes in the provided result object, resizes the underlying buffer if necessary, and returns that result object (or, if nil, creates and returns a new result object).

type Digraph 

type Digraph[VertexT any, EdgeT any, WeightT Number] struct {
	Vertexes []*Vertex[VertexT, EdgeT, WeightT]
	// contains filtered or unexported fields
}

A Digraph is a directed graph of vertexes and (directed) edges.

The graph may be disconnected (a disjoint union of disconnected subgraphs) or connected, may be a multigraph/multidigraph (may have more than one edge between the same two vertices) or a simple graph, may be weighted (with any Number type) or unweighted, may contain loops or may not permit loops, may contain cycles or be acyclic.

Properties of the graph, such as whether it contains cycles, can be queried e.g. to assert that the graph is a valid directed acyclic graph (DAG).

If the edges do not store a value, use EdgeT EdgeDontCare. If the graph is unweighted, use WeightT WeightDontCare.

func New 

func New[VertexT any, EdgeT any, WeightT Number]() *Digraph[VertexT, EdgeT, WeightT]

func (*Digraph[V, E, W]) AddEdge 

func (d *Digraph[V, E, W]) AddEdge(from *Vertex[V, E, W], to *Vertex[V, E, W], value E)

AddEdge creates a new edge between two vertexes in the graph, holding the arbitrary user-supplied value.

func (*Digraph[V, E, W]) AddUniqueEdge 

func (d *Digraph[V, E, W]) AddUniqueEdge(
	from *Vertex[V, E, W],
	to *Vertex[V, E, W],
	value E,
) bool

AddUniqueEdge creates a new edge between two vertexes in the graph, holding the arbitrary user-supplied value, if that edge does not already exist, and returns true. Otherwise, if the edge already exists, returns false and does nothing.

func (*Digraph[V, E, W]) AddUniqueEdgeFiltered 

func (d *Digraph[V, E, W]) AddUniqueEdgeFiltered(
	from *Vertex[V, E, W],
	to *Vertex[V, E, W],
	value E,
	equal func(a *E, b *E) bool,
) bool

AddUniqueEdgeFiltered behaves as AddUniqueEdge, however an edge is only deemed to be unique if the provided equality function returns false for the new edge value and the existing edge value.

func (*Digraph[V, E, W]) AddUniqueWeightedEdge 

func (d *Digraph[V, E, W]) AddUniqueWeightedEdge(
	from *Vertex[V, E, W],
	to *Vertex[V, E, W],
	value E,
	weight W,
) bool

AddUniqueWeightedEdge creates a new edge between two vertexes in the graph, holding the arbitrary user-supplied value, and with a given weight, if that edge does not already exist, and returns true. Otherwise, if the edge already exists, returns false and does nothing.

func (*Digraph[V, E, W]) AddUniqueWeightedEdgeFiltered 

func (d *Digraph[V, E, W]) AddUniqueWeightedEdgeFiltered(
	from *Vertex[V, E, W],
	to *Vertex[V, E, W],
	value E,
	weight W,
	equal func(a *E, b *E) bool,
) bool

AddUniqueWeightedEdgeFiltered behaves as AddUniqueWeightedEdge, however an edge is only deemed to be unique if the provided equality function returns false for the new edge value and the existing edge value. Weights are ignored for the purposes of uniqueness.

func (*Digraph[V, E, W]) AddVertex 

func (d *Digraph[V, E, W]) AddVertex(value V) *Vertex[V, E, W]

AddVertex creates a new vertex in the graph, holding the arbitrary user-supplied value, and returns a pointer that identifies that vertex in the graph.

func (*Digraph[V, E, W]) AddWeightedEdge 

func (d *Digraph[V, E, W]) AddWeightedEdge(from *Vertex[V, E, W], to *Vertex[V, E, W], value E, weight W)

AddWeightedEdge creates a new edge between two vertexes in the graph, holding the arbitrary user-supplied value, and with a given weight.

func (*Digraph[V, E, W]) Adjacency 

func (d *Digraph[V, E, W]) Adjacency(
	mat *AdjacencyMatrix,
	a *Vertex[V, E, W],
	b *Vertex[V, E, W],
) int

Adjacency returns the number of edges pointing from a to b (where a and b are adjacent, or a == b). In a simple graph, this is always zero or one. In a multigraph, it could be zero or any positive number.

func (*Digraph[V, E, W]) AdjacencyMatrix 

func (d *Digraph[V, E, W]) AdjacencyMatrix(mat *AdjacencyMatrix) *AdjacencyMatrix

AdjacencyMatrix calculates the number of directed edges between each adjacent vertex, stores this in the provided matrix buffer, resizes the underlying buffer if necessary, and returns that matrix (or, if nil, creates and returns a new matrix).

func (*Digraph[V, E, W]) AdjacencyMatrixFiltered 

func (d *Digraph[V, E, W]) AdjacencyMatrixFiltered(
	mat *AdjacencyMatrix,
	filter func(e *E) bool,
) *AdjacencyMatrix

AdjacencyMatrixFiltered behaves as AdjacencyMatrix except that it only considers edges where the provided function, which operates on the value of the edge, returns true.

func (*Digraph[V, E, W]) BreadthFirstSearch 

func (d *Digraph[V, E, W]) BreadthFirstSearch(
	bfs *BFSResult[V, E, W],
	start *Vertex[V, E, W],
	maxDepth DistanceT,
	visitVertex func(*Vertex[V, E, W]),
) *BFSResult[V, E, W]

BreadthFirstSearch performs a complete search of the reachable graph from a given start vertex, taking the shortest number of edges. The resulting search tree gives useful properties.

The search stores a result in the provided result object, resizing its underlying buffer if necessary, and returns that result object (or, if nil, creates and returns a new result object). Use the same result object across multiple searches to minimise memory allocations.

If you want a specific ordering of vertexes visited by the search, use Digraph.SortRoots and Digraph.SortEdges first.

The visitVertex callback function is called when each vertex is first visited in the search. If nil, it is ignored.

Computed vertex distances from source, in terms of the number of edges crossed, are of type int32. If maxDepth is greater than zero, the search excludes any vertex with a distance greater than maxDepth.

If the graph is modified, the resulting search is no longer valid and must not be queried.

func (*Digraph[V, E, W]) BreadthFirstSearchWeightedGeneral 

func (d *Digraph[V, E, W]) BreadthFirstSearchWeightedGeneral(
	bfs *BFSResult[V, E, W],
	start *Vertex[V, E, W],
) (*BFSResult[V, E, W], bool)

BreadthFirstSearchWeightedGeneral performs a complete search of the reachable graph from a given start vertex, calculating the shortest path by weight (distance). The resulting search tree gives useful properties. It stores this in the provided result object, resizes the underlying buffer if necessary, and returns that result object (or, if nil, creates and returns a new result object).

This search is performed in the "general case" where edges may have negative weights, but not negative-weight cycles. When the boolean return value is false, the search has detected negative-weight cycles and cannot proceed.

If you are certain that the graph does not contain edges with negative weights, then the alternative method [Digraph.WeightedSearch] is likely to be faster.

If you want a specific ordering of vertexes visited by the search, use Digraph.SortRoots and Digraph.SortEdges first.

func (*Digraph[V, E, W]) ContainsCycles 

func (d *Digraph[V, E, W]) ContainsCycles(dfs *DFSResult[V, E, W]) bool

ContainsCycles returns true if there exists any directed cycle (i.e. any path between a vertex and itself). If false, the digraph is a directed acyclic graph (DAG). A completed depth-first search of the graph is used as input to do this efficiently.

func (*Digraph[V, E, W]) ContainsLoops 

func (d *Digraph[V, E, W]) ContainsLoops(mat *AdjacencyMatrix) bool

ContainsLoops returns true if there is any edge that connects a vertex to itself. A completed adjacency matrix is used as input to do this efficiently.

func (*Digraph[V, E, W]) DAGSearchWeighted 

func (d *Digraph[V, E, W]) DAGSearchWeighted(
	dags *DAGSearchResult[V, E, W],
	start *Vertex[V, E, W],
	topologicalSort []*Vertex[V, E, W],
) *DAGSearchResult[V, E, W]

DAGSearchWeighted performs an "annotated" search of a weighted directed acyclic graph (a weighted DAG) from some root node, which gives useful properties. It stores this in the provided result object, resizes the underlying buffer if necessary, and returns that result object (or, if nil, creates and returns a new result object).

The topologicalSort input is an ordering of the vertexes in topological order (see DFSResult.TopologicalSort).

func (*Digraph[V, E, W]) DepthFirstSearch 

func (d *Digraph[V, E, W]) DepthFirstSearch(
	dfs *DFSResult[V, E, W],

) *DFSResult[V, E, W]

DepthFirstSearch performs a complete "annotated" search of the graph, which gives useful properties. It stores this in the provided result object, resizes the underlying buffer if necessary, and returns that result object (or, if nil, creates and returns a new result object).

If you want a specific ordering of vertexes visited by the search, use Digraph.SortRoots and Digraph.SortEdges first.

func (*Digraph[V, E, W]) DistanceMatrix 

func (d *Digraph[V, E, W]) DistanceMatrix(mat *Matrix[int]) *Matrix[W]

DistanceMatrix returns the distance TODO

The returned Matrix is no longer current if the graph has been modified by adding, changing, or removing vertexes, edges, or their weights or values.

func (*Digraph[V, E, W]) DistanceMatrixFiltered 

func (d *Digraph[V, E, W]) DistanceMatrixFiltered(mat *Matrix[int]) *Matrix[W]

func (*Digraph[V, E, W]) FindEdge 

func (d *Digraph[V, E, W]) FindEdge(
	from *Vertex[V, E, W],
	to *Vertex[V, E, W],
) *Edge[V, E, W]

FindEdge returns an edge, if any, between two adjacent vertexes. Otherwise, returns nil. If multiple edges exist between the two vertexes, the specific edge returned is arbitrary.

If an adjacency matrix has been constructed, and you only want to know if an edge exists and not to find the actual edge, it is more efficient to use the Digraph.Adjacency method.

func (*Digraph[V, E, W]) FindEdgeFiltered 

func (d *Digraph[V, E, W]) FindEdgeFiltered(
	from *Vertex[V, E, W],
	to *Vertex[V, E, W],
	f func(e *E) bool,
) *Edge[V, E, W]

FindEdgeFiltered returns an edge between two adjacent vertexes if it exists and only if the provided function, which operates on the value of the edge, returns true. Otherwise, returns nil. If multiple matching edges exist between the two vertexes, the specific edge returned is arbitrary.

It can be more efficient to construct and reuse a filtered adjacency matrix and use the Digraph.Adjacency method instead in cases where you only want to know if an edge exists and not to find the actual edge.

func (*Digraph[V, E, W]) Indegree 

func (d *Digraph[V, E, W]) Indegree(mat *AdjacencyMatrix, v *Vertex[V, E, W]) int

Indegree returns the number of edges pointing to the given vertex.

func (*Digraph[V, E, W]) Inputs 

func (d *Digraph[V, E, W]) Inputs(
	mat *AdjacencyMatrix,
	result Path[V, E, W],
	v *Vertex[V, E, W],
) Path[V, E, W]

Inputs returns the adjacent vertexes and edges pointing to the given vertex. It stores this in the provided result object, resizes the underlying buffer if necessary, and returns that result object (or, if nil, creates and returns a new result object).

func (*Digraph[V, E, W]) IsComplete 

func (d *Digraph[V, E, W]) IsComplete() bool

IsComplete returns true if there is exactly one directed edge between every possible vertex pair in each direction. For any pair (u,v), u has a directed edge to v, and v has a directed edge to u.

func (*Digraph[V, E, W]) IsFiniteDistance 

func (d *Digraph[V, E, W]) IsFiniteDistance(e DistanceT) bool

IsFiniteDistance returns true if a distance (in terms of number of edges) is finite, representing a reachable vertex.

func (*Digraph[V, E, W]) IsFiniteWeightedDistance 

func (d *Digraph[V, E, W]) IsFiniteWeightedDistance(w W) bool

IsFiniteWeightedDistance returns true if a weighted distance (in terms of a sum of weights along edges) is finite, representing an reachable vertex.

func (*Digraph[V, E, W]) IsForest 

func (d *Digraph[V, E, W]) IsForest() bool

IsForest returns true if for any two vertexes there is at most one undirected path between them, or (equivalently) the graph is a disjoint union of trees (the graph is said to be a "directed forest" or polyforest) i.e. every node with no parent is the root node of an individual tree.

func (*Digraph[V, E, W]) IsInfiniteDistance 

func (d *Digraph[V, E, W]) IsInfiniteDistance(e DistanceT) bool

IsInfiniteDistance returns true if a distance (in terms of number of edges) is infinite, representing an unreachable vertex.

func (*Digraph[V, E, W]) IsInfiniteWeightedDistance 

func (d *Digraph[V, E, W]) IsInfiniteWeightedDistance(w W) bool

IsInfiniteWeightedDistance returns true if a weighted distance (in terms of a sum of weights along edges) is infinite, representing an unreachable vertex.

func (*Digraph[V, E, W]) IsSimple 

func (d *Digraph[V, E, W]) IsSimple(mat *AdjacencyMatrix) bool

IsSimple returns true if for any two vertexes there is at most one edge (in the same direction) between them. If false, the digraph is a multigraph/multidigraph. A completed adjacency matrix is used as input to do this efficiently.

func (*Digraph[V, E, W]) IsStronglyConnected 

func (d *Digraph[V, E, W]) IsStronglyConnected() bool

IsStronglyConnected returns true if there is at least one directed path between every possible vertex pair (in both directions). A graph with just one vertex is always connected.

func (*Digraph[V, E, W]) IsTournament 

func (d *Digraph[V, E, W]) IsTournament() bool

IsTournament returns true if there is exactly one directed edge between every possible vertex pair in either direction. For any pair (u,v), either u has a // directed edge to v, or v has a directed edge to u, but not both.

func (*Digraph[V, E, W]) IsTree 

func (d *Digraph[V, E, W]) IsTree() bool

IsTree returns true if for any two vertexes there is exactly one undirected path between them (the graph is said to be a "directed tree" or polytree). Alternatively, each vertex has exactly one parent, except for the root (which has no parent).

func (*Digraph[V, E, W]) IsWeaklyConnected 

func (d *Digraph[V, E, W]) IsWeaklyConnected() bool

IsWeaklyConnected returns true if there is at least one undirected path between every possible vertex pair. A graph with just one vertex is always connected.

func (*Digraph[V, E, W]) Outdegree 

func (d *Digraph[V, E, W]) Outdegree(mat *AdjacencyMatrix, v *Vertex[V, E, W]) int

Outdegree returns the number of edges pointing away from the given vertex.

func (*Digraph[V, E, W]) Roots 

func (d *Digraph[V, E, W]) Roots(
	mat *AdjacencyMatrix,
	result []*Vertex[V, E, W],
) []*Vertex[V, E, W]

Roots returns all vertexes in the graph with no parents. It stores this in the provided result object, resizes the underlying buffer if necessary, and returns that result object (or, if nil, creates and returns a new result object).

func (*Digraph[V, E, W]) SortEdges 

func (d *Digraph[V, E, W]) SortEdges(
	lessThan func(*Vertex[V, E, W], *Edge[V, E, W], *Edge[V, E, W]) bool,
)

SortEdges performs an in-place stable sort of each vertex's edge. This can be used to achieve a specific ordering for searches.

The function lessThan defines an ordering by returning true if an edge on the vertex comes before another edge on that vertex.

Sorting edges does not change vertex IDs.

func (*Digraph[V, E, W]) SortRoots 

func (d *Digraph[V, E, W]) SortRoots(
	adjacencyMatrix *AdjacencyMatrix,
	lessThan func(*Vertex[V, E, W], *Vertex[V, E, W]) bool,
)

SortRoots performs an in-place stable sort of the graph's vertexes such that root vertexes (if any) appear before non-root vertexes, and the root vertexes are sorted by the comparison function lessThan. This can be used to achieve a specific ordering for searches or topological sorts.

Note that this can change vertex IDs (see VertexID) and therefore invalidates any existing calculated matrix, path, search result of the graph etc., including the input matrix when this method returns.

The function lessThan defines an ordering by returning true if a vertex comes before another. It is only applied to root vertexes.

func (*Digraph[V, E, W]) WeightedAdjacency 

func (d *Digraph[V, E, W]) WeightedAdjacency(
	mat *Matrix[W],
	a *Vertex[V, E, W],
	b *Vertex[V, E, W],
) W

WeightedAdjacency returns the weighted distance from a to b (where a and b are adjacent, or a == b), using the weighted adjacency matrix mat. In a simple graph, this is always either the weight of exactly one edge, or infinity if there is no directed edge from a to b.

In a multigraph, it is always either the weight calculated by the reducer function used to generate the weighted adjacency matrix (such as minimum weight, or sum of weights), or infinity if there is no directed edge from a to b.

func (*Digraph[V, E, W]) WeightedAdjacencyMatrix 

func (d *Digraph[V, E, W]) WeightedAdjacencyMatrix(
	mat *Matrix[W],
	reducer *EdgeWeightReducer[W],
) *Matrix[W]

WeightedAdjacencyMatrix calculates the weights of edges between each adjacent vertex, stores this in the provided matrix buffer, resizes the underlying buffer if necessary, and returns that matrix (or, if nil, creates and returns a new matrix).

In the case of a multigraph (multiple edges between two vertexes), the provided reducer is used to reduce multiple weights into a single value. For example, sum all weights, or return the minimum weight. If you are certain that the graph is not a multigraph (i.e. is simple), then the reducer may be nil.

func (*Digraph[V, E, W]) WeightedAdjacencyMatrixFiltered 

func (d *Digraph[V, E, W]) WeightedAdjacencyMatrixFiltered(
	mat *Matrix[W],
	reducer *EdgeWeightReducer[W],
	filter func(e *E) bool,
) *Matrix[W]

WeightedAdjacencyMatrixFiltered behaves as [WeightedAdjacencyMatrix] except that it only considers edges where the provided filter function, which operates on the value of the edge, returns true.

func (*Digraph[V, E, W]) WeightedDistanceMatrix 

func (d *Digraph[V, E, W]) WeightedDistanceMatrix(mat *Matrix[int]) *Matrix[W]

func (*Digraph[V, E, W]) WeightedDistanceMatrixFiltered 

func (d *Digraph[V, E, W]) WeightedDistanceMatrixFiltered(mat *Matrix[int]) *Matrix[W]

type DistanceMatrix 

type DistanceMatrix = Matrix[DistanceT]

type DistanceT 

type DistanceT int

DistanceT is the type of distance in terms of number of edges (this is not a weighted distance, which is instead the graph WeightT type).

type Edge 

type Edge[VertexT any, EdgeT any, WeightT Number] struct {
	Value  EdgeT
	Weight WeightT
	Target *Vertex[VertexT, EdgeT, WeightT]
}

Edge represents a directed connection from a source vertex to a target vertex. The vertex stores a value of type VertexT.

This edge may optionally have an arbitrary user-supplied value associated with it of type EdgeT, and an arbitrary numerical weight (such as a distance in metres, or a cost in pounds sterling) of type WeightT. If the edge does not store a value, use EdgeT EdgeDontCare. If the edge does not store a weight, use WeightT WeightDontCare.

A path, as opposed to a connection, is a list of vertexes and edges from a source vertex to a target vertex, including all vertexes and edges passed on the way. A path has both a distance in terms of number of edges crossed and a weighted distance in terms of the sum of edge weights crossed.

Edge values are stored directly in the edge. Use a pointer type where appropriate to avoid copying. There is no useful zero value for an Edge.

type EdgeDontCare 

type EdgeDontCare = any

EdgeDontCare represents the type for an edge value when you don't care what that type is (because edges in your graph do not have values).

type EdgeWeightReducer 

type EdgeWeightReducer[W Number] struct {
	Identity W
	Reduce   func(W, W) W
}

EdgeWeightReducer defines a method to reduce multiple edge weights into a single weight. This can be the case in a multigraph/multidigraph.

The Reduce function is applied left-to-right on a vertex's edges. For a given ordering, see Digraph.SortEdges. The first argument to the first invocation of the reducer is the provided Identity value (i.e. for sum, this is zero. For multiply, this is one).

func NewEdgeWeightReducerMaximum 

func NewEdgeWeightReducerMaximum[W Number]() *EdgeWeightReducer[W]

NewEdgeWeightReducerMaximum returns an edge reducer that reduces a list of edge weights of type W to a maximum value.

func NewEdgeWeightReducerMinimum 

func NewEdgeWeightReducerMinimum[W Number]() *EdgeWeightReducer[W]

NewEdgeWeightReducerMinimum returns an edge reducer that reduces a list of edge weights of type W to a minimum value.

func NewEdgeWeightReducerSum 

func NewEdgeWeightReducerSum[W Number]() *EdgeWeightReducer[W]

NewEdgeWeightReducerSum returns an edge reducer that reduces a list of edge weights of type W to the sum of those weights.

type Matrix 

type Matrix[T Number] struct {
	// contains filtered or unexported fields
}

Matrix is a two-dimensional array of values, such as a graph's adjacency matrix (with values of type VertexID), weighted adjacency matrix (with values of type WeightT), or weighted distance matrix (also with values of type WeightT).

Changing the structure of a graph, such as sorting, adding, or removing vertexes and edges, changing edge weights (for a weighted matrix),or changing edge values (for a matrix constructed using a filter) will invalidate the matrix.

type Number 

type Number interface {
	constraints.Integer | constraints.Float
}

type Path 

type Path[VertexT any, EdgeT any, WeightT Number] []PathVertex[VertexT, EdgeT, WeightT]

Path is an ordered list of zero or more PathVertexes making up a path. A Path can be empty, but is never nil.

type PathVertex 

type PathVertex[VertexT any, EdgeT any, WeightT Number] struct {
	Vertex *Vertex[VertexT, EdgeT, WeightT]
	Via    *Edge[VertexT, EdgeT, WeightT]
}

PathVertex is a tuple of a vertex and the edge it was reached from when calculating a path.

type Vertex 

type Vertex[VertexT any, EdgeT any, WeightT Number] struct {
	Value VertexT
	Edges []Edge[VertexT, EdgeT, WeightT]
	// contains filtered or unexported fields
}

Vertex represents an object in a digraph.

This vertex has zero-or-more directed edges to a target vertex (if the graph permits loops, this includes directed edges to itself). In the case of a multidigraph, there may exist multiple directed edges linking the same two vertexes.

The vertex has an arbitrary user-supplied value associated with it of type VertexT, If the edges do not store a value, use EdgeT EdgeDontCare. If the edges do not store a weight, use WeightT WeightDontCare.

Vertex values are stored directly in the vertex. Use a pointer type where appropriate to avoid copying. There is no useful zero value for a Vertex.

func (*Vertex[V, E, W]) ID 

func (v *Vertex[V, E, W]) ID() VertexID

ID returns the current index of a vertex in a graph (see VertexID).

type VertexID 

type VertexID int32

VertexID is the type of the index of a vertex in a graph (see Vertex.ID).

For any i, where 0 <= i < len(Digraph.Vertexes[i]), Digraph.Vertexes[i].ID() == i.

Vertex IDs may change when a graph is sorted (using Digraph.SortRoots), when new vertexes are added, and when vertexes are removed.

type WeightDontCare 

type WeightDontCare = int

WeightDontCare represents the type for an edge weight when you don't care what that type is (because edges in your graph do not have weights).

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.