Module algo

Expand description

Graph algorithms for centrality, community detection, and structure analysis.

This module provides a collection of graph algorithms for analyzing graph topology, identifying important nodes, and discovering community structure. All algorithms are designed for unweighted, directed graphs and work with both SQLite and Native backends.

§Available Algorithms

§Centrality Algorithms

pagerank - PageRank centrality for identifying influential nodes
betweenness_centrality - Betweenness centrality for finding bridge nodes

§Community Detection

label_propagation - Fast label propagation for community discovery
louvain_communities - Louvain method for modularity optimization

§Structural Analysis

connected_components - Find all connected components in the graph
weakly_connected_components - Find weakly connected components (undirected connectivity)
strongly_connected_components - Find strongly connected components using Tarjan’s algorithm
cycle_basis - Minimal cycle basis for cycle explanation (Paton’s algorithm)
cycle_basis_bounded - Cycle basis with bounded enumeration
cycle_basis_with_progress - Cycle basis with progress tracking
CycleBasisBounds - Configuration for bounds (max_cycles, max_cycle_length, max_per_scc)
CycleBasisResult - Result with cycles, SCC decomposition, helpers
find_cycles_limited - Enumerate cycles up to a limit
nodes_by_degree - Rank nodes by degree (hub detection)
topological_sort - Compute topological ordering of nodes in DAGs

§Dependency Analysis

critical_path - Longest weighted path in DAG for bottleneck identification
critical_path_with_progress - Critical path with progress tracking
CriticalPathResult - Result with path, distance, bottlenecks, slack
CriticalPathError - Error for non-DAG graphs

§Reachability Analysis

transitive_closure - Compute all-pairs reachability (can reach relationships)
transitive_reduction - Remove redundant edges while preserving reachability
TransitiveClosureBounds - Bounds for limiting transitive closure computation
reachable_from - Forward reachability (what does this affect?)
reverse_reachable_from - Backward reachability (what affects this?)
can_reach - Point-to-point reachability check
unreachable_from - Find unreachable nodes from entry

§Control Flow Analysis

dominators - Compute dominators and immediate dominator tree
dominators_with_progress - Dominator computation with progress tracking
DominatorResult - Dominance sets and immediate dominator tree
post_dominators - Compute post-dominators and immediate post-dominator tree
post_dominators_with_progress - Post-dominator computation with progress tracking
post_dominators_auto_exit - Post-dominators with automatic exit detection
PostDominatorResult - Post-dominance sets and immediate post-dominator tree
dominance_frontiers - Compute dominance frontiers for SSA construction
dominance_frontiers_with_progress - Dominance frontier computation with progress tracking
iterated_dominance_frontiers - Compute iterated dominance frontiers for SSA φ-placement
DominanceFrontierResult - Dominance frontier sets
IteratedDominanceFrontierResult - Iterated dominance frontier result with φ-node placements
natural_loops - Detect natural loops using back-edge dominance analysis
natural_loops_with_progress - Natural loop detection with progress tracking
NaturalLoop - Natural loop with header, back-edges, and body
NaturalLoopsResult - Natural loop detection result with nesting analysis
control_dependence_graph - Compute Control Dependence Graph from post-dominators
control_dependence_from_exit - Compute CDG with automatic exit detection
ControlDependenceResult - Control dependence edges and reverse mapping

§Program Analysis

backward_slice - Backward program slicing (what affects this node?)
backward_slice_with_progress - Backward slicing with progress tracking
forward_slice - Forward program slicing (what does this affect?)
forward_slice_with_progress - Forward slicing with progress tracking
SliceResult - Result with control_nodes, data_nodes, and slice_nodes

§Call Graph Analysis

collapse_sccs - Collapse SCCs to form condensation DAG for call graph analysis
collapse_sccs_with_progress - SCC collapse with progress tracking
SccCollapseResult - Result with node_to_supernode, supernode_members, supernode_edges

§Cut and Partitioning

