Documentation
¶
Overview ¶
Package dag defines a Directed Acyclic Graph.
Index ¶
- func Reduce(g *Graph)
- func StronglyConnectedComponents(g *Graph) [][]Node
- func Validate(g *Graph) error
- func Walk(g *Graph, start []Node, fn WalkFunc) error
- func WalkReverse(g *Graph, start []Node, fn WalkFunc) error
- func WalkTopological(g *Graph, start []Node, fn WalkFunc) error
- type Edge
- type Graph
- func (g *Graph) Add(n Node)
- func (g *Graph) AddEdge(e Edge)
- func (g *Graph) Clone() *Graph
- func (g *Graph) Dependants(n Node) []Node
- func (g *Graph) Dependencies(n Node) []Node
- func (g *Graph) Edges() []Edge
- func (g *Graph) GetByID(id string) Node
- func (g *Graph) Leaves() []Node
- func (g *Graph) Nodes() []Node
- func (g *Graph) Remove(n Node)
- func (g *Graph) RemoveEdge(e Edge)
- func (g *Graph) Roots() []Node
- type Node
- type WalkFunc
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Reduce ¶
func Reduce(g *Graph)
Reduce performs a transitive reduction on g. A transitive reduction removes as many edges as possible while maintaining the same "reachability" as the original graph: any node N reachable from node S will still be reachable after a reduction.
func StronglyConnectedComponents ¶ added in v0.26.0
func StronglyConnectedComponents(g *Graph) [][]Node
StronglyConnectedComponents returns the list of strongly connected components of the graph using Tarjan algorithm.
func Validate ¶ added in v0.26.0
func Validate(g *Graph) error
Validate checks that the graph doesn't contain cycles
func Walk ¶
func Walk(g *Graph, start []Node, fn WalkFunc) error
Walk performs a depth-first walk of outgoing edges for all nodes in start, invoking the provided fn for each node. Walk returns the error returned by fn.
Nodes unreachable from start will not be passed to fn.
func WalkReverse ¶
func WalkReverse(g *Graph, start []Node, fn WalkFunc) error
WalkReverse performs a depth-first walk of incoming edges for all nodes in start, invoking the provided fn for each node. Walk returns the error returned by fn.
Nodes unreachable from start will not be passed to fn.
func WalkTopological ¶
func WalkTopological(g *Graph, start []Node, fn WalkFunc) error
WalkTopological performs a topological walk of all nodes in start in dependency order: a node will not be visited until its outgoing edges are visited first.
Nodes will not be passed to fn if they are not reachable from start or if not all of their outgoing edges are reachable from start.
Types ¶
type Graph ¶
type Graph struct {
// contains filtered or unexported fields
}
Graph is a Directed Acyclic Graph. The zero value is ready for use. Graph cannot be modified concurrently.
func (*Graph) Add ¶
func (g *Graph) Add(n Node)
Add adds a new Node into g. Add is a no-op if n already exists in g.
Add will panic if there is another node in g with the same NodeID as n.
func (*Graph) AddEdge ¶
func (g *Graph) AddEdge(e Edge)
AddEdge adds a new Edge into g. AddEdge does not prevent cycles from being introduced; cycles must be detected separately.
AddEdge will panic if either node in the edge doesn't exist in g.
func (*Graph) Dependants ¶
func (g *Graph) Dependants(n Node) []Node
Dependants returns the list of Nodes that depend on n: all Nodes for which an edge to n is defined.
func (*Graph) Dependencies ¶
func (g *Graph) Dependencies(n Node) []Node
Dependencies returns the list of Nodes that n depends on: all Nodes for which an edge from n is defined.
func (*Graph) GetByID ¶
func (g *Graph) GetByID(id string) Node
GetByID returns a node from an ID. Returns nil if the ID does not exist in the graph.
func (*Graph) Leaves ¶
func (g *Graph) Leaves() []Node
Leaves returns the set of Nodes in g that have no dependencies. This is useful for walking g in reverse.
func (*Graph) Remove ¶
func (g *Graph) Remove(n Node)
Remove removes a Node from g. Remove is a no-op if n does not exist in g.
Remove also removes any edge to or from n.
func (*Graph) RemoveEdge ¶
func (g *Graph) RemoveEdge(e Edge)
RemoveEdge removes an edge e from g. RemoveEdge is a no-op if e doesn't exist in g.
Source Files