Documentation
¶
Index ¶
- Variables
- type Builder
- type ExecutionOrder
- type Filter
- type Graph
- func (g *Graph) AddDependency(fromID, toID string) 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) 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
- type Node
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
}
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 dependency relationship between two nodes. The fromID depends on toID (fromID -> toID).
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) 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 dependency relationship between two nodes. The fromID depends on toID (fromID -> toID).
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
// 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.
Source Files