graph_advanced/
tarjan_scc.rs

1use graph_core::{Graph, NodeId};
2use std::collections::HashMap;
3
4/// Finds all **Strongly Connected Components** (SCCs) using Tarjan's algorithm.
5///
6/// A strongly connected component is a maximal set of nodes where every node
7/// is reachable from every other node via directed edges.
8///
9/// # Algorithm
10///
11/// A single DFS pass assigns each node a **discovery time** (`disc`) and a
12/// **low-link value** (`low[u]`): the smallest discovery time reachable from
13/// the subtree rooted at `u` via tree edges and at most one back-edge.
14///
15/// Nodes are pushed onto a stack as they are discovered. When we finish
16/// processing node `u` and find `low[u] == disc[u]`, `u` is the root of an
17/// SCC: we pop the stack until we reach `u`, and all popped nodes form one SCC.
18///
19/// # Returns
20///
21/// A `Vec` of SCCs, each SCC being a `Vec<NodeId>`. Components are returned
22/// in **reverse topological order** of the condensed DAG: if there is an edge
23/// from SCC A to SCC B, then B appears before A in the result.
24///
25/// # Complexity
26///
27/// O(V + E) — a single DFS pass over all nodes and edges.
28///
29/// # Examples
30///
31/// ```
32/// use graph_core::{AdjacencyList, Graph};
33/// use graph_advanced::tarjan_scc;
34///
35/// // Two-node cycle: {0, 1} form one SCC; {2} is its own.
36/// //   0 → 1 → 0
37/// //   1 → 2
38/// let mut g: AdjacencyList<()> = AdjacencyList::directed();
39/// let n: Vec<_> = (0..3).map(|_| g.add_node(())).collect();
40/// g.add_edge(n[0], n[1], 1.0).unwrap();
41/// g.add_edge(n[1], n[0], 1.0).unwrap();
42/// g.add_edge(n[1], n[2], 1.0).unwrap();
43///
44/// let sccs = tarjan_scc(&g);
45/// assert_eq!(sccs.len(), 2);
46/// ```
47pub fn tarjan_scc<G>(graph: &G) -> Vec<Vec<NodeId>>
48where
49    G: Graph<Weight = f64>,
50{
51    let mut state = TarjanState {
52        disc: HashMap::new(),
53        low: HashMap::new(),
54        on_stack: HashMap::new(),
55        stack: Vec::new(),
56        timer: 0,
57        result: Vec::new(),
58    };
59
60    for node in graph.nodes() {
61        if !state.disc.contains_key(&node) {
62            dfs_tarjan(graph, node, &mut state);
63        }
64    }
65
66    state.result
67}
68
69struct TarjanState {
70    disc: HashMap<NodeId, usize>,
71    low: HashMap<NodeId, usize>,
72    on_stack: HashMap<NodeId, bool>,
73    stack: Vec<NodeId>,
74    timer: usize,
75    result: Vec<Vec<NodeId>>,
76}
77
78fn dfs_tarjan<G>(graph: &G, node: NodeId, state: &mut TarjanState)
79where
80    G: Graph<Weight = f64>,
81{
82    state.disc.insert(node, state.timer);
83    state.low.insert(node, state.timer);
84    state.timer += 1;
85    state.on_stack.insert(node, true);
86    state.stack.push(node);
87
88    for (neighbour, _) in graph.neighbors(node) {
89        if !state.disc.contains_key(&neighbour) {
90            // Tree edge: recurse and pull up low-link.
91            dfs_tarjan(graph, neighbour, state);
92            let child_low = state.low[&neighbour];
93            let node_low = state.low.get_mut(&node).unwrap();
94            if child_low < *node_low {
95                *node_low = child_low;
96            }
97        } else if *state.on_stack.get(&neighbour).unwrap_or(&false) {
98            // Back edge to a node still on the stack (in current SCC).
99            let neighbour_disc = state.disc[&neighbour];
100            let node_low = state.low.get_mut(&node).unwrap();
101            if neighbour_disc < *node_low {
102                *node_low = neighbour_disc;
103            }
104        }
105    }
106
107    // If node is the root of an SCC, pop the stack to collect the component.
108    if state.low[&node] == state.disc[&node] {
109        let mut scc = Vec::new();
110        loop {
111            let w = state
112                .stack
113                .pop()
114                .expect("stack must not be empty during SCC pop");
115            state.on_stack.insert(w, false);
116            scc.push(w);
117            if w == node {
118                break;
119            }
120        }
121        state.result.push(scc);
122    }
123}
graph_advanced/tarjan_scc.rs

graph_advanced/
tarjan_scc.rs
