guppy/petgraph_support/scc.rs
1// Copyright (c) The cargo-guppy Contributors
2// SPDX-License-Identifier: MIT OR Apache-2.0
3
4use ahash::AHashMap;
5use fixedbitset::FixedBitSet;
6use nested::Nested;
7use petgraph::{
8 algo::kosaraju_scc,
9 graph::IndexType,
10 prelude::*,
11 visit::{IntoNeighborsDirected, IntoNodeIdentifiers, VisitMap, Visitable},
12};
13use std::slice;
14
15#[derive(Clone, Debug)]
16pub(crate) struct Sccs<Ix: IndexType> {
17 sccs: Nested<Vec<NodeIndex<Ix>>>,
18 // Map of node indexes to the index of the SCC they belong to. If a node is not part of an SCC,
19 // then the corresponding index is not stored here.
20 multi_map: AHashMap<NodeIndex<Ix>, usize>,
21}
22
23impl<Ix: IndexType> Sccs<Ix> {
24 /// Creates a new instance from the provided graph and the given sorter.
25 pub fn new<G>(graph: G, mut scc_sorter: impl FnMut(&mut Vec<NodeIndex<Ix>>)) -> Self
26 where
27 G: IntoNeighborsDirected<NodeId = NodeIndex<Ix>> + Visitable + IntoNodeIdentifiers,
28 <G as Visitable>::Map: VisitMap<NodeIndex<Ix>>,
29 {
30 // Use kosaraju_scc since it is iterative (tarjan_scc is recursive) and package graphs
31 // have unbounded depth.
32 let sccs = kosaraju_scc(graph);
33 let sccs: Nested<Vec<_>> = sccs
34 .into_iter()
35 .map(|mut scc| {
36 if scc.len() > 1 {
37 scc_sorter(&mut scc);
38 }
39 scc
40 })
41 // kosaraju_scc returns its sccs in reverse topological order. Reverse it again for
42 // forward topological order.
43 .rev()
44 .collect();
45 let mut multi_map = AHashMap::new();
46 for (idx, scc) in sccs.iter().enumerate() {
47 if scc.len() > 1 {
48 multi_map.extend(scc.iter().map(|ix| (*ix, idx)));
49 }
50 }
51 Self { sccs, multi_map }
52 }
53
54 /// Returns true if `a` and `b` are in the same scc.
55 ///
56 /// Every node is in its own (possibly single-element) SCC, so this is
57 /// reflexive: `is_same_scc(a, a)` is always `true`. This is the SCC
58 /// equivalence relation; it is *not* a cycle-membership predicate.
59 /// Callers that want to know whether two nodes lie on a common cycle
60 /// should additionally check [`Sccs::in_multi_scc`] and/or whether the
61 /// node has a self-loop edge.
62 pub fn is_same_scc(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool {
63 if a == b {
64 return true;
65 }
66 match (self.multi_map.get(&a), self.multi_map.get(&b)) {
67 (Some(a_scc), Some(b_scc)) => a_scc == b_scc,
68 _ => false,
69 }
70 }
71
72 /// Returns true if `ix` belongs to an SCC with more than one element.
73 ///
74 /// A multi-node SCC is, by definition, non-trivial: every pair of its
75 /// members lies on a directed cycle. Combined with a self-loop check on
76 /// `ix`, this is enough to decide whether a node lies on any cycle.
77 pub fn in_multi_scc(&self, ix: NodeIndex<Ix>) -> bool {
78 self.multi_map.contains_key(&ix)
79 }
80
81 /// Returns all the SCCs of this graph in forward topological order,
82 /// including single-node SCCs.
83 ///
84 /// [`Sccs`] does not store edge information, so callers that care
85 /// about *cyclic* SCCs -- multi-node SCCs plus single-node SCCs with a
86 /// self-loop -- must consult the underlying graph for the self-loop
87 /// check themselves.
88 pub fn all_sccs(&self) -> impl DoubleEndedIterator<Item = &[NodeIndex<Ix>]> {
89 self.sccs.iter()
90 }
91
92 /// Returns all the nodes that have no incoming edges from outside their
93 /// own SCC.
94 ///
95 /// Edges *within* an SCC -- including self-loop edges on single-node SCCs
96 /// -- don't disqualify a node. The result is one representative per
97 /// external multi-node SCC, plus every single-node SCC whose only
98 /// incoming edge (if any) is a self-loop.
99 pub fn externals<'a, G>(&'a self, graph: G) -> impl Iterator<Item = NodeIndex<Ix>> + 'a
100 where
101 G: 'a + IntoNodeIdentifiers + IntoNeighborsDirected<NodeId = NodeIndex<Ix>>,
102 Ix: IndexType,
103 {
104 // Consider each SCC as one logical node.
105 let mut external_sccs = FixedBitSet::with_capacity(self.sccs.len());
106 let mut internal_sccs = FixedBitSet::with_capacity(self.sccs.len());
107 graph
108 .node_identifiers()
109 .filter(move |ix| match self.multi_map.get(ix) {
110 Some(&scc_idx) => {
111 // Consider one node identifier for each scc -- whichever one comes first.
112 if external_sccs.contains(scc_idx) {
113 return true;
114 }
115 if internal_sccs.contains(scc_idx) {
116 return false;
117 }
118
119 let scc = &self.sccs[scc_idx];
120 let is_external = scc
121 .iter()
122 .flat_map(|ix| {
123 // Look at all incoming nodes from every SCC member.
124 graph.neighbors_directed(*ix, Incoming)
125 })
126 .all(|neighbor_ix| {
127 // * Accept any nodes are in the same SCC.
128 // * Any other results imply that this isn't an external scc.
129 match self.multi_map.get(&neighbor_ix) {
130 Some(neighbor_scc_idx) => neighbor_scc_idx == &scc_idx,
131 None => false,
132 }
133 });
134 if is_external {
135 external_sccs.insert(scc_idx);
136 } else {
137 internal_sccs.insert(scc_idx);
138 }
139 is_external
140 }
141 None => {
142 // Not part of a multi-node SCC. Treat the node as its own
143 // (single-element) SCC: it's external iff it has no
144 // incoming neighbors *other than itself*.
145 //
146 // A self-loop is an edge within the node's own SCC and must
147 // not disqualify it from being external, matching how the
148 // multi-node branch above accepts in-SCC neighbors.
149 !graph
150 .neighbors_directed(*ix, Incoming)
151 .any(|neighbor_ix| neighbor_ix != *ix)
152 }
153 })
154 }
155
156 /// Iterate over all nodes in the direction specified.
157 pub fn node_iter(&self, direction: Direction) -> NodeIter<'_, Ix> {
158 NodeIter {
159 node_ixs: self.sccs.data().iter(),
160 direction,
161 }
162 }
163}
164
165/// An iterator over the nodes of strongly connected components.
166#[derive(Clone, Debug)]
167pub(crate) struct NodeIter<'a, Ix> {
168 node_ixs: slice::Iter<'a, NodeIndex<Ix>>,
169 direction: Direction,
170}
171
172impl<Ix> NodeIter<'_, Ix> {
173 /// Returns the direction this iteration is happening in.
174 #[allow(dead_code)]
175 pub fn direction(&self) -> Direction {
176 self.direction
177 }
178}
179
180impl<Ix: IndexType> Iterator for NodeIter<'_, Ix> {
181 type Item = NodeIndex<Ix>;
182
183 fn next(&mut self) -> Option<NodeIndex<Ix>> {
184 // Note that outgoing implies iterating over the sccs in forward order, while incoming means
185 // sccs in reverse order.
186 match self.direction {
187 Direction::Outgoing => self.node_ixs.next().copied(),
188 Direction::Incoming => self.node_ixs.next_back().copied(),
189 }
190 }
191}
192
193#[cfg(test)]
194mod tests {
195 use super::*;
196 use petgraph::Graph;
197 use std::collections::HashSet;
198
199 /// Self-loops are internal to a node's own (single-element) SCC, so
200 /// they neither qualify a node for nor disqualify it from being a
201 /// forward root on their own.
202 #[test]
203 fn externals_with_self_loops_on_single_node_sccs() {
204 // a -> a (self-loop, no external incoming): `a` is external.
205 // a -> b (real incoming edge for `b`)
206 // b -> b (self-loop; the real incoming wins): `b` is not external.
207 let mut graph = Graph::<(), (), Directed, u32>::new();
208 let a = graph.add_node(());
209 let b = graph.add_node(());
210 graph.add_edge(a, a, ());
211 graph.add_edge(a, b, ());
212 graph.add_edge(b, b, ());
213
214 let sccs = Sccs::<u32>::new(&graph, |_| {});
215 let externals: HashSet<NodeIndex<u32>> = sccs.externals(&graph).collect();
216 assert_eq!(externals, HashSet::from([a]));
217 }
218
219 /// A self-loop on a node that belongs to a multi-node SCC must not
220 /// disqualify the SCC from being external.
221 #[test]
222 fn externals_with_self_loop_inside_multi_node_scc() {
223 // a -> b, b -> a (mutual edges form a 2-node SCC {a, b})
224 // a -> a (self-loop, still inside the SCC)
225 // a -> c
226 //
227 // * The SCC {a, b} has no incoming edge from outside, so both of
228 // its members are externals.
229 // * `c` is reachable from the SCC and is not external.
230 let mut graph = Graph::<(), (), Directed, u32>::new();
231 let a = graph.add_node(());
232 let b = graph.add_node(());
233 let c = graph.add_node(());
234 graph.add_edge(a, b, ());
235 graph.add_edge(b, a, ());
236 graph.add_edge(a, a, ());
237 graph.add_edge(a, c, ());
238
239 let sccs = Sccs::<u32>::new(&graph, |_| {});
240 let externals: HashSet<NodeIndex<u32>> = sccs.externals(&graph).collect();
241 assert_eq!(externals, HashSet::from([a, b]));
242 }
243}