Documentation
¶
Overview ¶
Package graph contains utilities for (sparse|dense) (un|)directed (un|)weighted graphs.
One note about the convention: whenever there's a directed edge (u, v), its tail will be called u and its head will be called v.
Index ¶
- func WriteDOT[T comparable](g AnyG[T], w io.Writer, name string, directed bool, ...) (err error)
- type Any
- type AnyG
- type Builder
- type BuilderG
- func (b *BuilderG[T]) AddEdge(from, to int)
- func (b *BuilderG[T]) AddEdgeL(from, to T)
- func (b *BuilderG[T]) AddEdgeW(from, to, w int)
- func (b *BuilderG[T]) AddEdgeWL(from, to T, w int)
- func (b *BuilderG[T]) DenseDigraph() (g *DenseG[T])
- func (b *BuilderG[T]) DenseDigraphW() (g *DenseWG[T])
- func (b *BuilderG[T]) DenseGraph() (g *DenseG[T])
- func (b *BuilderG[T]) DenseGraphW() (g *DenseWG[T])
- func (b *BuilderG[T]) Len() int
- func (b *BuilderG[T]) SparseDigraph() (g *SparseG[T])
- func (b *BuilderG[T]) SparseDigraphW() (g *SparseWG[T])
- func (b *BuilderG[T]) V(label T) int
- type Dense
- type DenseG
- func (g *DenseG[T]) DelEdge(u, v int)
- func (g *DenseG[T]) E(u, v int) bool
- func (l DenseG) Label(v int) T
- func (l DenseG) Len() int
- func (g *DenseG[T]) NumPred(v int) (n int)
- func (g *DenseG[T]) NumSucc(u int) (n int)
- func (g *DenseG[T]) Pred(v int) iter.Seq[int]
- func (g *DenseG[T]) Succ(u int) iter.Seq[int]
- func (g *DenseG[T]) TopoSort(keepEdges bool) []int
- func (l DenseG) V(name T) (idx int, ok bool)
- func (g *DenseG[T]) W(u, v int) int
- type DenseW
- type DenseWG
- func (g *DenseWG[T]) E(u, v int) bool
- func (l DenseWG) Label(v int) T
- func (l DenseWG) Len() int
- func (g *DenseWG[T]) Pred(v int) iter.Seq[int]
- func (g *DenseWG[T]) Succ(u int) iter.Seq[int]
- func (g *DenseWG[T]) SuccW(u int) iter.Seq2[int, int]
- func (l DenseWG) V(name T) (idx int, ok bool)
- func (g *DenseWG[T]) W(u, v int) int
- type Sparse
- type SparseG
- type SparseW
- type SparseWG
- func (g *SparseWG[T]) E(u, v int) bool
- func (l SparseWG) Label(v int) T
- func (l SparseWG) Len() int
- func (g *SparseWG[T]) NumSucc(u int) int
- func (g *SparseWG[T]) PredI(v, i int) int
- func (g *SparseWG[T]) SuccI(u, i int) int
- func (g *SparseWG[T]) SuccW(u int) iter.Seq2[int, int]
- func (g *SparseWG[T]) TopoSort(keepEdges bool) []int
- func (l SparseWG) V(name T) (idx int, ok bool)
- func (g *SparseWG[T]) W(u, v int) int
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func WriteDOT ¶
func WriteDOT[T comparable](g AnyG[T], w io.Writer, name string, directed bool, nodeAttr func(v int) map[string]string, edgeAttr func(u, v int) map[string]string) (err error)
WriteDOT writes the graph out in GraphViz format. The `nodeAttr` and `edgeAttr` callback functions are optional, and can be used to add extra attributes to the node. If the callback returns a "label" attribute, it takes precedence over the usual node name / edge weight.
Types ¶
type AnyG ¶
type AnyG[T comparable] interface { Len() int V(T) (int, bool) Label(v int) T W(u, v int) int Succ(u int) iter.Seq[int] // contains filtered or unexported methods }
AnyG represents the common subset of all graph types.
It's useful for writing generic functions on both sparse and dense graphs. Note that there's generally some performance impact, so it's best left for non-sensitive utility functions.
type BuilderG ¶
type BuilderG[T comparable] struct { // contains filtered or unexported fields }
BuilderG is used to incrementally grow a graph.
Note that there is no checking for duplicate edges by default. The caller should pick one of:
- Ensure that the input only lists each edge once.
- Accept that the resulting graph will in fact be a multigraph.
- Use one of the dense graphs, which use an adjacency matrix (inherently robust for this).
- TODO: add methods for deduplicating
func NewBuilderG ¶
func NewBuilderG[T comparable]() *BuilderG[T]
NewBuilder returns a new, empty Builder.
func (*BuilderG[T]) AddEdgeL ¶
func (b *BuilderG[T]) AddEdgeL(from, to T)
AddEdgeL records a new edge between two vertices (denoted by labels, created if necessary).
func (*BuilderG[T]) AddEdgeW ¶
AddEdgeW records a new weighted edge between two vertices in the graph.
func (*BuilderG[T]) AddEdgeWL ¶
AddEdgeWL records a new weighted edge between two vertices (denoted by labels, created if necessary).
func (*BuilderG[T]) DenseDigraph ¶
DenseDigraph returns the contents of the builder as an unweighted dense digraph.
func (*BuilderG[T]) DenseDigraphW ¶
DenseDigraphW returns the contents of the builder as a weighted dense digraph.
If multiple edges have been recorded between two vertices, their values sum up.
func (*BuilderG[T]) DenseGraph ¶
DenseGraph returns the contents of the builder as an unweighted dense undirected graph.
func (*BuilderG[T]) DenseGraphW ¶
DenseGraphW returns the contents of the builder as a weighted dense undirected graph.
If multiple edges have been recorded between two vertices (in any order), their values sum up.
func (*BuilderG[T]) SparseDigraph ¶
SparseDigraph returns the contents of the builder as an unweighted sparse digraph.
func (*BuilderG[T]) SparseDigraphW ¶
SparseDigraphW returns the contents of the builder as a weighted sparse digraph.
type DenseG ¶
type DenseG[T comparable] struct { // contains filtered or unexported fields }
DenseG represents a dense graph using a boolean adjacency matrix.
func (*DenseG[T]) DelEdge ¶
DelEdge removes the edge (u, v) from the graph. If the edge did not exist, the call does nothing.
func (DenseG) Label ¶
func (l DenseG) Label(v int) T
Label returns the label corresponding to a vertex index.
func (*DenseG[T]) NumPred ¶
NumPred returns the total number of successors of u. This is an O(|V|) operation.
func (*DenseG[T]) NumSucc ¶
NumSucc returns the total number of successors of u. This is an O(|V|) operation.
type DenseWG ¶
type DenseWG[T comparable] struct { // contains filtered or unexported fields }
DenseWG represents a dense weighted graph using an integer adjacency matrix.
func (*DenseWG[T]) E ¶
E returns true if the edge (u, v) exists and has a non-zero weight in the graph.
func (DenseWG) Label ¶
func (l DenseWG) Label(v int) T
Label returns the label corresponding to a vertex index.
func (*DenseWG[T]) SuccW ¶
SuccW returns an iterator for the successors of vertex u, together with their weights.
type SparseG ¶
type SparseG[T comparable] struct { // contains filtered or unexported fields }
SparseG represents a sparse graph with adjacency lists.
func (SparseG) Label ¶
func (l SparseG) Label(v int) T
Label returns the label corresponding to a vertex index.
type SparseWG ¶
type SparseWG[T comparable] struct { SparseG[T] // contains filtered or unexported fields }
SparseWG represents a sparse weighted graphs with adjacency and edge weight lists.
func (*SparseWG[T]) E ¶
E returns true if the edge (u, v) exists and has a non-zero weight in the graph.
func (SparseWG) Label ¶
func (l SparseWG) Label(v int) T
Label returns the label corresponding to a vertex index.
func (*SparseWG[T]) NumSucc ¶
NumSucc returns the number of successors of u. This is an O(1) operation.
func (*SparseWG[T]) PredI ¶
PredI returns the i'th predecessor of u (ordered by vertex index). Note that this is an O(|V|+|E|) operation.
func (*SparseWG[T]) SuccW ¶
SuccW returns an iterator for the successors of vertex u, together with their weights.
Source Files