modular_decomposition/md_tree/
functions.rs

1use crate::{MDTree, ModuleIndex, ModuleKind};
2
3impl<NodeId: Copy + PartialEq> MDTree<NodeId> {
4    /// Returns whether the original graph is a [cograph](https://en.wikipedia.org/wiki/Cograph).
5    pub fn is_cograph(&self) -> bool {
6        self.module_kinds().all(|node| *node != ModuleKind::Prime)
7    }
8}
9
10struct TwinsBase<'tree, NodeId: Copy + PartialEq, P> {
11    md_tree: &'tree MDTree<NodeId>,
12    stack: Vec<ModuleIndex>,
13    pred: P,
14}
15
16impl<'tree, NodeId: Copy + PartialEq, P: FnMut(&ModuleKind<NodeId>) -> bool> TwinsBase<'tree, NodeId, P> {
17    fn new(md_tree: &'tree MDTree<NodeId>, pred: P) -> Self {
18        let stack = match md_tree.module_kind(md_tree.root()) {
19            Some(ModuleKind::Node(_)) => vec![],
20            _ => vec![md_tree.root()],
21        };
22        Self { md_tree, stack, pred }
23    }
24}
25
26impl<'tree, NodeId: Copy + PartialEq, P: FnMut(&ModuleKind<NodeId>) -> bool> Iterator for TwinsBase<'tree, NodeId, P> {
27    type Item = Vec<NodeId>;
28
29    fn next(&mut self) -> Option<Self::Item> {
30        // Walk the tree with a dfs on the internal nodes.
31        // If a node has a matching type `$internal_node_type` then collect its leaf children
32        // and return them if there are at least two.
33        while let Some(node) = self.stack.pop() {
34            let kind = self.md_tree.module_kind(node).expect("node is valid");
35            if (self.pred)(kind) {
36                let mut leaf_children = vec![];
37                for child in self.md_tree.children(node) {
38                    if let Some(ModuleKind::Node(u)) = self.md_tree.module_kind(child) {
39                        leaf_children.push(*u);
40                    } else {
41                        self.stack.push(child);
42                    }
43                }
44                if leaf_children.len() >= 2 {
45                    return Some(leaf_children);
46                }
47            } else {
48                let children = self
49                    .md_tree
50                    .children(node)
51                    .filter(|child| !matches!(self.md_tree.module_kind(*child), Some(ModuleKind::Node(_))));
52                self.stack.extend(children);
53            }
54        }
55        None
56    }
57}
58
59impl<NodeId: Copy + PartialEq> MDTree<NodeId> {
60    /// Returns an iterator for the set of nodes of the original graph that are twins.
61    ///
62    /// Two nodes are twins when they have the same neighborhood excluding themselves, i.e. N(u) \ {v} = N(v) \ {u}.
63    ///
64    /// Twins are either true or false twins. See [MDTree::true_twins] and [MDTree::false_twins].
65    ///
66    /// ```rust
67    /// # use std::error::Error;
68    /// #
69    /// # fn main() -> Result<(), Box<dyn Error>> {
70    /// use petgraph::graph::{NodeIndex, UnGraph};
71    /// use modular_decomposition::modular_decomposition;
72    ///
73    /// // a K_2 + 2 K_1
74    /// let graph = UnGraph::<(), ()>::from_edges([(2, 3)]);
75    /// let md = modular_decomposition(&graph)?;
76    ///
77    /// let mut twins: Vec<_> = md.twins().collect();
78    /// twins.iter_mut().for_each(|nodes| nodes.sort());
79    /// twins.sort();
80    /// assert_eq!(twins, [[NodeIndex::new(0), NodeIndex::new(1)], [NodeIndex::new(2), NodeIndex::new(3)]]);
81    /// # Ok(())
82    /// # }
83    pub fn twins(&self) -> impl Iterator<Item = Vec<NodeId>> + '_ {
84        TwinsBase::new(self, |kind| matches!(kind, ModuleKind::Series | ModuleKind::Parallel))
85    }
86
87    /// Returns an iterator for the set of nodes of the original graph that are true twins.
88    ///
89    /// Two nodes are true twins when they have the same closed neighborhood, i.e. N(u) = N(v).
90    ///
91    /// ```rust
92    /// # use std::error::Error;
93    /// #
94    /// # fn main() -> Result<(), Box<dyn Error>> {
95    /// use petgraph::graph::{NodeIndex, UnGraph};
96    /// use modular_decomposition::modular_decomposition;
97    ///
98    /// // a K_2 + 2 K_1
99    /// let graph = UnGraph::<(), ()>::from_edges([(2, 3)]);
100    /// let md = modular_decomposition(&graph)?;
101    ///
102    /// let mut twins: Vec<_> = md.true_twins().collect();
103    /// twins.iter_mut().for_each(|nodes| nodes.sort());
104    /// twins.sort();
105    /// assert_eq!(twins, [[NodeIndex::new(2), NodeIndex::new(3)]]);
106    /// # Ok(())
107    /// # }
108    pub fn true_twins(&self) -> impl Iterator<Item = Vec<NodeId>> + '_ {
109        TwinsBase::new(self, |kind| kind == &ModuleKind::Series)
110    }
111
112    /// Returns an iterator for the set of nodes of the original graph that false twins.
113    ///
114    /// Two nodes are false twins when they have the same open neighborhood, i.e. N(u) u {u} = N(v) u {v}.
115    ///
116    /// ```rust
117    /// # use std::error::Error;
118    /// #
119    /// # fn main() -> Result<(), Box<dyn Error>> {
120    /// use petgraph::graph::{NodeIndex, UnGraph};
121    /// use modular_decomposition::modular_decomposition;
122    ///
123    /// // a K_2 + 2 K_1
124    /// let graph = UnGraph::<(), ()>::from_edges([(2, 3)]);
125    /// let md = modular_decomposition(&graph)?;
126    ///
127    /// let mut twins: Vec<_> = md.false_twins().collect();
128    /// twins.iter_mut().for_each(|nodes| nodes.sort());
129    /// twins.sort();
130    /// assert_eq!(twins, [[NodeIndex::new(0), NodeIndex::new(1)]]);
131    /// # Ok(())
132    /// # }
133    pub fn false_twins(&self) -> impl Iterator<Item = Vec<NodeId>> + '_ {
134        TwinsBase::new(self, |kind| kind == &ModuleKind::Parallel)
135    }
136}
137
138#[cfg(test)]
139mod test {
140    use petgraph::graph::{NodeIndex, UnGraph};
141
142    use crate::modular_decomposition;
143    use crate::tests;
144
145    fn to_usize(node_vecs: &[Vec<NodeIndex>]) -> Vec<Vec<usize>> {
146        let mut node_vecs: Vec<Vec<usize>> =
147            node_vecs.iter().map(|nodes| nodes.iter().map(|node| node.index()).collect()).collect();
148        node_vecs.iter_mut().for_each(|nodes| nodes.sort());
149        node_vecs.sort();
150        node_vecs
151    }
152
153    #[test]
154    fn cograph_k5() {
155        let graph = tests::complete_graph(5);
156        let md = modular_decomposition(&graph).unwrap();
157        assert!(md.is_cograph());
158    }
159
160    #[test]
161    fn cograph_e5() {
162        let graph = tests::empty_graph(5);
163        let md = modular_decomposition(&graph).unwrap();
164        assert!(md.is_cograph());
165    }
166
167    #[test]
168    fn cograph_p5() {
169        let graph = tests::path_graph(5);
170        let md = modular_decomposition(&graph).unwrap();
171        assert!(!md.is_cograph());
172    }
173
174    #[test]
175    fn twins_k1() {
176        let graph = tests::complete_graph(1);
177        let md = modular_decomposition(&graph).unwrap();
178        let twins: Vec<_> = md.twins().collect();
179        assert!(twins.is_empty());
180        let true_twins: Vec<_> = md.true_twins().collect();
181        assert!(true_twins.is_empty());
182        let false_twins: Vec<_> = md.false_twins().collect();
183        assert!(false_twins.is_empty());
184    }
185
186    #[test]
187    fn twins_k3() {
188        let graph = tests::complete_graph(3);
189        let md = modular_decomposition(&graph).unwrap();
190        let twins: Vec<_> = md.twins().collect();
191        assert_eq!(to_usize(&twins), [[0, 1, 2]]);
192        let true_twins: Vec<_> = md.true_twins().collect();
193        assert_eq!(to_usize(&true_twins), [[0, 1, 2]]);
194        let false_twins: Vec<_> = md.false_twins().collect();
195        assert_eq!(to_usize(&false_twins), Vec::<Vec<_>>::new());
196    }
197
198    #[test]
199    fn twins_e3() {
200        let graph = tests::empty_graph(3);
201        let md = modular_decomposition(&graph).unwrap();
202        let twins: Vec<_> = md.twins().collect();
203        assert_eq!(to_usize(&twins), [[0, 1, 2]]);
204        let true_twins: Vec<_> = md.true_twins().collect();
205        assert_eq!(to_usize(&true_twins), Vec::<Vec<_>>::new());
206        let false_twins: Vec<_> = md.false_twins().collect();
207        assert_eq!(to_usize(&false_twins), [[0, 1, 2]]);
208    }
209
210    #[test]
211    fn twins_k2_plus_2k1() {
212        let graph = UnGraph::<(), ()>::from_edges([(2, 3)]);
213        let md = modular_decomposition(&graph).unwrap();
214        let twins: Vec<_> = md.twins().collect();
215        assert_eq!(to_usize(&twins), [[0, 1], [2, 3]]);
216        let true_twins: Vec<_> = md.true_twins().collect();
217        assert_eq!(to_usize(&true_twins), [[2, 3]]);
218        let false_twins: Vec<_> = md.false_twins().collect();
219        assert_eq!(to_usize(&false_twins), [[0, 1]]);
220    }
221
222    #[test]
223    fn twins_k2_plus_2k1_complement() {
224        let graph = UnGraph::<(), ()>::from_edges([(0, 1), (0, 2), (0, 3), (1, 2), (1, 3)]);
225        let md = modular_decomposition(&graph).unwrap();
226        let twins: Vec<_> = md.twins().collect();
227        assert_eq!(to_usize(&twins), [[0, 1], [2, 3]]);
228        let true_twins: Vec<_> = md.true_twins().collect();
229        assert_eq!(to_usize(&true_twins), [[0, 1]]);
230        let false_twins: Vec<_> = md.false_twins().collect();
231        assert_eq!(to_usize(&false_twins), [[2, 3]]);
232    }
233
234    #[test]
235    fn twins_pace2023_exact_054() {
236        let graph = tests::pace2023_exact_054();
237        let md_tree = modular_decomposition(&graph).unwrap();
238
239        let mut twins: Vec<_> = md_tree.twins().collect();
240        twins.iter_mut().for_each(|nodes| nodes.sort());
241        twins.sort();
242        assert_eq!(
243            to_usize(&twins),
244            [
245                vec![24, 25],
246                vec![32, 35],
247                vec![44, 63, 64],
248                vec![45, 46],
249                vec![48, 49, 50],
250                vec![52, 70],
251                vec![53, 54],
252                vec![55, 56],
253                vec![57, 62],
254                vec![65, 67],
255                vec![68, 69],
256                vec![71, 72]
257            ]
258        );
259
260        let mut true_twins: Vec<_> = md_tree.true_twins().collect();
261        true_twins.iter_mut().for_each(|nodes| nodes.sort());
262        true_twins.sort();
263        assert_eq!(
264            to_usize(&true_twins),
265            [
266                vec![24, 25],
267                vec![45, 46],
268                vec![48, 49, 50],
269                vec![53, 54],
270                vec![55, 56],
271                vec![65, 67],
272                vec![68, 69],
273                vec![71, 72]
274            ]
275        );
276
277        let mut false_twins: Vec<_> = md_tree.false_twins().collect();
278        false_twins.iter_mut().for_each(|nodes| nodes.sort());
279        false_twins.sort();
280        assert_eq!(to_usize(&false_twins), [vec![32, 35], vec![44, 63, 64], vec![52, 70], vec![57, 62]]);
281    }
282}
modular_decomposition/md_tree/functions.rs

modular_decomposition/md_tree/
functions.rs
