mapgraph/algo/
scc.rs

1//! Contains an implementation of the Tarjan's SCC algorithm.
2//!
3//! This algorithm expects the graph to be connected. In case the graph is disjoint, only nodes belonging to the same
4//! component as the start node will be marked.
5//!
6//! # Marking SCCs
7//!
8//! Strongly-Connected Components are represented by user-provided types. The implementation interacts with the types
9//! using the [`Scc`] and [`WithScc`] traits.
10//!
11//! The [`Scc`] trait should be implemented by the type representing an SCC. The type is expected to be easily clonable
12//! and the only required method is `with_entry` that constructs the type from an index of an arbitrary node belonging
13//! to the SCC. See docs for the [`Scc`] trait for more information.
14//!
15//! The [`WithScc`] trait is used to actually mark graph nodes with an SCC. It should be implemented on the graph's node
16//! weight type.
17//!
18//! This design allows to only reserve place for information about SCCs in graphs that actually use this algorithm.
19//!
20//! # Secondary maps
21//!
22//! The algorithm expects a secondary map that maps node indices to tuples containing two `u32`
23//! values to be provided as its last argument. This is only useful when you have strict performance
24//! requirements. When in doubt you should use a [`HashMap`] or a [`BTreeMap`]. In some cases,
25//! however, it might affect performance of the  algorithm, especially for large graphs. If this is
26//! your case, continue reading.
27//!
28//! Choosing a map is a concern mostly for graphs based on [`SlotMap`]-like node maps which provide
29//! secondary maps that can be accessed faster than [`HashMap`]s. These maps are backed by vectors
30//! so the usage of memory will be inefficient when you only visit a small number of node slots:
31//!
32//! 1. When the node slots are densely located but the component the start node belongs to happens
33//!    to be a small part of the graph;
34//! 2. When the node slots are located sparsely.
35//!
36//! Otherwise using these secondary maps is OK and will give you a performance boost when compared
37//! to other kinds of maps.
38//!
39//! [`HashMap`]: std::collections::HashMap
40//! [`BTreeMap`]: std::collections::BTreeMap
41//! [`SlotMap`]: slotmap::SlotMap
42
43use crate::{
44    graph::{iter::Walker, Edge, Node},
45    map::{ExtKeyMap, IntKeyMap, Map},
46    FrozenGraph,
47};
48use alloc::vec::Vec;
49use core::{cmp, fmt::Debug, marker::PhantomData};
50
51/// A trait for a type that represents a strongly-connected component of a graph.
52///
53/// # Requirements
54///
55/// It is expected that two instances of a type implementing this trait that are produced by a call
56/// to the [`Scc::with_entry`] method and exist at the same time are never equal. An instance
57/// produced by cloning another instance should always be equal to the original instance. This may
58/// be easily achieved by wrapping an `Rc` or an `Arc` with a newtype and implementing `PartialEq`
59/// using their `ptr_eq` methods.
60///
61/// Violating these requirements won't cause UB or even affect the implementation of the Tarjan's
62/// SCC algorithm, but will probably break your own code.
63pub trait Scc<I>: Clone + Eq {
64    /// Constructs the type representing an SCC with an index of a node that belongs to this SCC.
65    ///
66    /// Which exact node is specified isn't important since any other node in the SCC can be found
67    /// with a DFS pass starting from any other node.
68    fn with_entry(entry: I) -> Self;
69}
70
71/// A trait for a node weight that stores information about the SCC it belongs to.
72pub trait WithScc<I> {
73    /// The type that represents a strongly-connected component.
74    type Ty: Scc<I>;
75
76    /// Returns a reference to the SCC the node belongs to.
77    fn scc(&self) -> Option<&Self::Ty>;
78
79    /// Sets the SCC of the weight.
80    fn set_scc(&mut self, scc: Self::Ty);
81}
82
83struct State<NI, E, EF>
84where
85    EF: for<'a> FnMut(&'a E) -> bool,
86{
87    stack: Vec<NI>,
88    index: u32,
89    edge_filter: EF,
90    _marker: PhantomData<E>,
91}
92
93fn recurse<N, E, NI, EI, NM, EM, SM, EF>(
94    graph: &mut FrozenGraph<N, E, NI, EI, NM, EM>,
95    block: NI,
96    indices: &mut SM,
97    state: &mut State<NI, E, EF>,
98) -> (u32, u32)
99where
100    N: WithScc<NI>,
101    NI: Copy + Eq + Debug + 'static,
102    EI: Copy + Eq + Debug + 'static,
103    NM: Map<Node<N, EI>, Key = NI>,
104    EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
105    SM: ExtKeyMap<(u32, u32), Key = NI>,
106    EF: FnMut(&E) -> bool,
107{
108    let cur_index = state.index;
109    let mut low_link = cur_index;
110    state.index = cur_index + 1;
111
112    // Indices shouldn't be set when this function is called.
113    indices
114        .try_insert(block, (cur_index, low_link))
115        .expect("index for block shouldn't be set");
116    state.stack.push(block);
117
118    let mut walker = graph.walk_outputs(block);
119    while let Some((_, edge)) = walker.walk_next(graph) {
120        if !(state.edge_filter)(edge.weight()) {
121            continue;
122        }
123
124        let succ = edge.to();
125        match indices.get(succ) {
126            None => {
127                let (_, succ_low_link) = recurse(graph, succ, indices, state);
128                low_link = cmp::min(low_link, succ_low_link);
129
130                if let Some((_, v)) = indices.get_mut(block) {
131                    *v = low_link;
132                }
133            }
134            Some(&(succ_index, _)) if state.stack.contains(&succ) => {
135                low_link = cmp::min(low_link, succ_index);
136
137                if let Some((_, v)) = indices.get_mut(block) {
138                    *v = low_link;
139                }
140            }
141            _ => (),
142        }
143    }
144
145    if low_link == cur_index {
146        let mut cur_block_opt = state.stack.pop();
147
148        // Entry isn't really required to even be a point where the loop is entered. This is any
149        // valid block belonging to a loop so use the one we already have
150        if let Some(entry) = cur_block_opt {
151            // Do not create a loop for an scc subgraph consisting of one node that isn't connected
152            // to itself.
153            if entry != block
154                || graph
155                    .successors(entry)
156                    .any(|(succ_idx, _)| succ_idx == entry)
157            {
158                let scc = N::Ty::with_entry(entry);
159                while let Some(cur_block) = cur_block_opt {
160                    graph
161                        .node_weight_mut(cur_block)
162                        .expect("invalid node index in stack")
163                        .set_scc(scc.clone());
164
165                    if cur_block == block {
166                        break;
167                    }
168
169                    cur_block_opt = state.stack.pop();
170                }
171            }
172        }
173    }
174
175    (cur_index, low_link)
176}
177
178/// Runs Tarjan's SCC detection algorithm on a graph and marks weights with SCCs they belong to.
179pub fn mark_sccs<N, E, NI, EI, NM, EM, SM>(
180    graph: &mut FrozenGraph<N, E, NI, EI, NM, EM>,
181    start_node_index: NI,
182    secondary_map: &mut SM,
183) where
184    N: WithScc<NI>,
185    NI: Copy + Eq + Debug + 'static,
186    EI: Copy + Eq + Debug + 'static,
187    NM: Map<Node<N, EI>, Key = NI>,
188    EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
189    SM: ExtKeyMap<(u32, u32), Key = NI>,
190{
191    let mut state = State {
192        stack: Vec::new(),
193        index: 0,
194        edge_filter: |_| true,
195        _marker: PhantomData,
196    };
197
198    secondary_map.clear();
199
200    recurse(graph, start_node_index, secondary_map, &mut state);
201}
202
203/// Runs Tarjan's SCC detection algorithm on a graph while ignoring certain edges and marks weights with SCCs they
204/// belong to.
205pub fn mark_sccs_with_filter<N, E, NI, EI, NM, EM, SM, EF>(
206    graph: &mut FrozenGraph<N, E, NI, EI, NM, EM>,
207    start_node_index: NI,
208    secondary_map: &mut SM,
209    edge_filter: EF,
210) where
211    N: WithScc<NI>,
212    NI: Copy + Eq + Debug + 'static,
213    EI: Copy + Eq + Debug + 'static,
214    NM: Map<Node<N, EI>, Key = NI>,
215    EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
216    SM: ExtKeyMap<(u32, u32), Key = NI>,
217    EF: FnMut(&E) -> bool,
218{
219    let mut state = State {
220        stack: Vec::new(),
221        index: 0,
222        edge_filter,
223        _marker: PhantomData,
224    };
225
226    secondary_map.clear();
227
228    recurse(graph, start_node_index, secondary_map, &mut state);
229}
230
231#[cfg(all(test, feature = "slotmap"))]
232mod tests {
233    use super::*;
234    use crate::{
235        aliases::{SecondarySlotMap, SlotMapGraph},
236        map::slotmap::NodeIndex,
237    };
238    use alloc::rc::Rc;
239
240    #[derive(Clone, Eq, Debug)]
241    struct TestScc(Rc<NodeIndex>);
242
243    impl PartialEq for TestScc {
244        fn eq(&self, other: &Self) -> bool {
245            Rc::ptr_eq(&self.0, &other.0)
246        }
247    }
248
249    impl Scc<NodeIndex> for TestScc {
250        fn with_entry(entry: NodeIndex) -> Self {
251            Self(Rc::new(entry))
252        }
253    }
254
255    #[derive(Default, Debug)]
256    struct TestNodeWeight(Option<TestScc>);
257
258    impl WithScc<NodeIndex> for TestNodeWeight {
259        type Ty = TestScc;
260
261        fn scc(&self) -> Option<&Self::Ty> {
262            self.0.as_ref()
263        }
264
265        fn set_scc(&mut self, scc: Self::Ty) {
266            self.0 = Some(scc);
267        }
268    }
269
270    #[test]
271    fn test_simple_loop() {
272        let mut graph = SlotMapGraph::<TestNodeWeight, ()>::default();
273
274        let entry_node = graph.add_default_node();
275        let node1 = graph.add_default_node();
276        let node2 = graph.add_default_node();
277        let exit_node = graph.add_default_node();
278
279        graph.add_edge((), entry_node, node1).unwrap();
280        graph.add_edge((), node1, node2).unwrap();
281        graph.add_edge((), node2, exit_node).unwrap();
282        graph.add_edge((), node2, entry_node).unwrap();
283
284        let mut secondary_map = SecondarySlotMap::default();
285        mark_sccs(&mut graph, entry_node, &mut secondary_map);
286
287        let scc = graph.node_weight(entry_node).unwrap().scc().unwrap();
288        assert_eq!(scc, graph.node_weight(node1).unwrap().scc().unwrap());
289        assert_eq!(scc, graph.node_weight(node2).unwrap().scc().unwrap());
290        assert!(graph.node_weight(exit_node).unwrap().scc().is_none());
291    }
292
293    #[test]
294    fn test_two_loops() {
295        // This test creates two identical two-block loops and checks if the loop detector is able
296        // to detect these correctly. The graph looks roughly as follows:
297        //
298        //            < entry >
299        //      |---------|---------|
300        //     \|/                 \|/
301        //   < L1 > <-         -> < R1 >
302        //      |    |         |    |
303        //   < L2 > -|         |- < R2 >
304        //      |                   |
305        //      |----> < exit > <---|
306
307        let mut graph = SlotMapGraph::<TestNodeWeight, ()>::default();
308        let entry_node = graph.add_default_node();
309        let left_node1 = graph.add_default_node();
310        let left_node2 = graph.add_default_node();
311        let right_node1 = graph.add_default_node();
312        let right_node2 = graph.add_default_node();
313        let exit_node = graph.add_default_node();
314
315        graph.add_edge((), entry_node, left_node1).unwrap();
316        graph.add_edge((), left_node1, left_node2).unwrap();
317        graph.add_edge((), left_node2, left_node1).unwrap();
318        graph.add_edge((), left_node2, exit_node).unwrap();
319
320        graph.add_edge((), entry_node, right_node1).unwrap();
321        graph.add_edge((), right_node1, right_node2).unwrap();
322        graph.add_edge((), right_node2, right_node1).unwrap();
323        graph.add_edge((), right_node2, exit_node).unwrap();
324
325        let mut secondary_map = SecondarySlotMap::default();
326        mark_sccs(&mut graph, entry_node, &mut secondary_map);
327
328        let left_scc = graph.node_weight(left_node1).unwrap().scc().unwrap();
329        let right_scc = graph.node_weight(right_node1).unwrap().scc().unwrap();
330
331        assert!(graph.node_weight(exit_node).unwrap().scc().is_none());
332        assert_eq!(
333            left_scc,
334            graph.node_weight(left_node2).unwrap().scc().unwrap()
335        );
336        assert_eq!(
337            right_scc,
338            graph.node_weight(right_node2).unwrap().scc().unwrap()
339        );
340        assert_ne!(left_scc, right_scc);
341        assert!(graph.node_weight(exit_node).unwrap().scc().is_none());
342    }
343
344    /// Constructs a simple irreducible graph and tests whether loop detector can handle this.
345    #[test]
346    fn test_irreducible() {
347        let mut graph = SlotMapGraph::<TestNodeWeight, ()>::default();
348        let entry_node = graph.add_default_node();
349        let cond_node = graph.add_default_node();
350        let node1 = graph.add_default_node();
351        let node2 = graph.add_default_node();
352        let node3 = graph.add_default_node();
353
354        graph.add_edge((), entry_node, cond_node).unwrap();
355        graph.add_edge((), cond_node, node1).unwrap();
356        graph.add_edge((), cond_node, node2).unwrap();
357        graph.add_edge((), node1, node2).unwrap();
358        graph.add_edge((), node2, node3).unwrap();
359        graph.add_edge((), node3, node1).unwrap();
360
361        let mut secondary_map = SecondarySlotMap::default();
362        mark_sccs(&mut graph, entry_node, &mut secondary_map);
363
364        let scc = graph.node_weight(node1).unwrap().scc().unwrap();
365
366        assert!(graph.node_weight(entry_node).unwrap().scc().is_none());
367        assert!(graph.node_weight(cond_node).unwrap().scc().is_none());
368        assert_eq!(scc, graph.node_weight(node2).unwrap().scc().unwrap());
369        assert_eq!(scc, graph.node_weight(node3).unwrap().scc().unwrap());
370    }
371}
mapgraph/algo/scc.rs

mapgraph/algo/
scc.rs
