Documentation
¶
Overview ¶
Package dag provides utilities for working with directed acyclic graphs (DAGs).
Index ¶
- type Edge
- type Graph
- func (g *Graph[NodeType]) Add(n NodeType) NodeType
- func (g *Graph[NodeType]) AddEdge(e Edge[NodeType]) error
- func (g *Graph[NodeType]) Children(n NodeType) []NodeType
- func (g *Graph[NodeType]) Clone() *Graph[NodeType]
- func (g *Graph[NodeType]) Eliminate(n NodeType)
- func (g *Graph[NodeType]) Inject(parent, node NodeType) NodeType
- func (g *Graph[NodeType]) Leaves() []NodeType
- func (g *Graph[NodeType]) Len() int
- func (g *Graph[NodeType]) Nodes() iter.Seq[NodeType]
- func (g *Graph[NodeType]) Parents(n NodeType) []NodeType
- func (g *Graph[NodeType]) Root() (NodeType, error)
- func (g *Graph[NodeType]) Roots() []NodeType
- func (g *Graph[NodeType]) Walk(n NodeType, f WalkFunc[NodeType], order WalkOrder) error
- type Node
- type WalkFunc
- type WalkOrder
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Edge ¶
type Edge[NodeType Node] struct { Parent, Child NodeType }
Edge is a directed connection (parent-child relation) between two nodes.
type Graph ¶
type Graph[NodeType Node] struct { // contains filtered or unexported fields }
Graph is a directed acyclic graph (DAG).
func (*Graph[NodeType]) Add ¶
func (g *Graph[NodeType]) Add(n NodeType) NodeType
Add adds a new node n to the graph if it doesn't already exist. For convenience, Add returns the input node without modification.
Add is a no-op if n is the zero value.
func (*Graph[NodeType]) AddEdge ¶
AddEdge creates a directed edge between two nodes in the graph, establishing a parent-child relationship between the nodes where e.Parent becomes a parent of e.Child.
AddEdge returns an error if:
* Either node is the zero value, or * either node doesn't exist in the graph.
AddEdge preserves the order of addition of edges.
func (*Graph[NodeType]) Children ¶
func (g *Graph[NodeType]) Children(n NodeType) []NodeType
Children returns all child nodes of the given node.
func (*Graph[NodeType]) Clone ¶
Clone returns a shallow clone of the graph: nodes in the graph are transferred using ordinary assignment.
func (*Graph[NodeType]) Eliminate ¶
func (g *Graph[NodeType]) Eliminate(n NodeType)
Eliminate removes the node n from the graph and reconnects n's parents to n's children, maintaining connectivity across the graph.
If n does not have a parent, all of its children will be promoted to root nodes.
func (*Graph[NodeType]) Inject ¶
func (g *Graph[NodeType]) Inject(parent, node NodeType) NodeType
Inject injects a new node between a parent and its children:
* The children of parent become children of node. * The child of parent becomes node.
Inject panics if given a node that already exists in the plan.
For convenience, Inject returns node without modification.
func (*Graph[NodeType]) Leaves ¶
func (g *Graph[NodeType]) Leaves() []NodeType
Leaves returns all nodes that have no children.
func (*Graph[NodeType]) Parents ¶
func (g *Graph[NodeType]) Parents(n NodeType) []NodeType
Parent returns the parent of the given node.
func (*Graph[NodeType]) Root ¶
Root returns the root node that have no parents. It returns an error if the plan has no or multiple root nodes.
func (*Graph[NodeType]) Roots ¶
func (g *Graph[NodeType]) Roots() []NodeType
Roots returns all nodes that have no parents.
type Node ¶
type Node interface {
comparable
ID() ulid.ULID
}
Node represents an individual node in a Graph. The zero value of Node is reserved to indicate a nil node.
type WalkFunc ¶
WalkFunc is a function that gets invoked when walking a Graph. Walking will stop if WalkFunc returns a non-nil error.
Source Files