causal_hub/graphs/algorithms/components/
connected_components.rs

1use std::collections::BTreeSet;
2
3use crate::{
4    graphs::{directions, UndirectedGraph},
5    prelude::BFS,
6    V,
7};
8
9/// Connected components structure.
10pub struct ConnectedComponents<'a, G>
11where
12    G: UndirectedGraph<Direction = directions::Undirected>,
13{
14    g: &'a G,
15    queue: BTreeSet<usize>,
16}
17
18impl<'a, G> ConnectedComponents<'a, G>
19where
20    G: UndirectedGraph<Direction = directions::Undirected>,
21{
22    /// Build a CC iterator.
23    ///
24    /// # Examples
25    ///
26    /// ```
27    /// use std::collections::BTreeSet;
28    ///
29    /// use causal_hub::prelude::*;
30    ///
31    /// // Build a new undirected graph.
32    /// let g = Graph::new(
33    ///     ["A", "B", "C", "D", "E", "F"],
34    ///     [
35    ///         ("A", "B"),
36    ///         ("B", "C"),
37    ///         ("D", "E"),
38    ///     ]
39    /// );
40    ///
41    /// // Build a connected component iterator.
42    /// let mut cc = CC::from(&g);
43    ///
44    /// // Assert connected components.
45    /// assert!(
46    ///     cc.eq([
47    ///         BTreeSet::from([0, 1, 2]),
48    ///         BTreeSet::from([3, 4]),
49    ///         BTreeSet::from([5]),
50    ///     ])
51    /// );
52    /// ```
53    ///
54    pub fn new(g: &'a G) -> Self {
55        // Initialize to-be-visited queue.
56        let queue = V!(g).collect();
57
58        Self { g, queue }
59    }
60}
61
62impl<'a, G> Iterator for ConnectedComponents<'a, G>
63where
64    G: UndirectedGraph<Direction = directions::Undirected>,
65{
66    type Item = BTreeSet<usize>;
67
68    fn next(&mut self) -> Option<Self::Item> {
69        // Check if there is still a vertex to be visited.
70        self.queue.pop_first().map(|x| {
71            // Perform BFS Tree visit starting from the vertex.
72            let component = BFS::from((self.g, x)).collect();
73            // Remove visited vertices from the to-be-visited set.
74            self.queue = &self.queue - &component;
75
76            component
77        })
78    }
79}
80
81impl<'a, G> From<&'a G> for ConnectedComponents<'a, G>
82where
83    G: UndirectedGraph<Direction = directions::Undirected>,
84{
85    fn from(g: &'a G) -> Self {
86        Self::new(g)
87    }
88}
89
90/// Alias for connected components.
91pub type CC<'a, G> = ConnectedComponents<'a, G>;
causal_hub/graphs/algorithms/components/connected_components.rs

causal_hub/graphs/algorithms/components/
connected_components.rs