min_st_cut - Minimum s-t edge cut for fault tolerance analysis
min_st_cut_with_progress - Minimum s-t edge cut with progress tracking
min_vertex_cut - Minimum vertex cut for critical node identification
min_vertex_cut_with_progress - Minimum vertex cut with progress tracking
MinCutResult - Result of minimum edge cut computation
MinVertexCutResult - Result of minimum vertex cut computation
partition_bfs_level - BFS-level graph partitioning for sharding
partition_greedy - Greedy partitioning with boundary improvement
partition_kway - Size-bounded k-way partitioning
partition_kway_with_progress - K-way partitioning with progress tracking
PartitionConfig - Configuration for k-way partitioning
PartitionResult - Result of graph partitioning computation

§Path Analysis

enumerate_paths - Enumerate all execution paths using DFS with bounds
enumerate_paths_with_progress - Path enumeration with progress tracking
enumerate_paths_with_dominance - Path enumeration with dominance-based pruning
enumerate_paths_with_dominance_progress - Dominance-constrained enumeration with progress tracking
PathEnumerationConfig - Configuration for bounds (max_depth, max_paths, revisit_cap)
PathEnumerationDominanceConfig - Configuration for constraint-based pruning
PathClassification - Path classification (Normal, Error, Degenerate, Infinite)
EnumeratedPath - Single execution path with nodes and classification
PathEnumerationResult - Enumeration result with categorized paths and statistics
PathEnumerationPruningStats - Statistics for dominance-based pruning effectiveness

§Observability Algorithms

happens_before_analysis - Event ordering for concurrent trace analysis
impact_radius - Blast zone computation using bounded reachability
impact_radius_with_progress - Impact radius with progress tracking
VectorClock - Partial order data structure for happens-before analysis
HappensBeforeResult - Result with concurrent pairs and race statistics
ImpactRadiusConfig - Configuration for impact radius (max_distance, max_hops, weight_fn)
ImpactRadiusResult - Result with blast_zone, distances, boundary, size
TraceEvent - Runtime trace event representation
Operation - Memory operation type (Read/Write)

Note: WeightCallback and default_weight_fn are re-exported from the dependency analysis section for use with impact radius computation.

§ML / Inference

find_subgraph_patterns - Bounded subgraph isomorphism for pattern matching
find_subgraph_patterns_with_progress - Subgraph isomorphism with progress tracking
SubgraphPatternBounds - Configuration for bounds (max_matches, timeout_ms, max_pattern_nodes)
SubgraphMatchResult - Result with matches, patterns_found, computation_time_ms, bounded_hit
structural_similarity - Structural similarity using isomorphism checking and MCS approximation
structural_similarity_with_progress - Structural similarity with progress tracking
SimilarityBounds - Configuration for bounds (max_matches, timeout_ms, similarity_threshold)
SimilarityResult - Result with isomorphic, mcs_similarity, ged_distance, mcs_size
rewrite_graph_patterns - DPO-style graph rewriting for pattern transformation
rewrite_graph_patterns_with_progress - Graph rewriting with progress tracking
RewriteRule - Rule specifying pattern, replacement, and interface
RewriteBounds - Configuration for bounds (max_matches, validation)
RewriteResult - Result with rewritten_graph, operations_applied, validation_errors

§Graph Diff

graph_diff() - Structural graph delta between two snapshots
graph_diff_with_progress() - Graph diff with progress tracking
validate_refactor() - Refactor validation with safety heuristics
GraphDiffResult - Result with nodes/edges added/removed and similarity metrics
NodeDelta - Node delta (nodes_added, nodes_removed)
EdgeDelta - Edge delta (edges_added, edges_removed)
RefactorValidation - Validation result with is_safe, breaking_changes, warnings

§Security & Compliance

propagate_taint_forward() - Forward taint propagation from sources to sinks
propagate_taint_forward_with_progress() - Forward propagation with progress tracking
propagate_taint_backward() - Backward taint propagation from sink to sources
propagate_taint_backward_with_progress() - Backward propagation with progress tracking
sink_reachability_analysis() - Full vulnerability detection (all sinks)
sink_reachability_analysis_with_progress() - Sink analysis with progress tracking
discover_sources_and_sinks() - Discover sources/sinks using custom callbacks
discover_sources_and_sinks_default() - Discover using metadata-based detectors
TaintResult - Result with sources, sinks_reached, tainted_nodes, source_sink_paths
SourceCallback - Trait for custom source detection
SinkCallback - Trait for custom sink detection
MetadataSourceDetector - Default source detector using entity metadata
MetadataSinkDetector - Default sink detector using entity metadata

