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 WalkIncomingNodes(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 ¶
StronglyConnectedComponents returns the list of strongly connected components of the graph using Tarjan algorithm.
func Walk ¶
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 WalkIncomingNodes ¶
WalkIncomingNodes walks all the nodes that have a direct, incoming edge to start.
func WalkTopological ¶
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 ¶
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 ¶
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 ¶
Dependants returns the list of Nodes that depend on n: all Nodes for which an edge to n is defined.
func (*Graph) Dependencies ¶
Dependencies returns the list of Nodes that n depends on: all Nodes for which an edge from n is defined.
func (*Graph) GetByID ¶
GetByID returns a node from an ID. Returns nil if the ID does not exist in the graph.
func (*Graph) Leaves ¶
Leaves returns the set of Nodes in g that have no dependencies. This is useful for walking g in reverse.
func (*Graph) Remove ¶
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 ¶
RemoveEdge removes an edge e from g. RemoveEdge is a no-op if e doesn't exist in g.
Source Files