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(g Any, w io.Writer, name string, directed bool, ...) (err error)
- type Any
- type Builder
- func (b *Builder) AddEdge(from, to int)
- func (b *Builder) AddEdgeL(from, to string)
- func (b *Builder) AddEdgeW(from, to, w int)
- func (b *Builder) AddEdgeWL(from, to string, w int)
- func (b *Builder) DenseDigraph() (g *Dense)
- func (b *Builder) DenseDigraphW() (g *DenseW)
- func (b *Builder) DenseGraph() (g *Dense)
- func (b *Builder) DenseGraphW() (g *DenseW)
- func (b *Builder) Len() int
- func (b *Builder) SparseDigraph() (g *Sparse)
- func (b *Builder) SparseDigraphW() (g *SparseW)
- func (b *Builder) V(label string) int
- type Dense
- func (g *Dense) DelEdge(u, v int)
- func (g *Dense) E(u, v int) bool
- func (g *Dense) ForSucc(u int, cb func(v int) bool) bool
- func (g *Dense) ForSuccW(u int, cb func(v, w int) bool) bool
- func (l Dense) Label(v int) string
- func (l Dense) Len() int
- func (g *Dense) Next(it DenseIt) DenseIt
- func (g *Dense) NumPred(v int) (n int)
- func (g *Dense) NumSucc(u int) (n int)
- func (g *Dense) Pred(v int) DenseIt
- func (g *Dense) Succ(u int) DenseIt
- func (g *Dense) TopoSort(keepEdges bool) []int
- func (l Dense) V(name string) (idx int, ok bool)
- func (g *Dense) W(u, v int) int
- type DenseIt
- type DenseW
- func (g *DenseW) E(u, v int) bool
- func (g *DenseW) ForSucc(u int, cb func(v int) bool) bool
- func (g *DenseW) ForSuccW(u int, cb func(v, w int) bool) bool
- func (l DenseW) Label(v int) string
- func (l DenseW) Len() int
- func (g *DenseW) Next(it DenseIt) DenseIt
- func (g *DenseW) Pred(v int) DenseIt
- func (g *DenseW) Succ(u int) DenseIt
- func (l DenseW) V(name string) (idx int, ok bool)
- func (g *DenseW) W(u, v int) int
- type Sparse
- func (g *Sparse) E(u, v int) bool
- func (g *Sparse) ForSucc(u int, cb func(v int) bool) bool
- func (g *Sparse) ForSuccW(u int, cb func(v, w int) bool) bool
- func (l Sparse) Label(v int) string
- func (l Sparse) Len() int
- func (g *Sparse) Next(it SparseIt) SparseIt
- func (g *Sparse) Succ(u int) SparseIt
- func (l Sparse) V(name string) (idx int, ok bool)
- func (g *Sparse) W(u, v int) int
- type SparseIt
- type SparseItW
- type SparseW
- func (g *SparseW) E(u, v int) bool
- func (g *SparseW) ForSuccW(u int, cb func(v, w int) bool) bool
- func (l SparseW) Label(v int) string
- func (l SparseW) Len() int
- func (g *SparseW) Next(it SparseItW) SparseItW
- func (g *SparseW) NumSucc(u int) int
- func (g *SparseW) PredI(v, i int) int
- func (g *SparseW) Succ(u int) SparseItW
- func (g *SparseW) SuccI(u, i int) int
- func (g *SparseW) TopoSort(keepEdges bool) []int
- func (l SparseW) V(name string) (idx int, ok bool)
- func (g *SparseW) W(u, v int) int
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func WriteDOT ¶
func WriteDOT(g Any, 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 Any ¶
type Any interface {
Len() int
V(string) (int, bool)
Label(v int) string
W(u, v int) int
ForSucc(u int, cb func(v int) bool) bool
// contains filtered or unexported methods
}
AnyGraph 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 Builder ¶
type Builder struct {
// contains filtered or unexported fields
}
A Builder 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 (*Builder) AddEdgeL ¶
AddEdgeL records a new edge between two vertices (denoted by labels, created if necessary).
func (*Builder) AddEdgeWL ¶
AddEdgeWL records a new weighted edge between two vertices (denoted by labels, created if necessary).
func (*Builder) DenseDigraph ¶
DenseDigraph returns the contents of the builder as an unweighted dense digraph.
func (*Builder) 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 (*Builder) DenseGraph ¶
DenseGraph returns the contents of the builder as an unweighted dense undirected graph.
func (*Builder) 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 (*Builder) SparseDigraph ¶
SparseDigraph returns the contents of the builder as an unweighted sparse digraph.
func (*Builder) SparseDigraphW ¶
SparseDigraphW returns the contents of the builder as an unweighted sparse digraph.
type Dense ¶
type Dense struct {
// contains filtered or unexported fields
}
func (*Dense) DelEdge ¶
DelEdge removes the edge (u, v) from the graph. If the edge did not exist, the call does nothing.
func (*Dense) ForSucc ¶
ForSucc iterates over the successors of u, returning true if the end was reached. Return false from the callback to stop short; that is then returned to the caller.
func (*Dense) ForSuccW ¶
ForSuccW is like ForSucc, but the weight (always 1) will also be passed to the callback.
func (*Dense) NumPred ¶
NumPred returns the total number of successors of u. This is an O(|V|) operation.
func (*Dense) NumSucc ¶
NumSucc returns the total number of successors of u. This is an O(|V|) operation.
type DenseIt ¶
type DenseIt struct {
// contains filtered or unexported fields
}
DenseIt is an iterator over the edges of a dense graph.
type DenseW ¶
type DenseW struct {
// contains filtered or unexported fields
}
func (*DenseW) ForSucc ¶
ForSucc iterates over the successors of u, returning true if the end was reached. Return false from the callback to stop short; that is then returned to the caller.
func (*DenseW) ForSuccW ¶
ForSuccW is like ForSucc, but the weight will also be passed to the callback.
type Sparse ¶
type Sparse struct {
// contains filtered or unexported fields
}
func (*Sparse) ForSucc ¶
ForSucc iterates over the successors of u, returning true if the end was reached. Return false from the callback to stop short; that is then returned to the caller.
func (*Sparse) ForSuccW ¶
ForSuccW is like ForSucc, but the weight (always 1) will also be passed to the callback.
type SparseIt ¶
type SparseIt struct {
// contains filtered or unexported fields
}
SparseIt is an iterator over the edges of a sparse unweighted graph.
type SparseItW ¶
type SparseItW struct {
SparseIt
// contains filtered or unexported fields
}
SparseWIt is an iterator over the edges of a sparse weighted graph.
type SparseW ¶
type SparseW struct {
Sparse
// contains filtered or unexported fields
}
func (*SparseW) E ¶
E returns true if the edge (u, v) exists and has a non-zero weight in the graph.
func (*SparseW) ForSuccW ¶
ForSuccW is like ForSucc, but the weight will also be passed to the callback.
func (*SparseW) PredI ¶
PredI returns the i'th predecessor of u (ordered by vertex index). Note that this is an O(|V|+|E|) operation.
Source Files