Package dag provides the Directed-Acyclic-Graph (DAG) primitives required by Terramate. The nodes can be added by providing both the descendants and ancestors of each node but only the descendant -> ancestors relationship is kept.
Errors returned by operations on the DAG.
This section is empty.
This section is empty.
type DAG[V any] struct {
}
DAG is a Directed-Acyclic Graph
New creates a new empty Directed-Acyclic-Graph.
Transform transforms a DAG of D's to a DAG of S's by applying the given function to each node. Afterwards, source DAG must be discarded.
func (d *DAG[V]) AddNode(id ID, value V, descendants, ancestors []ID) error
AddNode adds a new node to the dag. The lists of descendants and ancestors defines its edge. The value is anything related to the node that needs to be retrieved later when processing the DAG.
func (d *DAG[V]) AncestorsOf(id ID) []ID
AncestorsOf returns the list of ancestor node ids of the given id.
HasCycle returns true if the DAG has a cycle.
func (d *DAG[V]) IDs() []ID
IDs returns the sorted list of node ids.
Node returns the node with the given id.
func (d *DAG[V]) Order() []ID
Order returns the topological order of the DAG. The node ids are lexicographic sorted whenever possible to give a consistent output. May only be called after Validate().
func (d *DAG[V]) Reduce(predicate func(id ID) bool)
Reduce removes nodes that match the given predicate. When a node is removed, all edges to it are replaced by edges to its children, so the order within the graph is preserved. May only be called after Validate().
Validate the DAG looking for cycles.
type Visited map[ID]struct{}
Visited in a map of visited dag nodes by id. Note: it's not concurrent-safe.
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4