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.
Index ¶
- type DAG
- func (d *DAG) AddEdge(src Vertex, dst Vertex) error
- func (d *DAG) AddVertex(v Vertex) error
- func (d *DAG) DeleteEdge(src Vertex, dst Vertex) error
- func (d *DAG) DeleteVertex(v Vertex) 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) GetParents(v Vertex) (map[Vertex]bool, error)
- func (d *DAG) GetRoots() map[Vertex]bool
- func (d *DAG) GetSize() int
- func (d *DAG) GetVertices() map[Vertex]bool
- func (d *DAG) String() string
- type DMutex
- type EdgeDuplicateError
- type EdgeLoopError
- type EdgeUnknownError
- type Vertex
- type VertexDuplicateError
- type VertexNilError
- type VertexUnknownError
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) DeleteVertex ¶
Delete a vertex including all inbound and outbound edges. Delete cached ancestors and descendants of relevant vertices.
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) GetParents ¶
Return all parents of the given vertex.
type DMutex ¶ added in v0.9.6
type DMutex struct {
// contains filtered or unexported fields
}
Structure for dynamic mutexes.
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 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