strongly_connected_components/internal/
scc_decomposition.rs

1use crate::internal::node::Node;
2use crate::internal::scc::Scc;
3
4/// Represents the decomposition of a [`Graph`](crate::Graph) into
5/// [Strongly Connected Components](https://en.wikipedia.org/wiki/Strongly_connected_component)
6/// (SCC).
7pub struct SccDecomposition {
8    pub(super) nodes_to_sccs: Vec<usize>,
9    pub(super) sccs: Vec<Scc>,
10}
11
12impl SccDecomposition {
13    /// Returns the number of SCCs in the decomposition.
14    pub fn len(&self) -> usize {
15        self.sccs.len()
16    }
17
18    /// Returns `true` if there are no SCCs.
19    pub fn is_empty(&self) -> bool {
20        self.sccs.is_empty()
21    }
22
23    /// Returns the SCC containing the given node.
24    /// Each node of the [`Graph`](crate::Graph) will always
25    /// be assigned to exactly one SCC.
26    pub fn scc_of_node(&self, node: Node) -> &Scc {
27        assert!(node.id < self.nodes_to_sccs.len());
28        let scc_id = self.nodes_to_sccs[node.id];
29        assert!(scc_id < self.sccs.len());
30        &self.sccs[scc_id]
31    }
32
33    /// Returns an iterator over all SCCs in topological order.
34    /// If nodes `A` and `B` belong to different SCCs
35    /// and the graph has an edge `A->B`, then `B`'s SCC will appear before `A`'s SCC.
36    pub fn iter_sccs(&self) -> impl Iterator<Item = &Scc> {
37        self.sccs.iter()
38    }
39
40    /// Returns an iterator over all nodes in topological order.
41    /// If nodes `A` and `B` belong to different SCCs
42    /// and the graph has an edge `A->B`, then `B` will appear before `A`.
43    pub fn iter_nodes(&self) -> impl Iterator<Item = Node> + '_ {
44        self.sccs.iter().flat_map(|sccs| sccs.iter_nodes())
45    }
46}
strongly_connected_components/internal/scc_decomposition.rs

strongly_connected_components/internal/
scc_decomposition.rs
