Documentation ¶
Overview ¶
Package groph is a pure Go library for graph data and algorithms.
It provides an abstract graph model through some interfaces described below, a set of different implementations for those graph models—there is no onesizefitsall implementation—and graph algorithms provided in sub packages.
Vertices are always represented by an integer value of type VIdx ranging from 0 to n1 for graphs with n vertices. Mapping different vertex types to the VIdx values for groph is currently left to the user. Edges are associated with values called “weights” which is a useful feature for most graph algorithms. A simple, unweighted graph can be considered to have weights of type bool that represent whether an edged is in the graph.
The graph interfaces ¶
The graph interfaces are grouped by some specific aspects:
 Graph implementations can be readonly and readwrite.
 Graph implementations are for directed or undirected graphs.
 Values associated with edges can be general, i.e. of type interface{}, or have some specific type.
The most basic is the RGraph interface that allows readonly access to directed and undirected graphs with no specific edge type. The WGraph interface extends RGraph with methods to change edges in the graph.
The variants of RGraph and WGraph for undirected graphs are RUndirected and WUndirected. Any specific graph that does not implement RUndirected is considered to be a directed graph. One can use the Directed() function to just distinguish directed and undirected at runtime. To also downcast to undirected graphs use standard Go features.
More specific interfaces are derived from these interfaces and adhere to the following naming convention. The first letter is either 'R' or 'W' to indicate readonly respectively readwrite graphs. The second letter is either 'G' or 'U' to distinguish general graph interfaces from undirected interfaces. Finally comes an indicator for the edge weights, e.g. “i32” for int32 or “f32” for float32 or “bool” for just bool.
Index ¶
 Constants
 func Clipped(err error) int
 func Copy[W any](dst WGraph[W], src RGraph[W]) error
 func CopyX[V, W any](dst WGraph[V], src RGraph[W], x func(W) (V, error)) error
 func Del[W any](g WGraph[W], vs ...VIdx)
 func Set[W any](g WGraph[W], w W, vs ...VIdx)
 type ClipError
 type RDirected
 type RGraph
 type RUndirected
 type SrcDstError
 type UVError
 type VIdx
 type VisitEdge
 type VisitEdgeW
 type VisitVertex
 type WDirected
 type WGraph
 type WUndirected
Constants ¶
const (
IntNoEdge int = minInt
)
const Stopped stop = 0
Variables ¶
This section is empty.
Functions ¶
func Clipped ¶ added in v0.6.0
Clipped returns the clipping if err is a ClipError. Otherwise it returns 0.
Types ¶
type ClipError ¶ added in v0.6.0
type ClipError int
ClipError is returned when the order of src and dst in Cp*Weights does not match. If err is < 0 there were err vertices ignored from src. If err > 0 then err vertices in dst were not covered.
type RDirected ¶ added in v0.6.0
type RDirected[W any] interface { RGraph[W] // OutDegree returns the number of outgoing edges of vertex v in graph // g. Note that for undirected graphs each edge is also considered to // be an outgoing edge. OutDegree(v VIdx) int EachOut(from VIdx, onDest VisitVertex) error // InDegree returns the number of incoming edges of vertex v in graph // g. Note that for undirected graphs each edge is also considered to // be an incoming edge. InDegree(v VIdx) int EachIn(to VIdx, onSource VisitVertex) error RootCount() int EachRoot(onEdge VisitVertex) error LeafCount() int EachLeaf(onEdge VisitVertex) error }
type RGraph ¶
type RGraph[W any] interface { // Order return the numer of vertices in the graph. Order() int // Returns the weight of the edge that connects the vertex with index // u with the vertex with index v. If there is no such edge it returns nil. Edge(u, v VIdx) (weight W) // IsEdge returns true if and only if weight denotes an existing edge. IsEdge(weight W) bool // NotEdge return a W typed value that denotes a nonexisting edge, i.e. // IsEdge(NotEdge()) == false. NotEdge() W // Size returns the number of edges of the graph. Size() int // EachEdge calls onEdge for each edge in the graph. When onEdge returns // true EachEdge stops immediately and returns true. Otherwise EachEdge // returns false. EachEdge(onEdge VisitEdgeW[W]) error }
RGraph represents graph that allows read only access to the egde weights.
For graphs that can change be modified see WGraph. For undirected graphs see also RUndirected.
type RUndirected ¶
type RUndirected[W any] interface { RGraph[W] // Weight must only be called when u ≥ v. Otherwise WeightU's // behaviour is unspecified, it even might crash. In many // implementations this can be way more efficient than the // general case, see method Weight(). EdgeU(u, v VIdx) (weight W) Degree(v VIdx) int EachAdjacent(of VIdx, onNeighbour VisitVertex) error }
RUndirected represents an undirected graph that allows read only access to the edge weights. For undirected graphs each edge (u,v) is considered outgiong as well as incoming for both, vertex u and vertext v.
type SrcDstError ¶ added in v0.6.0
SrcDstError is returned when an error occurred in the src or dst graph during Cp*Weights.
func (SrcDstError) Error ¶ added in v0.6.0
func (err SrcDstError) Error() string
type UVError ¶ added in v0.6.0
type UVError struct {
U, V VIdx
// contains filtered or unexported fields
}
type VIdx ¶
type VIdx = int
VIdx is the type used to represent vertices in the graph implementations provided by the groph package.
type VisitEdgeW ¶ added in v0.6.0
type VisitVertex ¶
type WGraph ¶
type WGraph[W any] interface { RGraph[W] // Reset resizes the graph to order and reinitializes it. Implementations // are expected to reuse memory. Reset(order int) // SetWeight sets the edge weight for the edge starting at vertex u and // ending at vertex v. Passing w==nil removes the edge. SetEdge(u, v VIdx, weight W) DelEdge(u, v VIdx) }
WGraph represents graph that allows read and write access to the egde weights.
For undirected graphs see also WUndirected.
type WUndirected ¶
type WUndirected[W any] interface { WGraph[W] RUndirected[W] // SetWeightU must only be called when u ≥ v. Otherwise // SetWeightU's behaviour is unspecified, it even might crash. // // See also RUndirected.WeightU SetEdgeU(u, v VIdx, w W) DelEdgeU(u, v VIdx) }
WUndirected represents an undirected graph that allows read and write access to the egde weights.
Directories ¶
Path  Synopsis 

Package adjls provides graph implementations as adjacency lists.

Package adjls provides graph implementations as adjacency lists. 
Package adjls provides graph implementations as adjacency matrix.

Package adjls provides graph implementations as adjacency matrix. 
Package gimpls provides standard implementations for graph methods that can help to implement groph graphs.

Package gimpls provides standard implementations for graph methods that can help to implement groph graphs. 
Package graphs provides some specific graph implementstions.

Package graphs provides some specific graph implementstions. 
Package paths has algorithms that compute certain paths of a graph.

Package paths has algorithms that compute certain paths of a graph. 