README
¶
dag
Yet another directed acyclic graph (DAG) implementation in golang.
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 a Directed Acyclic Graph data structure and relevant methods.
Example ¶
// initialize a new graph
d := 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())
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) 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) String() string
- type EdgeDuplicateError
- type EdgeLoopError
- type EdgeUnknownError
- type IdDuplicateError
- type IdEmptyError
- type IdUnknownError
- 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
}
The DAG type implements a Directed Acyclic Graph.
func (*DAG) AncestorsWalker ¶ added in v0.9.9
AncestorsWalker returns a channel and subsequently returns / walks all ancestors of a vertex in a breath first order. The second channel returned may be used to stop further walking.
Example ¶
dag := NewDAG()
v1 := &myVertex{1}
v2 := &myVertex{2}
v3 := &myVertex{3}
v4 := &myVertex{4}
v5 := &myVertex{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) DeleteVertex ¶
Delete a vertex including all inbound and outbound edges. Delete cached ancestors and descendants of relevant vertices.
func (*DAG) DescendantsWalker ¶ added in v0.9.9
DescendantsWalker returns a channel and subsequently returns / walks all descendants of a vertex in a breath first order. The second channel returned may be used to stop further walking.
func (*DAG) GetAncestors ¶
Return all Ancestors of the given vertex.
func (*DAG) GetChildren ¶
Return all children of the given vertex.
func (*DAG) GetDescendants ¶
Return all Descendants of the given vertex.
func (*DAG) GetOrderedAncestors ¶ added in v0.9.9
GetOrderedAncestors returns all ancestors of a vertex in a breath first order
func (*DAG) GetOrderedDescendants ¶ added in v0.9.9
GetOrderedDescendants returns all descendants of a vertex in a breath first order
func (*DAG) GetParents ¶
Return all parents of the given vertex.
type EdgeDuplicateError ¶ added in v0.9.3
type EdgeDuplicateError struct {
// contains filtered or unexported fields
}
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
}
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
}
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
}
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{}
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
}
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 VertexDuplicateError ¶ added in v0.9.3
type VertexDuplicateError struct {
// contains filtered or unexported fields
}
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{}
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
}
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