Struct DependencyGraph 

pub struct DependencyGraph {
    pub nodes: RapidMap<PathBuf, AnalysisDefFingerprint>,
    pub edges: Vec<DependencyEdge>,
    /* private fields */
}

A dependency graph tracking relationships between source files.

The graph is directed: edges point from dependent files to their dependencies. For example, if main.rs imports utils.rs, there is an edge from main.rs to utils.rs.

The graph maintains both forward (dependencies) and reverse (dependents) adjacency lists for efficient bidirectional traversal.

Examples

use thread_flow::incremental::graph::DependencyGraph;
use thread_flow::incremental::types::{DependencyEdge, DependencyType};
use std::path::PathBuf;
use thread_utilities::RapidSet;

let mut graph = DependencyGraph::new();

// main.rs depends on utils.rs
graph.add_edge(DependencyEdge::new(
    PathBuf::from("main.rs"),
    PathBuf::from("utils.rs"),
    DependencyType::Import,
));

// Find what main.rs depends on
let deps = graph.get_dependencies(&PathBuf::from("main.rs"));
assert_eq!(deps.len(), 1);
assert_eq!(deps[0].to, PathBuf::from("utils.rs"));

// Find what depends on utils.rs
let dependents = graph.get_dependents(&PathBuf::from("utils.rs"));
assert_eq!(dependents.len(), 1);
assert_eq!(dependents[0].from, PathBuf::from("main.rs"));

Fields

nodes: RapidMap<PathBuf, AnalysisDefFingerprint>

Fingerprint state for each tracked file.

edges: Vec<DependencyEdge>

All dependency edges in the graph.

Implementations

impl DependencyGraph

pub fn new() -> Self

Creates a new empty dependency graph.

Examples

use thread_flow::incremental::graph::DependencyGraph;

let graph = DependencyGraph::new();
assert_eq!(graph.node_count(), 0);
assert_eq!(graph.edge_count(), 0);

pub fn add_node(&mut self, file: &Path)

Ensures a file node exists in the graph without adding any edges.

This is useful when a file has been processed but no dependency edges were extracted (e.g., a file with no imports, or a Go file where all imports resolve to external packages without a configured module path).

Arguments

• file - Path of the file to add as a node.

Examples

use thread_flow::incremental::graph::DependencyGraph;
use std::path::Path;

let mut graph = DependencyGraph::new();
graph.add_node(Path::new("main.go"));
assert!(graph.contains_node(Path::new("main.go")));
assert_eq!(graph.node_count(), 1);
assert_eq!(graph.edge_count(), 0);

pub fn add_edge(&mut self, edge: DependencyEdge)

Adds a dependency edge to the graph.

Both the source (from) and target (to) nodes are automatically registered if they do not already exist. Adjacency lists are updated for both forward and reverse lookups.

Arguments

• edge - The dependency edge to add.

Examples

use thread_flow::incremental::graph::DependencyGraph;
use thread_flow::incremental::types::{DependencyEdge, DependencyType};
use std::path::PathBuf;

let mut graph = DependencyGraph::new();
graph.add_edge(DependencyEdge::new(
    PathBuf::from("a.rs"),
    PathBuf::from("b.rs"),
    DependencyType::Import,
));
assert_eq!(graph.edge_count(), 1);
assert_eq!(graph.node_count(), 2);

pub fn get_dependencies(&self, file: &Path) -> Vec<&DependencyEdge>

Returns all direct dependencies of a file (files it depends on).

Arguments

• file - The file to query dependencies for.

Returns

A vector of references to dependency edges where from is the given file.

pub fn get_dependents(&self, file: &Path) -> Vec<&DependencyEdge>

Returns all direct dependents of a file (files that depend on it).

Arguments

• file - The file to query dependents for.

Returns

A vector of references to dependency edges where to is the given file.

pub fn find_affected_files( &self, changed_files: &RapidSet<PathBuf>, ) -> RapidSet<PathBuf>

Finds all files affected by changes to the given set of files.

Uses BFS traversal following reverse dependency edges (dependents) to discover the full set of files that need reanalysis. Only DependencyStrength::Strong edges trigger cascading invalidation.

Algorithm complexity: O(V + E) where V = files, E = dependency edges.

Arguments

• changed_files - Set of files that have been modified.

Returns

Set of all affected files, including the changed files themselves.

Examples

use thread_flow::incremental::graph::DependencyGraph;
use thread_flow::incremental::types::{DependencyEdge, DependencyType};
use std::path::PathBuf;
use thread_utilities::RapidSet;

let mut graph = DependencyGraph::new();

// A -> B -> C (A depends on B, B depends on C)
graph.add_edge(DependencyEdge::new(
    PathBuf::from("A"), PathBuf::from("B"), DependencyType::Import,
));
graph.add_edge(DependencyEdge::new(
    PathBuf::from("B"), PathBuf::from("C"), DependencyType::Import,
));

// Change C -> affects B and A
let changed = RapidSet::from([PathBuf::from("C")]);
let affected = graph.find_affected_files(&changed);
assert!(affected.contains(&PathBuf::from("A")));
assert!(affected.contains(&PathBuf::from("B")));
assert!(affected.contains(&PathBuf::from("C")));

pub fn topological_sort( &self, files: &RapidSet<PathBuf>, ) -> Result<Vec<PathBuf>, GraphError>

Performs topological sort on the given subset of files.

Returns files in dependency order: dependencies appear before their dependents. This ordering ensures correct incremental reanalysis.

Detects cyclic dependencies and returns GraphError::CyclicDependency if a cycle is found.

Algorithm complexity: O(V + E) using DFS.

Arguments

• files - The subset of files to sort.

Errors

Returns GraphError::CyclicDependency if a cycle is detected.

Examples

use thread_flow::incremental::graph::DependencyGraph;
use thread_flow::incremental::types::{DependencyEdge, DependencyType};
use std::path::PathBuf;
use thread_utilities::RapidSet;

let mut graph = DependencyGraph::new();
// A depends on B, B depends on C
graph.add_edge(DependencyEdge::new(
    PathBuf::from("A"), PathBuf::from("B"), DependencyType::Import,
));
graph.add_edge(DependencyEdge::new(
    PathBuf::from("B"), PathBuf::from("C"), DependencyType::Import,
));

let files = RapidSet::from([
    PathBuf::from("A"), PathBuf::from("B"), PathBuf::from("C"),
]);
let sorted = graph.topological_sort(&files).unwrap();
// C should come before B, B before A
let pos_a = sorted.iter().position(|p| p == &PathBuf::from("A")).unwrap();
let pos_b = sorted.iter().position(|p| p == &PathBuf::from("B")).unwrap();
let pos_c = sorted.iter().position(|p| p == &PathBuf::from("C")).unwrap();
assert!(pos_c < pos_b);
assert!(pos_b < pos_a);

pub fn node_count(&self) -> usize

Returns the number of nodes (files) in the graph.

pub fn edge_count(&self) -> usize

Returns the number of edges in the graph.

pub fn contains_node(&self, file: &Path) -> bool

Checks whether the graph contains a node for the given file.

pub fn validate(&self) -> Result<(), GraphError>

Validates graph integrity.

Checks for dangling edges (edges referencing nodes not in the graph) and other structural issues.

Returns

Ok(()) if the graph is structurally valid, or a GraphError otherwise.

pub fn clear(&mut self)

Removes all edges and nodes from the graph.

Trait Implementations

impl Clone for DependencyGraph

fn clone(&self) -> DependencyGraph

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for DependencyGraph

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for DependencyGraph

fn default() -> Self

Returns the “default value” for a type.