§Algorithm Characteristics

Algorithm	Time Complexity	Best For	Limitations
PageRank	O(k × (V + E))	Influence ranking	Requires connected graph for best results
Betweenness	O(V × (V + E))	Bridge nodes	Expensive on large graphs
Label Propagation	O(k × E)	Fast clustering	Non-deterministic tiebreaking
Louvain	O(k × V × E)	Quality communities	Slower than label propagation
Connected Components	O(V + E)	Graph connectivity	None
Weakly Connected Components	O(V + E)	Undirected connectivity	None
Strongly Connected Components	O(V + E)	Cycle detection, loop analysis	None
Cycle Basis	O(V + E + C×V)	Cycle explanation, deadlock detection	C = number of cycles
Transitive Closure	O(V × (V + E))	All-pairs reachability	O(V²) space, use bounds for large graphs
Transitive Reduction	O(V × (V + E))	Graph simplification	Most meaningful for DAGs
Topological Sort	O(V + E)	Linear ordering of DAGs	Requires DAG (returns cycle error)
Critical Path	O(V + E)	Build systems, bottleneck identification	Requires DAG
Reachability	O(V + E)	Impact analysis, slicing	None
Dominators	O(V²) worst, faster in practice	CFG analysis, SSA construction	Requires single entry
Post-Dominators	O(V²) worst, faster in practice	CFG analysis, control dependence	Requires single exit or virtual exit
Dominance Frontiers	O(V²) worst	SSA φ-node placement, convergence points	Requires dominators
Iterated DF	O(V × iterations)	SSA construction, φ-node placement	Fixed-point iteration
Natural Loops	O(E × N) worst	Loop optimization, program analysis	Requires dominators
Control Dependence	O(E) after post-dom	Program slicing, impact analysis	Requires post-dominators
Program Slicing	O(V + E)	Bug isolation, impact analysis	Requires CDG + reachability
SCC Collapse	O(V + E)	Call graph analysis, mutual recursion detection	None
Path Enumeration	O(P × L)	Test coverage, symbolic execution	Bounds required for cyclic CFGs
Path Enumeration (Dominance)	O(P² × L) amortized	Path pruning for complex CFGs	Requires dominators, control dependence, natural loops
Min s-t Edge Cut	O(V × E²)	Fault tolerance, security boundaries	Requires connected source/sink
Min Vertex Cut	O(V × E²)	Critical node identification	Requires connected source/sink
BFS-Level Partitioning	O(V + E)	Graph sharding, locality	Local optimum based on seeds
Greedy Partitioning	O(I × E)	Cut minimization	Local optimum (I = iterations)
K-way Partitioning	O(V + E)	Multi-way sharding, load balancing	Requires k >= 2

Where:

V = number of vertices
E = number of edges
P = number of paths
L = average path length
k = number of iterations (algorithm-dependent)

§Input Requirements

§Graph Connectivity

Connected components: Works on disconnected graphs (finds all components)
Weakly connected components: Works on disconnected graphs (finds all components treating edges as undirected)
Strongly connected components: Works on disconnected graphs (finds all SCCs including trivial)
Topological sort: Only works on DAGs (returns cycle error with cycle path for cyclic graphs)
PageRank: Handles disconnected components (splits rank)
Betweenness: Handles disconnected components (each component separately)
Label propagation: Works on disconnected graphs (each component independently)
Louvain: Works on disconnected graphs (each component independently)
Transitive closure: Works on disconnected graphs (each component independently)
Transitive reduction: Works on disconnected graphs (each component independently)

§Edge Directionality

All algorithms support directed graphs:

Pagerank: Follows outgoing edges (link-based ranking)
Betweenness: Considers both directions for shortest paths
Label propagation: Uses bidirectional edges (undirected view)
Louvain: Uses bidirectional edges (undirected view)

