graph_advanced/
condensation.rs

1use crate::tarjan_scc;
2use graph_core::{Graph, NodeId};
3use std::collections::HashMap;
4
5/// The result of condensing a directed graph into its SCC DAG.
6///
7/// Each node in the condensed graph represents one SCC of the original graph.
8/// The condensed graph is always a DAG (directed acyclic graph).
9#[derive(Debug, Clone)]
10pub struct CondensedGraph {
11    /// `components[i]` is the list of original [`NodeId`]s that belong to
12    /// super-node `i` in the condensed graph.
13    pub components: Vec<Vec<NodeId>>,
14    /// Edges of the condensed DAG.
15    ///
16    /// `edges[i]` is the list of super-node indices that super-node `i` has
17    /// a directed edge to. Self-loops (SCC to itself) are not included.
18    pub edges: Vec<Vec<usize>>,
19}
20
21impl CondensedGraph {
22    /// Returns the number of super-nodes (SCCs) in the condensed graph.
23    #[inline]
24    pub fn node_count(&self) -> usize {
25        self.components.len()
26    }
27}
28
29/// Condenses a directed graph into its **SCC DAG**.
30///
31/// Each strongly connected component (SCC) is collapsed into a single
32/// super-node. The resulting graph is always a DAG — any cycle that existed
33/// in the original graph is now internal to a single super-node.
34///
35/// Uses [`tarjan_scc()`] internally to compute the SCCs.
36///
37/// # Returns
38///
39/// A [`CondensedGraph`] where:
40/// - `components[i]` lists the original nodes that form super-node `i`.
41/// - `edges[i]` lists which super-nodes super-node `i` has edges to.
42///
43/// # Complexity
44///
45/// O(V + E) — dominated by the SCC computation.
46///
47/// # Examples
48///
49/// ```
50/// use graph_core::{AdjacencyList, Graph};
51/// use graph_advanced::condensation;
52///
53/// // 0 ↔ 1  (one SCC),  2 is a singleton,  edge 0→2.
54/// let mut g: AdjacencyList<()> = AdjacencyList::directed();
55/// let n: Vec<_> = (0..3).map(|_| g.add_node(())).collect();
56/// g.add_edge(n[0], n[1], 1.0).unwrap();
57/// g.add_edge(n[1], n[0], 1.0).unwrap();
58/// g.add_edge(n[0], n[2], 1.0).unwrap();
59///
60/// let cg = condensation(&g);
61/// assert_eq!(cg.node_count(), 2); // two SCCs
62/// // There must be exactly one inter-SCC edge.
63/// let total_edges: usize = cg.edges.iter().map(|e| e.len()).sum();
64/// assert_eq!(total_edges, 1);
65/// ```
66pub fn condensation<G>(graph: &G) -> CondensedGraph
67where
68    G: Graph<Weight = f64>,
69{
70    let sccs = tarjan_scc(graph);
71
72    // Map every original NodeId to its SCC index.
73    let mut node_to_scc: HashMap<NodeId, usize> = HashMap::new();
74    for (scc_idx, scc) in sccs.iter().enumerate() {
75        for &node in scc {
76            node_to_scc.insert(node, scc_idx);
77        }
78    }
79
80    let num_sccs = sccs.len();
81    let mut edge_set: Vec<std::collections::HashSet<usize>> =
82        vec![std::collections::HashSet::new(); num_sccs];
83
84    for node in graph.nodes() {
85        let from_scc = node_to_scc[&node];
86        for (neighbour, _) in graph.neighbors(node) {
87            let to_scc = node_to_scc[&neighbour];
88            if from_scc != to_scc {
89                edge_set[from_scc].insert(to_scc);
90            }
91        }
92    }
93
94    let edges: Vec<Vec<usize>> = edge_set
95        .into_iter()
96        .map(|s| s.into_iter().collect())
97        .collect();
98
99    CondensedGraph {
100        components: sccs,
101        edges,
102    }
103}
graph_advanced/condensation.rs

graph_advanced/
condensation.rs
