Function strongly_connected_components 

pub fn strongly_connected_components(
    graph: &SqliteGraph,
) -> Result<SccResult, SqliteGraphError>

Computes strongly connected components using Tarjan’s algorithm.

A strongly connected component (SCC) is a maximal subgraph where every node can reach every other node. This function finds all SCCs in the graph using Tarjan’s single-pass DFS algorithm.

Arguments

• graph - The graph to analyze

Returns

SccResult containing:

• List of components (each component is a set of node IDs)
• Node-to-component mapping
• Condensed DAG edges (between SCCs)

Components are returned in reverse topological order

The first components in the result are sink SCCs (no outgoing edges to other SCCs). This is useful for algorithms that process components in topological order.

Example

use sqlitegraph::{SqliteGraph, algo::strongly_connected_components};

let graph = SqliteGraph::open_in_memory()?;
// ... add nodes and edges ...
let scc = strongly_connected_components(&graph)?;

println!("Found {} SCCs", scc.components.len());
println!("Non-trivial SCCs (cycles): {}", scc.non_trivial_count());

Complexity

Time: O(|V| + |E|) - single DFS pass Space: O(|V|) for stack, indices, and lowlink maps

Edge Cases

• Empty graph: Returns empty SccResult
• Single node: One component with one node
• Disconnected graph: Multiple components (may all be trivial)
• Linear chain: Each node is its own SCC (all trivial)
• Simple cycle: One non-trivial SCC containing all nodes