§Output Format

§Centrality Algorithms

Return Vec<(NodeId, Score)> sorted by score descending:

let results = pagerank(&graph)?;

// Top 5 most influential nodes
for (node_id, score) in results.iter().take(5) {
    println!("Node {}: PageRank = {:.4}", node_id, score);
}

§Community Detection

Return Vec<Vec<NodeId>> where each inner vector is a community:

let communities = louvain_communities(&graph)?;

println!("Found {} communities", communities.len());
for (i, community) in communities.iter().enumerate() {
    println!("Community {}: {} nodes", i, community.len());
}

§Usage Patterns

§When to Use PageRank

Identify influential nodes in citation networks
Rank web pages or documents by link structure
Find key entities in knowledge graphs
Recommendation systems based on graph structure

§When to Use Betweenness Centrality

Find bridge nodes connecting communities
Identify bottlenecks in communication networks
Detect control points in flow networks
Analyze information flow in social networks

§When to Use Label Propagation

Fast community detection on large graphs
Exploratory analysis where speed matters more than quality
Baseline comparison for other clustering methods
Incremental clustering where results update frequently

§When to Use Louvain

High-quality community detection where modularity matters
Hierarchical clustering to reveal multi-scale structure
Research applications requiring reproducible results
Final clustering when offline computation is acceptable

§Progress Tracking

Long-running algorithms provide _with_progress variants:

use sqlitegraph::{
    algo::pagerank_with_progress,
    progress::ConsoleProgress
};

let progress = ConsoleProgress::new();
let results = pagerank_with_progress(&graph, progress)?;
// Output: PageRank iteration 10/100...

Progress tracking is available for:

Use [NoProgress] for zero-overhead progress tracking (default).

Re-exports§

pub use backend::pagerank as pagerank_backend;
pub use backend::betweenness_centrality as betweenness_centrality_backend;
pub use backend::strongly_connected_components as scc_backend;
pub use backend::shortest_path as shortest_path_backend;
pub use backend::topological_sort as topological_sort_backend;
pub use backend::bfs_traversal;
pub use backend::dfs_traversal;
pub use backend::k_hop_neighbors;

Modules§

backend: Generic graph algorithms using GraphBackend trait

Structs§

ControlDependenceResult: Control Dependence Graph result.
CriticalPathResult: Result of critical path analysis on a DAG.
CycleBasisBounds: Bounds for limiting cycle basis computation.
CycleBasisResult: Result of minimal cycle basis computation.
DominanceFrontierResult: Dominance frontier result for a CFG.
DominatorResult: Result of dominator computation.
EdgeDelta: Result of computing edge delta between two graphs.
EnumeratedPath: A single execution path through the CFG.
GraphDiffResult: Complete graph diff result with delta and similarity metrics.
HappensBeforeResult: Result of happens-before analysis on trace events.
ImpactRadiusConfig: Configuration for impact radius computation.
ImpactRadiusResult: Result of impact radius computation.
IteratedDominanceFrontierResult: Iterated dominance frontier result (for SSA φ-placement).
MetadataSinkDetector: Default sink detector using entity metadata.
MetadataSourceDetector: Default source detector using entity metadata.
MinCutResult: Result of minimum s-t edge cut computation.
MinVertexCutResult: Result of minimum vertex cut computation.
NaturalLoop: A natural loop identified by back-edges.
NaturalLoopsResult: Natural loop detection result.
NodeDelta: Result of computing node delta between two graphs.
PartitionConfig: Configuration for k-way partitioning.
PartitionResult: Result of graph partitioning computation.
PathEnumerationConfig: Configuration for path enumeration.
PathEnumerationDominanceConfig: Extended configuration for dominance-constrained enumeration.
PathEnumerationPruningStats: Statistics for dominance-based pruning.
PathEnumerationResult: Result of path enumeration.
PostDominatorResult: Result of post-dominator computation.
RefactorValidation: Validation result for refactor checking.
RewriteBounds: Bounds for limiting graph rewriting operations.
RewriteResult: Result of a graph rewriting operation.
RewriteRule: A rewrite rule for DPO-style graph transformation.
SccCollapseResult: Result of SCC collapse operation (condensation graph).
SccResult: Result of strongly connected components decomposition.
SimilarityBounds: Bounds for limiting structural similarity computation.
SimilarityResult: Result of structural similarity computation.
SliceResult: Result of a program slicing operation.
SubgraphMatchResult: Result of subgraph isomorphism search.
SubgraphPatternBounds: Bounds for limiting subgraph isomorphism search.
TaintResult: Result of taint analysis operation.
TraceEvent: Trace event from concurrent program execution.
TransitiveClosureBounds: Bounds for transitive closure computation.
VectorClock: Vector clock for happens-before analysis.

