dag

Documentation

Overview

Package dag provides directed acyclic graph operations for model dependencies. It supports cycle detection, topological sorting, and incremental change detection.

Index

• type Graph
  • func NewGraph() *Graph
  • func (g *Graph) AddEdge(parentID, childID string) error
  • func (g *Graph) AddNode(id string, data interface{})
  • func (g *Graph) Clear()
  • func (g *Graph) EdgeCount() int
  • func (g *Graph) GetAffectedNodes(changedIDs []string) []string
  • func (g *Graph) GetAllNodes() []*Node
  • func (g *Graph) GetChildren(id string) []string
  • func (g *Graph) GetExecutionLevels() ([][]string, error)
  • func (g *Graph) GetLeaves() []string
  • func (g *Graph) GetNode(id string) (*Node, bool)
  • func (g *Graph) GetParents(id string) []string
  • func (g *Graph) GetRoots() []string
  • func (g *Graph) GetUpstreamNodes(id string) []string
  • func (g *Graph) HasCycle() (bool, []string)
  • func (g *Graph) NodeCount() int
  • func (g *Graph) Subgraph(nodeIDs []string) *Graph
  • func (g *Graph) TopologicalSort() ([]*Node, error)
• type Node

Types

type Graph

type Graph struct {
	// contains filtered or unexported fields
}

Graph represents a directed acyclic graph.

func NewGraph

func NewGraph() *Graph

NewGraph creates a new empty graph.

func (*Graph) AddEdge

func (g *Graph) AddEdge(parentID, childID string) error

AddEdge adds a directed edge from parent to child (child depends on parent).

func (*Graph) AddNode

func (g *Graph) AddNode(id string, data interface{})

AddNode adds a node to the graph.

func (*Graph) Clear

func (g *Graph) Clear()

Clear removes all nodes and edges from the graph.

func (*Graph) EdgeCount

func (g *Graph) EdgeCount() int

EdgeCount returns the number of edges in the graph.

func (*Graph) GetAffectedNodes

func (g *Graph) GetAffectedNodes(changedIDs []string) []string

GetAffectedNodes returns all nodes affected by changes to the given nodes. This includes the changed nodes and all their downstream dependents.

func (*Graph) GetAllNodes

func (g *Graph) GetAllNodes() []*Node

GetAllNodes returns all nodes in the graph.

func (*Graph) GetChildren

func (g *Graph) GetChildren(id string) []string

GetChildren returns the children (dependents) of a node.

func (*Graph) GetExecutionLevels

func (g *Graph) GetExecutionLevels() ([][]string, error)

GetExecutionLevels returns nodes grouped by execution level. Nodes at level N can be executed in parallel after level N-1 completes. Level 0 contains nodes with no dependencies.

func (*Graph) GetLeaves

func (g *Graph) GetLeaves() []string

GetLeaves returns nodes with no children (no dependents).

func (*Graph) GetNode

func (g *Graph) GetNode(id string) (*Node, bool)

GetNode returns a node by ID.

func (*Graph) GetParents

func (g *Graph) GetParents(id string) []string

GetParents returns the parents (dependencies) of a node.

func (*Graph) GetRoots

func (g *Graph) GetRoots() []string

GetRoots returns nodes with no parents (no dependencies).

func (*Graph) GetUpstreamNodes

func (g *Graph) GetUpstreamNodes(id string) []string

GetUpstreamNodes returns all nodes upstream of the given node (its dependencies and their dependencies).

func (*Graph) HasCycle

func (g *Graph) HasCycle() (bool, []string)

HasCycle returns true if the graph contains a cycle, along with the cycle path.

func (*Graph) NodeCount

func (g *Graph) NodeCount() int

NodeCount returns the number of nodes in the graph.

func (*Graph) Subgraph

func (g *Graph) Subgraph(nodeIDs []string) *Graph

Subgraph returns a new graph containing only the specified nodes and their edges.

func (*Graph) TopologicalSort

func (g *Graph) TopologicalSort() ([]*Node, error)

TopologicalSort returns nodes in topological order (dependencies before dependents). Returns an error if the graph contains a cycle.

type Node

type Node struct {
	// ID is the unique identifier (model path)
	ID string
	// Data holds arbitrary node data
	Data interface{}
}

Node represents a node in the DAG.