graaf/algo/
tarjan.rs

1//! Tarjan's algorithm.
2//!
3//! Tarjan's algorithm finds a digraph's strongly connected components.
4//!
5//! # Examples
6//!
7//! There are three strongly connected components in this digraph:
8//!
9//! ![A digraph and its strongly connected components](https://raw.githubusercontent.com/bsdrks/graaf-images/main/out/tarjan_1-0.87.4.svg?)
10//!
11//! ```
12//! use {
13//!     graaf::{
14//!         AddArc,
15//!         AdjacencyList,
16//!         Empty,
17//!         Tarjan,
18//!     },
19//!     std::collections::BTreeSet,
20//! };
21//!
22//! let mut digraph = AdjacencyList::empty(8);
23//!
24//! digraph.add_arc(0, 1);
25//! digraph.add_arc(1, 2);
26//! digraph.add_arc(1, 4);
27//! digraph.add_arc(2, 3);
28//! digraph.add_arc(2, 6);
29//! digraph.add_arc(3, 2);
30//! digraph.add_arc(3, 7);
31//! digraph.add_arc(4, 0);
32//! digraph.add_arc(4, 5);
33//! digraph.add_arc(5, 6);
34//! digraph.add_arc(6, 5);
35//! digraph.add_arc(7, 3);
36//! digraph.add_arc(7, 6);
37//!
38//! assert!(Tarjan::new(&digraph).components().iter().eq(&[
39//!     BTreeSet::from([5, 6]),
40//!     BTreeSet::from([7, 3, 2]),
41//!     BTreeSet::from([4, 1, 0])
42//! ]));
43//! ```
44
45use {
46    crate::{
47        OutNeighbors,
48        Vertices,
49    },
50    std::collections::{
51        BTreeMap,
52        BTreeSet,
53    },
54};
55
56/// Tarjan's algorithm.
57///
58/// Tarjan's algorithm finds a digraph's strongly connected components.
59///
60/// # Examples
61///
62/// There are three strongly connected components in this digraph:
63///
64/// ![A digraph and its strongly connected components](https://raw.githubusercontent.com/bsdrks/graaf-images/main/out/tarjan_1-0.87.4.svg?)
65///
66/// ```
67/// use {
68///     graaf::{
69///         AddArc,
70///         AdjacencyList,
71///         Empty,
72///         Tarjan,
73///     },
74///     std::collections::BTreeSet,
75/// };
76///
77/// let mut digraph = AdjacencyList::empty(8);
78///
79/// digraph.add_arc(0, 1);
80/// digraph.add_arc(1, 2);
81/// digraph.add_arc(1, 4);
82/// digraph.add_arc(2, 3);
83/// digraph.add_arc(2, 6);
84/// digraph.add_arc(3, 2);
85/// digraph.add_arc(3, 7);
86/// digraph.add_arc(4, 0);
87/// digraph.add_arc(4, 5);
88/// digraph.add_arc(5, 6);
89/// digraph.add_arc(6, 5);
90/// digraph.add_arc(7, 3);
91/// digraph.add_arc(7, 6);
92///
93/// assert!(Tarjan::new(&digraph).components().iter().eq(&[
94///     BTreeSet::from([5, 6]),
95///     BTreeSet::from([7, 3, 2]),
96///     BTreeSet::from([4, 1, 0]),
97/// ]));
98/// ```
99#[derive(Clone, Debug, Eq, PartialEq)]
100pub struct Tarjan<'a, D> {
101    digraph: &'a D,
102    i: usize,
103    stack: Vec<usize>,
104    on_stack: BTreeSet<usize>,
105    index: BTreeMap<usize, usize>,
106    low_link: BTreeMap<usize, usize>,
107    components: Vec<BTreeSet<usize>>,
108}
109
110impl<'a, D> Tarjan<'a, D> {
111    /// Construct a new instance of Tarjan's algorithm.
112    ///
113    /// # Arguments
114    ///
115    /// * `digraph`: The digraph.
116    #[must_use]
117    pub const fn new(digraph: &'a D) -> Self
118    where
119        D: OutNeighbors + Vertices,
120    {
121        Self {
122            digraph,
123            i: 0,
124            stack: Vec::new(),
125            on_stack: BTreeSet::new(),
126            index: BTreeMap::new(),
127            low_link: BTreeMap::new(),
128            components: Vec::new(),
129        }
130    }
131
132    /// Find a digraph's strongly connected components.
133    ///
134    /// # Examples
135    ///
136    /// There are three strongly connected components in this digraph:
137    ///
138    /// ![A digraph and its strongly connected components](https://raw.githubusercontent.com/bsdrks/graaf-images/main/out/tarjan_1-0.87.4.svg?)
139    ///
140    /// ```
141    /// use {
142    ///     graaf::{
143    ///         AddArc,
144    ///         AdjacencyList,
145    ///         Empty,
146    ///         Tarjan,
147    ///     },
148    ///     std::collections::BTreeSet,
149    /// };
150    ///
151    /// let mut digraph = AdjacencyList::empty(8);
152    ///
153    /// digraph.add_arc(0, 1);
154    /// digraph.add_arc(1, 2);
155    /// digraph.add_arc(1, 4);
156    /// digraph.add_arc(2, 3);
157    /// digraph.add_arc(2, 6);
158    /// digraph.add_arc(3, 2);
159    /// digraph.add_arc(3, 7);
160    /// digraph.add_arc(4, 0);
161    /// digraph.add_arc(4, 5);
162    /// digraph.add_arc(5, 6);
163    /// digraph.add_arc(6, 5);
164    /// digraph.add_arc(7, 3);
165    /// digraph.add_arc(7, 6);
166    ///
167    /// assert!(Tarjan::new(&digraph).components().iter().eq(&[
168    ///     BTreeSet::from([5, 6]),
169    ///     BTreeSet::from([7, 3, 2]),
170    ///     BTreeSet::from([4, 1, 0])
171    /// ]));
172    /// ```
173    #[must_use]
174    pub fn components(&mut self) -> &Vec<BTreeSet<usize>>
175    where
176        D: OutNeighbors + Vertices,
177    {
178        for u in self.digraph.vertices() {
179            if !self.index.contains_key(&u) {
180                self.connect(u);
181            }
182        }
183
184        &self.components
185    }
186
187    fn connect(&mut self, u: usize)
188    where
189        D: OutNeighbors,
190    {
191        let _ = self.index.insert(u, self.i);
192        let _ = self.low_link.insert(u, self.i);
193        let _ = self.on_stack.insert(u);
194
195        self.stack.push(u);
196
197        self.i += 1;
198
199        for v in self.digraph.out_neighbors(u) {
200            if let Some(&w) = self.index.get(&v) {
201                if self.on_stack.contains(&v) {
202                    let _ = self.low_link.insert(u, self.low_link[&u].min(w));
203                }
204            } else {
205                self.connect(v);
206
207                let _ = self
208                    .low_link
209                    .insert(u, self.low_link[&u].min(self.low_link[&v]));
210            }
211        }
212
213        if self.index.get(&u) == self.low_link.get(&u) {
214            let mut component = BTreeSet::new();
215
216            while let Some(v) = self.stack.pop() {
217                let _ = self.on_stack.remove(&v);
218                let _ = component.insert(v);
219
220                if u == v {
221                    break;
222                }
223            }
224
225            self.components.push(component);
226        }
227    }
228}
229
230#[cfg(test)]
231mod tests {
232    use {
233        super::*,
234        crate::{
235            AdjacencyList,
236            Empty,
237            repr::adjacency_list::fixture::{
238                bang_jensen_34,
239                bang_jensen_94,
240                bang_jensen_196,
241                kattis_builddeps,
242                kattis_cantinaofbabel_1,
243                kattis_cantinaofbabel_2,
244                kattis_escapewallmaria_1,
245                kattis_escapewallmaria_2,
246                kattis_escapewallmaria_3,
247            },
248        },
249    };
250
251    #[test]
252    fn components_bang_jensen_196() {
253        assert!(Tarjan::new(&bang_jensen_196()).components().iter().eq(&[
254            BTreeSet::from([2, 3, 4]),
255            BTreeSet::from([5, 6, 7]),
256            BTreeSet::from([0, 1]),
257        ]));
258    }
259
260    #[test]
261    fn components_bang_jensen_34() {
262        assert!(Tarjan::new(&bang_jensen_34()).components().iter().eq(&[
263            BTreeSet::from([4]),
264            BTreeSet::from([0]),
265            BTreeSet::from([1]),
266            BTreeSet::from([3]),
267            BTreeSet::from([5]),
268            BTreeSet::from([2]),
269        ]));
270    }
271
272    #[test]
273    fn components_bang_jensen_94() {
274        assert!(Tarjan::new(&bang_jensen_94()).components().iter().eq(&[
275            BTreeSet::from([5]),
276            BTreeSet::from([3]),
277            BTreeSet::from([1]),
278            BTreeSet::from([6]),
279            BTreeSet::from([4]),
280            BTreeSet::from([2]),
281            BTreeSet::from([0]),
282        ]));
283    }
284
285    #[test]
286    fn components_kattis_builddeps() {
287        assert!(Tarjan::new(&kattis_builddeps()).components().iter().eq(&[
288            BTreeSet::from([1]),
289            BTreeSet::from([3]),
290            BTreeSet::from([4]),
291            BTreeSet::from([0]),
292            BTreeSet::from([5]),
293            BTreeSet::from([2]),
294        ]));
295    }
296
297    #[test]
298    fn components_kattis_cantinaofbabel_1() {
299        assert!(
300            Tarjan::new(&kattis_cantinaofbabel_1())
301                .components()
302                .iter()
303                .eq(&[
304                    BTreeSet::from([5, 6, 10]),
305                    BTreeSet::from([0, 1, 2, 3, 4, 7, 9, 11]),
306                    BTreeSet::from([8]),
307                ])
308        );
309    }
310
311    #[test]
312    fn components_kattis_cantinaofbabel_2() {
313        assert!(
314            Tarjan::new(&kattis_cantinaofbabel_2())
315                .components()
316                .iter()
317                .eq(&[
318                    BTreeSet::from([3, 4]),
319                    BTreeSet::from([5, 6]),
320                    BTreeSet::from([0, 1, 2, 7]),
321                    BTreeSet::from([8, 9, 10, 11]),
322                ])
323        );
324    }
325
326    #[test]
327    fn components_kattis_escapewallmaria_1() {
328        assert!(
329            Tarjan::new(&kattis_escapewallmaria_1())
330                .components()
331                .iter()
332                .eq(&[
333                    BTreeSet::from([0]),
334                    BTreeSet::from([1]),
335                    BTreeSet::from([2]),
336                    BTreeSet::from([3]),
337                    BTreeSet::from([4]),
338                    BTreeSet::from([12]),
339                    BTreeSet::from([5, 6, 9, 13]),
340                    BTreeSet::from([7]),
341                    BTreeSet::from([8]),
342                    BTreeSet::from([10]),
343                    BTreeSet::from([11]),
344                    BTreeSet::from([14]),
345                    BTreeSet::from([15]),
346                ])
347        );
348    }
349
350    #[test]
351    fn components_kattis_escapewallmaria_2() {
352        assert!(
353            Tarjan::new(&kattis_escapewallmaria_2())
354                .components()
355                .iter()
356                .eq(&[
357                    BTreeSet::from([0]),
358                    BTreeSet::from([1]),
359                    BTreeSet::from([2]),
360                    BTreeSet::from([3]),
361                    BTreeSet::from([4]),
362                    BTreeSet::from([5, 6, 9]),
363                    BTreeSet::from([7]),
364                    BTreeSet::from([8]),
365                    BTreeSet::from([10]),
366                    BTreeSet::from([11]),
367                    BTreeSet::from([12, 13]),
368                    BTreeSet::from([14]),
369                    BTreeSet::from([15]),
370                ])
371        );
372    }
373
374    #[test]
375    fn components_kattis_escapewallmaria_3() {
376        assert!(
377            Tarjan::new(&kattis_escapewallmaria_3())
378                .components()
379                .iter()
380                .eq(&[
381                    BTreeSet::from([0]),
382                    BTreeSet::from([1, 2, 5, 6, 9, 12, 13]),
383                    BTreeSet::from([3]),
384                    BTreeSet::from([4]),
385                    BTreeSet::from([7]),
386                    BTreeSet::from([8]),
387                    BTreeSet::from([10]),
388                    BTreeSet::from([11]),
389                    BTreeSet::from([14]),
390                    BTreeSet::from([15]),
391                ])
392        );
393    }
394
395    #[test]
396    fn components_trivial() {
397        assert!(
398            Tarjan::new(&AdjacencyList::trivial())
399                .components()
400                .iter()
401                .eq(&[BTreeSet::from([0])])
402        );
403    }
404}
graaf/algo/tarjan.rs

graaf/algo/
tarjan.rs