Enums§

CriticalPathError: Error type for critical path analysis.
Operation: Memory operation type in trace events.
PathClassification: Path classification based on termination properties.
RewriteOperation: A single rewrite operation for tracking changes.
TopoError: Error type for topological sort.

Traits§

SinkCallback: Callback trait for detecting security-sensitive sinks.
SourceCallback: Callback trait for detecting taint sources.

Functions§

backward_slice: Computes backward program slice: “what can affect this node?”
backward_slice_with_progress: Computes backward slice with progress tracking.
betweenness_centrality: Computes betweenness centrality for all nodes in the graph.
betweenness_centrality_with_progress: Computes betweenness centrality with progress callback reporting.
can_reach: Checks if one node can reach another (point-to-point reachability).
collapse_sccs: Collapses SCCs to form a condensation DAG.
collapse_sccs_with_progress: Collapses SCCs with progress tracking.
connected_components: Finds all connected components in the graph using BFS.
control_dependence_from_exit: Computes control dependence with automatic exit detection.
control_dependence_graph: Computes the Control Dependence Graph (CDG) using Cytron et al. edge-based definition.
critical_path: Computes the critical path (longest weighted path) in a DAG.
critical_path_with_progress: Computes the critical path with progress tracking.
cycle_basis: Computes minimal cycle basis using Paton’s algorithm.
cycle_basis_bounded: Computes cycle basis with bounded enumeration.
cycle_basis_with_progress: Computes cycle basis with progress tracking.
default_weight_fn: Default weight function that returns 1.0 for all edges.
discover_sources_and_sinks: Discovers all sources and sinks in the graph using custom callbacks.
discover_sources_and_sinks_default: Discovers sources and sinks using default metadata-based detectors.
dominance_frontiers: Computes dominance frontiers for a CFG using Cytron et al. efficient algorithm.
dominance_frontiers_with_progress: Computes dominance frontiers with progress tracking.
dominators: Computes dominators and immediate dominators for a CFG entry node.
dominators_with_progress: Computes dominators with progress tracking.
enumerate_paths: Enumerates all execution paths from entry node using DFS with bounds.
enumerate_paths_with_dominance: Enumerates all execution paths with dominance-based pruning.
enumerate_paths_with_dominance_progress: Enumerates all execution paths with dominance-based pruning and progress tracking.
enumerate_paths_with_progress: Enumerates all execution paths with progress tracking.
find_cycles_limited: Finds cycles in the graph up to a specified limit.
find_subgraph_patterns: Finds all subgraph isomorphisms of pattern within graph.
find_subgraph_patterns_with_progress: Finds all subgraph isomorphisms with progress tracking.
forward_slice: Computes forward program slice: “what does this node affect?”
forward_slice_with_progress: Computes forward slice with progress tracking.
graph_diff: Computes structural graph diff between two snapshots.
graph_diff_with_progress: Computes structural graph diff with progress tracking.
happens_before_analysis: Analyze trace events for concurrent memory access pairs (race detection).
impact_radius: Computes the impact radius from a source node using bounded weighted BFS.
impact_radius_with_progress: Computes the impact radius with progress tracking.
iterated_dominance_frontiers: Computes iterated dominance frontier for SSA φ-placement.
label_propagation: Label Propagation algorithm for fast community detection.
louvain_communities: Louvain method for community detection via modularity optimization.
louvain_communities_with_progress: Louvain method for community detection with progress callback reporting.
min_st_cut: Compute minimum s-t edge cut using max-flow min-cut theorem.
min_st_cut_with_progress: Compute minimum s-t edge cut with progress tracking.
min_vertex_cut: Compute minimum vertex cut using vertex splitting transformation.
min_vertex_cut_with_progress: Compute minimum vertex cut with progress tracking.
natural_loops: Computes natural loops by finding back-edges where header dominates tail.
natural_loops_from_exit: Computes natural loops with automatic entry node detection.
natural_loops_with_progress: Computes natural loops with progress tracking.
nodes_by_degree: Computes node degrees (total number of incoming + outgoing edges).
pagerank: Computes PageRank scores for all nodes in the graph.
pagerank_with_progress: Computes PageRank scores with progress callback reporting.
partition_bfs_level: Partition graph using BFS-level assignment.
partition_greedy: Partition graph using greedy iterative boundary improvement.
partition_kway: Partition graph into k balanced partitions using BFS growth from seeds.
partition_kway_with_progress: Partition graph into k balanced partitions with progress tracking.
post_dominators: Computes post-dominators and immediate post-dominators for a CFG exit node.
post_dominators_auto_exit: Computes post-dominators with automatic exit detection.
post_dominators_with_progress: Computes post-dominators with progress tracking.
propagate_taint_backward: Propagates taint backward from a sink to find affecting sources.
propagate_taint_backward_with_progress: Propagates taint backward with progress tracking.
propagate_taint_forward: Propagates taint forward from sources to find reachable sinks.
propagate_taint_forward_with_progress: Propagates taint forward with progress tracking.
reachable_from: Computes forward reachability from a start node.
reachable_from_with_progress: Computes forward reachability with progress tracking.
reverse_reachable_from: Computes backward reachability to a target node.
reverse_reachable_from_with_progress: Computes backward reachability with progress tracking.
rewrite_graph_patterns: Applies rewrite rules to transform a graph using DPO-style rewriting.
rewrite_graph_patterns_with_progress: Applies rewrite rules with progress tracking.
sink_reachability_analysis: Performs sink reachability analysis for all sinks.
sink_reachability_analysis_with_progress: Performs sink reachability analysis with progress tracking.
strongly_connected_components: Computes strongly connected components using Tarjan’s algorithm.
structural_similarity: Computes structural similarity between two graphs.
structural_similarity_with_progress: Computes structural similarity with progress tracking.
topological_sort: Computes topological ordering of nodes in a directed graph.
transitive_closure: Computes transitive closure for all-pairs reachability.
transitive_closure_with_progress: Computes transitive closure with progress callback reporting.
transitive_reduction: Computes transitive reduction to remove redundant edges from a DAG.
transitive_reduction_with_progress: Computes transitive reduction with progress callback reporting.
unreachable_from: Finds nodes unreachable from an entry point.
validate_refactor: Validates whether a graph diff represents a safe refactor.
weakly_connected_components: Finds all weakly connected components in the graph using bidirectional BFS.
weakly_connected_components_with_progress: Finds all weakly connected components with progress tracking.

Type Aliases§

WeightCallback: Weight callback type for edge weighting.

Module algo

Module algo Copy item path

§Available Algorithms

§Centrality Algorithms

§Community Detection

§Structural Analysis

§Dependency Analysis

§Reachability Analysis

§Control Flow Analysis

§Program Analysis

§Call Graph Analysis

§Cut and Partitioning

§Path Analysis

§Observability Algorithms

§ML / Inference

§Graph Diff

§Security & Compliance

§Algorithm Characteristics

§Input Requirements

§Graph Connectivity

§Edge Directionality

§Output Format

§Centrality Algorithms

§Community Detection

§Usage Patterns

§When to Use PageRank

§When to Use Betweenness Centrality

§When to Use Label Propagation

§When to Use Louvain

§Progress Tracking

Re-exports§

Modules§

Structs§

Enums§

Traits§

Functions§

Type Aliases§

Module algo