README
¶
dag
Implementation directed acyclic graphs (DAGs).
The implementation is fast and thread-safe. It prevents adding cycles or duplicates and thereby always maintains a valid DAG. The implementation caches descendants and ancestors to speed up subsequent calls.
Quickstart
Running:
package main
import (
"fmt"
"github.com/heimdalr/dag"
)
// data structure that will be used as vertex in the graph
type myVertex struct {
Label string
}
// implement the Vertex interface
func (v myVertex) String() string {
return v.Label
}
func main() {
// initialize a new graph
d := dag.NewDAG()
// init three vertices
v1 := &myVertex{"1"}
v2 := &myVertex{"2"}
v3 := &myVertex{"3"}
// add the above vertices and connect them with two edges
_ = d.AddEdge(v1, v2)
_ = d.AddEdge(v1, v3)
// describe the graph
fmt.Print(d.String())
}
will result in something like:
DAG Vertices: 3 - Edges: 2
Vertices:
2
3
1
Edges:
1 -> 2
1 -> 3
Documentation
¶
Overview ¶
Package dag implements directed acyclic graphs (DAGs).
Example ¶
// initialize a new graph
d := NewDAG()
// init three vertices
v1 := &iVertex{1}
v2 := &iVertex{2}
v3 := &iVertex{3}
// add the above vertices and connect them with two edges
_ = d.AddEdge(v1, v2)
_ = d.AddEdge(v1, v3)
// describe the graph
fmt.Print(d.String())
Output: DAG Vertices: 3 - Edges: 2 Vertices: 2 3 1 Edges: 1 -> 2 1 -> 3
Index ¶
- type DAG
- func (d *DAG) AddEdge(src Vertex, dst Vertex) error
- func (d *DAG) AddVertex(v Vertex) error
- func (d *DAG) AncestorsWalker(v Vertex) (chan Vertex, chan bool, error)
- func (d *DAG) DeleteEdge(src Vertex, dst Vertex) error
- func (d *DAG) DeleteVertex(v Vertex) error
- func (d *DAG) DescendantsWalker(v Vertex) (chan Vertex, chan bool, error)
- func (d *DAG) FlushCaches()
- func (d *DAG) GetAncestors(v Vertex) (map[Vertex]bool, error)
- func (d *DAG) GetChildren(v Vertex) (map[Vertex]bool, error)
- func (d *DAG) GetDescendants(v Vertex) (map[Vertex]bool, error)
- func (d *DAG) GetLeafs() map[Vertex]bool
- func (d *DAG) GetOrder() int
- func (d *DAG) GetOrderedAncestors(v Vertex) ([]Vertex, error)
- func (d *DAG) GetOrderedDescendants(v Vertex) ([]Vertex, error)
- func (d *DAG) GetParents(v Vertex) (map[Vertex]bool, error)
- func (d *DAG) GetRoots() map[Vertex]bool
- func (d *DAG) GetSize() int
- func (d *DAG) GetVertex(id string) (Vertex, error)
- func (d *DAG) GetVertices() map[Vertex]bool
- func (d *DAG) IsEdge(src Vertex, dst Vertex) (bool, error)
- func (d *DAG) ReduceTransitively()
- func (d *DAG) String() string
- type EdgeDuplicateError
- type EdgeLoopError
- type EdgeUnknownError
- type IdDuplicateError
- type IdEmptyError
- type IdUnknownError
- type SrcDstEqualError
- type Vertex
- type VertexDuplicateError
- type VertexNilError
- type VertexUnknownError
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type DAG ¶
type DAG struct {
// contains filtered or unexported fields
}
DAG implements the data structure of the DAG.
func (*DAG) AddEdge ¶
AddEdge adds an edge between src and dst. AddEdge returns an error, if src or dst are nil or if the edge would create a loop. AddEdge calls AddVertex, if src and/or dst are not yet known within the DAG.
func (*DAG) AddVertex ¶
AddVertex adds the vertex v to the DAG. AddVertex returns an error, if v is nil, v is already part of the graph, or the id of v is already part of the graph.
func (*DAG) AncestorsWalker ¶ added in v0.9.9
AncestorsWalker returns a channel and subsequently returns / walks all ancestors of the vertex v in a breath first order. The second channel returned may be used to stop further walking. AncestorsWalker returns an error, if v is nil or unknown.
Note, there is no order between sibling vertices. Two consecutive runs of AncestorsWalker may return different results.
Example ¶
dag := NewDAG()
v1 := &iVertex{1}
v2 := &iVertex{2}
v3 := &iVertex{3}
v4 := &iVertex{4}
v5 := &iVertex{5}
_ = dag.AddEdge(v1, v2)
_ = dag.AddEdge(v2, v3)
_ = dag.AddEdge(v2, v4)
_ = dag.AddEdge(v4, v5)
var ancestors []Vertex
vertices, signal, _ := dag.AncestorsWalker(v5)
for v := range vertices {
ancestors = append(ancestors, v)
if v == v2 {
signal <- true
break
}
}
fmt.Printf("%v", ancestors)
Output: [4 2]
func (*DAG) DeleteEdge ¶
DeleteEdge deletes an edge. DeleteEdge also deletes ancestor- and descendant-caches of related vertices. DeleteEdge returns an error, if src or dst are nil or unknown, or if there is no edge between src and dst.
func (*DAG) DeleteVertex ¶
DeleteVertex deletes the vertex v. DeleteVertex also deletes all attached edges (inbound and outbound) as well as ancestor- and descendant-caches of related vertices. DeleteVertex returns an error, if v is nil or unknown.
func (*DAG) DescendantsWalker ¶ added in v0.9.9
DescendantsWalker returns a channel and subsequently returns / walks all descendants of the vertex v in a breath first order. The second channel returned may be used to stop further walking. DescendantsWalker returns an error, if v is nil or unknown.
Note, there is no order between sibling vertices. Two consecutive runs of DescendantsWalker may return different results.
func (*DAG) FlushCaches ¶ added in v0.9.12
func (d *DAG) FlushCaches()
FlushCaches completely flushes the descendants- and ancestor cache.
Note, the only reason to call this method is to free up memory. Otherwise the caches are automatically maintained.
func (*DAG) GetAncestors ¶
GetAncestors return all ancestors of the vertex v. GetAncestors returns an error, if v is nil or unknown.
Note, in order to get the ancestors, GetAncestors populates the ancestor- cache as needed. Depending on order and size of the sub-graph of v this may take a long time and consume a lot of memory.
func (*DAG) GetChildren ¶
GetChildren returns all children of vertex v. GetChildren returns an error, if v is nil or unknown.
func (*DAG) GetDescendants ¶
GetDescendants return all ancestors of the vertex v. GetDescendants returns an error, if v is nil or unknown.
Note, in order to get the descendants, GetDescendants populates the descendants-cache as needed. Depending on order and size of the sub-graph of v this may take a long time and consume a lot of memory.
func (*DAG) GetOrderedAncestors ¶ added in v0.9.9
GetOrderedAncestors returns all ancestors of the vertex v in a breath-first order. Only the first occurrence of each vertex is returned. GetOrderedAncestors returns an error, if v is nil or unknown.
Note, there is no order between sibling vertices. Two consecutive runs of GetOrderedAncestors may return different results.
func (*DAG) GetOrderedDescendants ¶ added in v0.9.9
GetOrderedDescendants returns all descendants of the vertex v in a breath- first order. Only the first occurrence of each vertex is returned. GetOrderedDescendants returns an error, if v is nil or unknown.
Note, there is no order between sibling vertices. Two consecutive runs of GetOrderedDescendants may return different results.
func (*DAG) GetParents ¶
GetParents returns all parents of vertex v. GetParents returns an error, if v is nil or unknown.
func (*DAG) GetVertex ¶ added in v0.9.10
GetVertex returns a vertex by its id. GetVertex returns an error, if id is the empty string or unknown.
func (*DAG) GetVertices ¶
GetVertices returns all vertices.
func (*DAG) IsEdge ¶ added in v0.9.11
IsEdge returns true, if there exists an edge between src and dst. IsEdge returns false if there is no such edge. IsEdge returns an error, if src or dst are nil, unknown or the same.
func (*DAG) ReduceTransitively ¶ added in v0.9.11
func (d *DAG) ReduceTransitively()
ReduceTransitively transitively reduce the graph.
Note, in order to do the reduction the descendant-cache of all vertices is populated (i.e. the transitive closure). Depending on order and size of DAG this may take a long time and consume a lot of memory.
type EdgeDuplicateError ¶ added in v0.9.3
type EdgeDuplicateError struct {
// contains filtered or unexported fields
}
EdgeDuplicateError is the error type to describe the situation, that an edge already exists in the graph.
func (EdgeDuplicateError) Error ¶ added in v0.9.3
func (e EdgeDuplicateError) Error() string
Implements the error interface.
type EdgeLoopError ¶ added in v0.9.3
type EdgeLoopError struct {
// contains filtered or unexported fields
}
EdgeLoopError is the error type to describe loop errors (i.e. errors that where raised to prevent establishing loops in the graph).
func (EdgeLoopError) Error ¶ added in v0.9.3
func (e EdgeLoopError) Error() string
Implements the error interface.
type EdgeUnknownError ¶ added in v0.9.3
type EdgeUnknownError struct {
// contains filtered or unexported fields
}
EdgeUnknownError is the error type to describe the situation, that a given edge does not exit in the graph.
func (EdgeUnknownError) Error ¶ added in v0.9.3
func (e EdgeUnknownError) Error() string
Implements the error interface.
type IdDuplicateError ¶ added in v0.9.10
type IdDuplicateError struct {
// contains filtered or unexported fields
}
IdDuplicateError is the error type to describe the situation, that a given vertex id already exists in the graph.
func (IdDuplicateError) Error ¶ added in v0.9.10
func (e IdDuplicateError) Error() string
Implements the error interface.
type IdEmptyError ¶ added in v0.9.10
type IdEmptyError struct{}
IdEmptyError is the error type to describe the situation, that a nil is given instead of a vertex.
func (IdEmptyError) Error ¶ added in v0.9.10
func (e IdEmptyError) Error() string
Implements the error interface.
type IdUnknownError ¶ added in v0.9.10
type IdUnknownError struct {
// contains filtered or unexported fields
}
IdUnknownError is the error type to describe the situation, that a given vertex does not exit in the graph.
func (IdUnknownError) Error ¶ added in v0.9.10
func (e IdUnknownError) Error() string
Implements the error interface.
type SrcDstEqualError ¶ added in v0.9.11
type SrcDstEqualError struct {
// contains filtered or unexported fields
}
SrcDstEqualError is the error type to describe the situation, that src and dst are equal.
func (SrcDstEqualError) Error ¶ added in v0.9.11
func (e SrcDstEqualError) Error() string
Implements the error interface.
type Vertex ¶
type Vertex interface {
// Return a string representation of the vertex.
String() string
// Return the id of this vertex. This id must be unique and never change.
Id() string
}
Vertex is the interface to be implemented for the vertices of the DAG.
type VertexDuplicateError ¶ added in v0.9.3
type VertexDuplicateError struct {
// contains filtered or unexported fields
}
VertexDuplicateError is the error type to describe the situation, that a given vertex already exists in the graph.
func (VertexDuplicateError) Error ¶ added in v0.9.3
func (e VertexDuplicateError) Error() string
Implements the error interface.
type VertexNilError ¶ added in v0.9.3
type VertexNilError struct{}
VertexNilError is the error type to describe the situation, that a nil is given instead of a vertex.
func (VertexNilError) Error ¶ added in v0.9.3
func (e VertexNilError) Error() string
Implements the error interface.
type VertexUnknownError ¶
type VertexUnknownError struct {
// contains filtered or unexported fields
}
VertexUnknownError is the error type to describe the situation, that a given vertex does not exit in the graph.
func (VertexUnknownError) Error ¶
func (e VertexUnknownError) Error() string
Implements the error interface.
Source Files
Directories