Struct DependencyGraph 

pub struct DependencyGraph { /* private fields */ }

A directed-acyclic graph (DAG) of tasks with metadata only.

Stores nodes, edges, and scheduling hints without holding compute closures. Use this for planning, critical-path analysis, and dependency validation.

Implementations

impl DependencyGraph

pub fn new(config: DependencyGraphConfig) -> Self

Create an empty graph with the given configuration.

pub fn add_task(&mut self, name: &str, priority: i32) -> TaskId

Add a task with name and priority. Returns the new task’s TaskId.

pub fn add_task_with_cost( &mut self, name: &str, priority: i32, cost: f64, ) -> TaskId

Add a task with name, priority, and estimated cost. Returns the task’s TaskId.

pub fn add_dependency(&mut self, task: TaskId, dep: TaskId) -> CoreResult<()>

Declare that task depends on dep — dep must complete before task.

When enable_cycle_detection is set, this checks for cycles before adding the edge.

Errors

Returns CoreError::InvalidInput if either ID is unknown, if this is a self-loop, or if adding the edge would create a cycle (when cycle detection is enabled).

pub fn n_tasks(&self) -> usize

Total number of task nodes.

pub fn n_edges(&self) -> usize

Total number of dependency edges.

pub fn get_task(&self, id: TaskId) -> Option<&DepTaskNode>

Return a reference to the task node for id, or None if not found.

pub fn dependencies(&self, id: TaskId) -> &[TaskId]

Return the list of tasks that id directly depends on.

pub fn dependents(&self, id: TaskId) -> Vec<TaskId>

Compute the list of tasks that directly depend on id (reverse edges).

pub fn is_ready(&self, id: TaskId, completed: &HashSet<TaskId>) -> bool

Return true if id is ready to run (all direct dependencies are in completed).

pub fn topological_sort(&self) -> CoreResult<Vec<TaskId>>

Compute a topological ordering using the algorithm specified in the config.

Returns Err if the graph contains a cycle.

pub fn topological_sort_kahn(&self) -> CoreResult<Vec<TaskId>>

Kahn’s algorithm (BFS-based topological sort).

Returns Err if a cycle is detected.

pub fn topological_sort_dfs(&self) -> CoreResult<Vec<TaskId>>

DFS-based topological sort (finishing-time approach, Tarjan 1976).

Follows the forward dependency direction (from predecessors to dependents) in DFS post-order. Emitting tasks in post-order and reversing produces a valid topological ordering where all predecessors appear before their dependents.

Returns Err if a cycle is detected.

pub fn find_cycles(&self) -> Vec<Vec<TaskId>>

Find all simple cycles in the graph.

Returns each cycle as a Vec<TaskId> listing the nodes in cycle order. Returns an empty Vec if the graph is acyclic.

pub fn critical_path(&self) -> Vec<TaskId>

Compute the critical path — the longest chain from a source to a sink, weighted by estimated_cost.

Returns the ordered sequence of task IDs along that path. Returns an empty Vec if the graph is empty or contains a cycle.

pub fn execution_layers(&self) -> CoreResult<Vec<Vec<TaskId>>>

Group tasks into execution layers.

Layer 0 contains all tasks with no dependencies. Layer k contains all tasks whose dependencies are in layers < k.

Returns Err if the graph contains a cycle.

pub fn parallel_schedule( &self, n_workers: usize, ) -> CoreResult<Vec<Vec<TaskId>>>

Assign tasks to n_workers workers respecting dependencies.

Returns schedule[worker_id] = [task_id, ...]. Uses a greedy list-scheduling heuristic: assign the longest remaining task to the worker that becomes free first.

Returns Err if the graph contains a cycle.