Documentation
¶
Index ¶
- Variables
- type Builder
- type ExecutionOrder
- type Filter
- type Graph
- func (g *Graph) AddDependency(fromID, toID string) error
- func (g *Graph) AddDependencyWithOptional(fromID, toID string, optional bool) error
- func (g *Graph) AddNode(node *Node) error
- func (g *Graph) Clone() *Graph
- func (g *Graph) Filter(filter Filter) *Graph
- func (g *Graph) FilterByComponent(component string) *Graph
- func (g *Graph) FilterByStack(stack string) *Graph
- func (g *Graph) FilterByType(nodeType string) *Graph
- func (g *Graph) FilterSelection(f *SelectionFilter) *Graph
- func (g *Graph) FindPath(fromID, toID string) ([]string, bool)
- func (g *Graph) GetConnectedComponents() []*Graph
- func (g *Graph) GetExecutionLevels() ([][]Node, error)
- func (g *Graph) GetNode(id string) (*Node, bool)
- func (g *Graph) HasCycles() (bool, []string)
- func (g *Graph) IdentifyRoots()
- func (g *Graph) IsReachable(fromID, toID string) bool
- func (g *Graph) RemoveNode(nodeID string) error
- func (g *Graph) Reset()
- func (g *Graph) ReverseTopologicalSort() (ExecutionOrder, error)
- func (g *Graph) Size() int
- func (g *Graph) TopologicalSort() (ExecutionOrder, error)
- type GraphBuilder
- func (b *GraphBuilder) AddDependency(fromID, toID string) error
- func (b *GraphBuilder) AddDependencyWithOptional(fromID, toID string, optional bool) error
- func (b *GraphBuilder) AddNode(node *Node) error
- func (b *GraphBuilder) Build() (*Graph, error)
- func (b *GraphBuilder) GetGraph() *Graph
- func (b *GraphBuilder) Reset()
- type Node
- type SelectionFilter
Constants ¶
This section is empty.
Variables ¶
var ( // ErrNilNode is returned when attempting to add a nil node to the graph. ErrNilNode = errors.New("cannot add nil node to graph") // ErrEmptyNodeID is returned when a node has an empty ID. ErrEmptyNodeID = errors.New("node ID cannot be empty") // ErrNodeExists is returned when attempting to add a node that already exists. ErrNodeExists = errors.New("node already exists in graph") // ErrEmptyDependencyID is returned when dependency IDs are empty. ErrEmptyDependencyID = errors.New("dependency IDs cannot be empty") // ErrSelfDependency is returned when a node attempts to depend on itself. ErrSelfDependency = errors.New("node cannot depend on itself") // ErrNodeNotFound is returned when a referenced node doesn't exist in the graph. ErrNodeNotFound = errors.New("node does not exist in graph") // ErrGraphAlreadyBuilt is returned when attempting to modify a built graph. ErrGraphAlreadyBuilt = errors.New("graph has already been built") // ErrCircularDependency is returned when a circular dependency is detected. ErrCircularDependency = errors.New("circular dependency detected") // ErrNoRootNodes is returned when no root nodes are found in the graph. ErrNoRootNodes = errors.New("no root nodes found - possible circular dependency involving all nodes") // ErrAddNodeFailed is returned when the builder fails to add a node. ErrAddNodeFailed = errors.New("builder failed to add node") // ErrAddDependencyFailed is returned when the builder fails to add a dependency. ErrAddDependencyFailed = errors.New("builder failed to add dependency") )
Static error definitions for the dependency package.
Functions ¶
This section is empty.
Types ¶
type Builder ¶
type Builder interface {
// AddNode adds a node to the graph being built.
AddNode(node *Node) error
// AddDependency creates a dependency relationship between two nodes.
AddDependency(fromID, toID string) error
// Build finalizes the graph construction and returns the built graph.
Build() (*Graph, error)
}
Builder defines the interface for constructing dependency graphs.
type ExecutionOrder ¶
type ExecutionOrder []Node
ExecutionOrder represents a slice of nodes in dependency order.
type Filter ¶
type Filter struct {
// NodeIDs specifies which nodes to include.
NodeIDs []string
// IncludeDependencies indicates whether to include all dependencies of filtered nodes.
IncludeDependencies bool
// IncludeDependents indicates whether to include all dependents of filtered nodes.
IncludeDependents bool
// DependencyDepth bounds how many dependency levels IncludeDependencies
// pulls in, measured from the nearest filtered node (0 = unlimited).
DependencyDepth int
// DependentDepth bounds how many dependent levels IncludeDependents
// pulls in, measured from the nearest filtered node (0 = unlimited).
DependentDepth int
}
Filter defines options for filtering a dependency graph.
type Graph ¶
type Graph struct {
// Nodes maps node IDs to their corresponding Node structures.
Nodes map[string]*Node
// Roots contains IDs of nodes with no dependencies (entry points).
Roots []string
}
Graph represents a dependency graph of components.
func (*Graph) AddDependency ¶
AddDependency creates a required dependency relationship between two nodes. The fromID depends on toID (fromID -> toID).
func (*Graph) AddDependencyWithOptional ¶ added in v1.229.0
AddDependencyWithOptional creates a dependency relationship and records whether the edge was declared optional.
func (*Graph) Filter ¶
Filter creates a new graph containing only the specified nodes and their relationships.
func (*Graph) FilterByComponent ¶
FilterByComponent creates a new graph containing only nodes with the specified component name.
func (*Graph) FilterByStack ¶
FilterByStack creates a new graph containing only nodes from the specified stack.
func (*Graph) FilterByType ¶
FilterByType creates a new graph containing only nodes of the specified type.
func (*Graph) FilterSelection ¶ added in v1.231.0
func (g *Graph) FilterSelection(f *SelectionFilter) *Graph
FilterSelection creates a new graph from a selector-aware selection:
result = (Seeds + dependencies(Seeds)) + {n in dependents(DependentSeeds) : KeepDependent(n)}
Dependents that fail KeepDependent (and DependentSeeds that are not in Seeds) are dropped, but edges through them are contracted so that execution order between the surviving nodes is preserved. With a nil KeepDependent and nil DependentSeeds the result equals Filter.
func (*Graph) GetConnectedComponents ¶
GetConnectedComponents returns all connected components in the graph. Each connected component is a subgraph where all nodes are reachable from each other.
func (*Graph) GetExecutionLevels ¶
GetExecutionLevels returns nodes grouped by execution level. Level 0 contains nodes with no dependencies, level 1 contains nodes that only depend on level 0, etc.
func (*Graph) IdentifyRoots ¶
func (g *Graph) IdentifyRoots()
IdentifyRoots finds all nodes with no dependencies.
func (*Graph) IsReachable ¶
IsReachable checks if one node is reachable from another.
func (*Graph) RemoveNode ¶
RemoveNode removes a node and all its relationships from the graph.
func (*Graph) ReverseTopologicalSort ¶
func (g *Graph) ReverseTopologicalSort() (ExecutionOrder, error)
ReverseTopologicalSort returns nodes in reverse dependency order. Nodes that depend on others are processed first.
func (*Graph) TopologicalSort ¶
func (g *Graph) TopologicalSort() (ExecutionOrder, error)
TopologicalSort returns nodes in dependency order using Kahn's algorithm. Nodes with no dependencies are processed first, followed by nodes that depend on them.
type GraphBuilder ¶
type GraphBuilder struct {
// contains filtered or unexported fields
}
GraphBuilder implements the Builder interface for constructing dependency graphs.
func (*GraphBuilder) AddDependency ¶
func (b *GraphBuilder) AddDependency(fromID, toID string) error
AddDependency creates a required dependency relationship between two nodes. The fromID depends on toID (fromID -> toID).
func (*GraphBuilder) AddDependencyWithOptional ¶ added in v1.229.0
func (b *GraphBuilder) AddDependencyWithOptional(fromID, toID string, optional bool) error
AddDependencyWithOptional creates a dependency relationship and records whether the edge was declared optional.
func (*GraphBuilder) AddNode ¶
func (b *GraphBuilder) AddNode(node *Node) error
AddNode adds a node to the graph being built.
func (*GraphBuilder) Build ¶
func (b *GraphBuilder) Build() (*Graph, error)
Build finalizes the graph construction and returns the built graph.
func (*GraphBuilder) GetGraph ¶
func (b *GraphBuilder) GetGraph() *Graph
GetGraph returns the current state of the graph (for debugging purposes). Note: This should not be used in production code; use Build() instead.
func (*GraphBuilder) Reset ¶
func (b *GraphBuilder) Reset()
Reset resets the builder to start building a new graph.
type Node ¶
type Node struct {
// ID is the unique identifier for the node (typically component-stack).
ID string
// Component is the name of the component.
Component string
// Stack is the stack name where this component is defined.
Stack string
// Type indicates the component type (e.g., "terraform", "helmfile").
Type string
// Dependencies contains IDs of nodes that this node depends on.
Dependencies []string
// OptionalDependencies identifies outgoing edges that were declared optional.
OptionalDependencies map[string]bool
// Dependents contains IDs of nodes that depend on this node.
Dependents []string
// Metadata stores additional component-specific data.
Metadata map[string]any
// Processed indicates whether this node has been processed during traversal.
Processed bool
}
Node represents a component in the dependency graph.
type SelectionFilter ¶ added in v1.231.0
type SelectionFilter struct {
// Seeds is the kept selection. Dependencies expand from here, unfiltered.
Seeds []string
// DependentSeeds is the unfiltered selection that dependents expand from.
// A nil slice means Seeds. Entries that are not in Seeds are treated as
// dropped intermediates: they are never included, but dependents reached
// through them are still considered and ordering is contracted around them.
DependentSeeds []string
// IncludeDependencies pulls in dependencies of Seeds without applying KeepDependent.
IncludeDependencies bool
// DependencyDepth bounds how many dependency levels are pulled in (0 = unlimited).
DependencyDepth int
// IncludeDependents pulls in dependents of DependentSeeds that pass KeepDependent.
IncludeDependents bool
// DependentDepth bounds how many dependent levels are walked, counted on the
// full graph including dropped intermediates (0 = unlimited).
DependentDepth int
// KeepDependent reports whether a reached dependent is included. A nil
// function keeps every reached dependent.
KeepDependent func(*Node) bool
}
SelectionFilter describes a selector-aware graph filter. It separates the kept selection (which dependencies expand from) from the unfiltered selection (which dependents expand from) and lets the caller drop reached dependents that do not match additional selectors.
Source Files