Struct Dag 

pub struct Dag {
    pub nodes: Vec<DagNode>,
    forward: Vec<Vec<usize>>,
}

Complete DAG state: nodes + reverse index.

Fields

nodes: Vec<DagNode>

forward: Vec<Vec<usize>>

Forward adjacency: node → list of nodes that depend on it (downstream).

Implementations

impl Dag

pub fn new(nodes: Vec<DagNode>) -> Self

Build a DAG from a set of nodes. Nodes must be indexed 0..n-1. Automatically builds the forward (reverse-edge) index.

pub fn node_count(&self) -> usize

pub fn edge_count(&self) -> usize

pub fn upstream(&self, node: usize) -> &[usize]

Get direct upstream dependencies of a node.

pub fn downstream(&self, node: usize) -> &[usize]

Get direct downstream dependents of a node.

pub fn all_upstream(&self, node: usize) -> Vec<usize>

Get all transitive upstream nodes (BFS).

pub fn all_downstream(&self, node: usize) -> Vec<usize>

Get all transitive downstream nodes (BFS). This is the invalidation cascade.

pub fn topological_sort(&self) -> Option<Vec<usize>>

Kahn’s algorithm. Returns None if cycle detected.

pub fn detect_cycle(&self) -> Option<Vec<usize>>

Returns the cycle path if one exists, or None.

pub fn compute_depths(&self) -> Vec<usize>

Compute the depth (longest path from any root) of each node. Roots (no dependencies) have depth 0.

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

Find the longest path (critical path) from any root to any leaf. Returns the path as a sequence of node indices.

pub fn assign_layers(&self) -> (Vec<usize>, usize)

Assign layers using a depth-based approach for proper dependency flow. Returns (layer_assignment, max_layer). Layer 0 = leftmost/topmost (roots).

pub fn minimize_crossings( &self, layers: &[usize], max_layer: usize, ) -> Vec<Vec<usize>>

Minimize edge crossings within each layer using the barycenter heuristic. Takes layer assignments and returns an ordering of nodes within each layer. Returns Vec<Vec> where result[layer] = ordered node indices in that layer.

pub fn layout(&self, width: f64, height: f64) -> Vec<(f64, f64)>

Full Sugiyama layout: returns (x, y) positions for each node. Coordinates are normalized to [0, 1] range.

pub fn subgraph<F>(&self, predicate: F, depth: usize) -> Vec<usize>

where F: Fn(&DagNode) -> bool,

Extract a subgraph containing only nodes matching a predicate, plus their transitive dependencies and dependents up to a given depth. Returns the set of included node indices.

fn expand_direction( &self, start: usize, max_depth: usize, upstream: bool, included: &mut [bool], )

pub fn impact_analysis(&self, node: usize) -> ImpactResult

Simulate invalidating a node: returns (cascade_count, affected_by_type). affected_by_type[i] = count of affected nodes of type i (indexed by NodeType::layer_order).

pub fn orphans(&self) -> Vec<usize>

pub fn validate(&self) -> Vec<String>

Validate the DAG state. Returns a list of issues (empty = valid). Issues starting with “ERROR:” are critical; “WARN:” are advisory.

pub fn stale_nodes(&self) -> Vec<usize>

Get stale nodes sorted by dependency depth (shallowest first).

pub fn plannable_tasks(&self) -> Vec<usize>

Get task nodes that are ready to work on:

• Type is Task
• Status is Pending
• All dependencies are Valid

pub fn blocked_tasks(&self) -> Vec<usize>

Get task nodes that are blocked:

• Type is Task
• Status is Pending
• At least one dependency is not Valid

pub fn active_tasks(&self) -> Vec<usize>

Get active (in-progress) task nodes.

pub fn parallel_groups(&self) -> Vec<Vec<usize>>

Find groups of plannable tasks that can be executed in parallel (no mutual transitive dependencies).

pub fn summarize(&self) -> String

Summarize the DAG state as a human-readable string.

pub fn count_crossings(&self, positions: &[(f64, f64)]) -> usize

Count the number of edge crossings given a set of node positions. Lower is better for readability.

pub fn find_paths( &self, source: usize, target: usize, max_paths: usize, ) -> Vec<Vec<usize>>

Find all paths from source to target. Returns paths sorted by length. Limits to max_paths to prevent combinatorial explosion.

fn dfs_paths( &self, current: usize, target: usize, path: &mut Vec<usize>, result: &mut Vec<Vec<usize>>, max_paths: usize, )