modular_decomposition/
lib.rs

1//! This is a library to compute the [modular decomposition](https://en.wikipedia.org/wiki/Modular_decomposition) of a simple, undirected graph.
2//!
3//! A node set *M* is a *module* if every node has the same neighborhood outside
4//! *M*. The set of all nodes *V* and the sets with a single node *{u}* are
5//! trivial modules.
6//!
7//! # Examples
8//!
9//! The smallest prime graph is the path graph on 4 nodes.
10//! ```rust
11//! # use std::error::Error;
12//! #
13//! # fn main() -> Result<(), Box<dyn Error>> {
14//! use petgraph::graph::UnGraph;
15//! use modular_decomposition::{ModuleKind, modular_decomposition};
16//!
17//! // a path graph with 4 nodes
18//! let graph = UnGraph::<(), ()>::from_edges([(0, 1), (1, 2), (2, 3)]);
19//! let md = modular_decomposition(&graph)?;
20//!
21//! assert_eq!(md.module_kind(md.root()), Some(&ModuleKind::Prime));
22//! # Ok(())
23//! # }
24//! ```
25//!
26//! Determining whether a graph is a [cograph](https://en.wikipedia.org/wiki/Cograph).
27//! ```rust
28//! # use std::error::Error;
29//! #
30//! # fn main() -> Result<(), Box<dyn Error>> {
31//! use petgraph::graph::UnGraph;
32//! use modular_decomposition::{ModuleKind, modular_decomposition};
33//!
34//! // a complete graph with 3 nodes
35//! let graph = UnGraph::<(), ()>::from_edges([(0, 1), (0, 2), (1, 2)]);
36//! let md = modular_decomposition(&graph)?;
37//!
38//! // a graph is a cograph exactly if none of its modules is prime
39//! let is_cograph = md.module_kinds().all(|kind| *kind != ModuleKind::Prime);
40//! assert!(is_cograph);
41//! # Ok(())
42//! # }
43//! ```
44//!
45//! # Generics
46//!
47//! The algorithm is implemented for structs that implement the `petgraph`
48//! traits `NodeCompactIndexable`, `IntoNeighbors`, and `GraphProp<EdgeType =
49//! Undirected>`.
50//!
51//! # References
52//! + \[HPV99\]: Michel Habib, Christophe Paul, and Laurent Viennot. “Partition Refinement Techniques: An Interesting Algorithmic Tool Kit”. <https://doi.org/10.1142/S0129054199000125>.
53//! + \[CHM02\]: Christian Capelle, Michel Habib, and Fabien Montgolfier. “Graph
54//!   Decompositions and Factorizing Permutations”. <https://doi.org/10.46298/dmtcs.298>.
55
56#![forbid(unsafe_code)]
57#![doc(test(attr(deny(warnings, rust_2018_idioms), allow(dead_code))))]
58#![warn(missing_docs, missing_debug_implementations, rust_2018_idioms, unreachable_pub)]
59
60/// A modular decomposition algorithm.
61pub mod fracture;
62mod index;
63mod md_tree;
64
65mod deque;
66mod segmented_stack;
67#[cfg(test)]
68mod tests;
69
70pub use fracture::modular_decomposition;
71pub use md_tree::MDTree;
72pub use md_tree::ModuleIndex;
73pub use md_tree::ModuleKind;
74
75#[cfg(test)]
76mod test {
77    use super::*;
78    use crate::md_tree::{MDTree, ModuleKind};
79    use petgraph::graph::NodeIndex;
80    use petgraph::visit::NodeIndexable;
81
82    #[derive(Default, Debug)]
83    struct ModuleKindCounts {
84        prime: usize,
85        series: usize,
86        parallel: usize,
87        vertex: usize,
88    }
89
90    impl PartialEq<[usize; 4]> for ModuleKindCounts {
91        fn eq(&self, &[prime, series, parallel, vertex]: &[usize; 4]) -> bool {
92            self.prime == prime && self.series == series && self.parallel == parallel && self.vertex == vertex
93        }
94    }
95
96    fn count_module_kinds(md: &MDTree<NodeIndex>) -> ModuleKindCounts {
97        let mut counts = ModuleKindCounts::default();
98        for kind in md.module_kinds() {
99            match kind {
100                ModuleKind::Prime => counts.prime += 1,
101                ModuleKind::Series => counts.series += 1,
102                ModuleKind::Parallel => counts.parallel += 1,
103                ModuleKind::Node(_) => counts.vertex += 1,
104            }
105        }
106        counts
107    }
108
109    #[test]
110    fn empty_0() {
111        let graph = tests::empty_graph(0);
112        let md = modular_decomposition(&graph);
113        assert!(md.is_err())
114    }
115
116    #[test]
117    fn empty_1() {
118        let graph = tests::empty_graph(1);
119        let md = modular_decomposition(&graph).unwrap();
120        assert_eq!(md.strong_module_count(), 1);
121        assert_eq!(count_module_kinds(&md), [0, 0, 0, 1]);
122        assert_eq!(md.module_kind(md.root()), Some(&ModuleKind::Node(graph.from_index(0))));
123    }
124
125    #[test]
126    fn empty_2() {
127        let graph = tests::empty_graph(2);
128        let md = modular_decomposition(&graph).unwrap();
129        assert_eq!(md.strong_module_count(), 3);
130        assert_eq!(count_module_kinds(&md), [0, 0, 1, 2]);
131        assert_eq!(md.module_kind(md.root()), Some(&ModuleKind::Parallel));
132        assert_eq!(md.children(md.root()).count(), 2);
133    }
134
135    #[test]
136    fn complete_2() {
137        let graph = tests::complete_graph(2);
138        let md = modular_decomposition(&graph).unwrap();
139        assert_eq!(md.strong_module_count(), 3);
140        assert_eq!(count_module_kinds(&md), [0, 1, 0, 2]);
141        assert_eq!(md.module_kind(md.root()), Some(&ModuleKind::Series));
142        assert_eq!(md.children(md.root()).count(), 2);
143    }
144
145    #[test]
146    fn complete_4() {
147        let graph = tests::complete_graph(4);
148        let md = modular_decomposition(&graph).unwrap();
149        assert_eq!(count_module_kinds(&md), [0, 1, 0, 4]);
150        assert_eq!(md.module_kind(md.root()), Some(&ModuleKind::Series));
151        assert_eq!(md.children(md.root()).count(), 4);
152    }
153
154    #[test]
155    fn complete_32() {
156        let graph = tests::complete_graph(32);
157        let md = modular_decomposition(&graph).unwrap();
158        assert_eq!(count_module_kinds(&md), [0, 1, 0, 32]);
159        assert_eq!(md.module_kind(md.root()), Some(&ModuleKind::Series));
160        assert_eq!(md.children(md.root()).count(), 32);
161    }
162
163    #[test]
164    fn path_4() {
165        let graph = tests::path_graph(4);
166        let md = modular_decomposition(&graph).unwrap();
167        assert_eq!(md.strong_module_count(), 5);
168        assert_eq!(count_module_kinds(&md), [1, 0, 0, 4]);
169        assert_eq!(md.module_kind(md.root()), Some(&ModuleKind::Prime));
170        assert_eq!(md.children(md.root()).count(), 4);
171    }
172
173    #[test]
174    fn path_32() {
175        let graph = tests::path_graph(32);
176        let md = modular_decomposition(&graph).unwrap();
177        assert_eq!(count_module_kinds(&md), [1, 0, 0, 32]);
178        assert_eq!(md.module_kind(md.root()), Some(&ModuleKind::Prime));
179        assert_eq!(md.children(md.root()).count(), 32);
180    }
181
182    #[test]
183    fn pace2023_exact_024() {
184        let graph = tests::pace2023_exact_024();
185        let md = modular_decomposition(&graph).unwrap();
186        assert_eq!(count_module_kinds(&md), [1, 2, 2, 40]);
187        assert_eq!(md.module_kind(md.root()), Some(&ModuleKind::Parallel));
188        assert_eq!(md.children(md.root()).count(), 3);
189    }
190
191    #[test]
192    fn pace2023_exact_054() {
193        let graph = tests::pace2023_exact_054();
194        let md = modular_decomposition(&graph).unwrap();
195        assert_eq!(count_module_kinds(&md), [3, 9, 5, 73]);
196        assert_eq!(md.module_kind(md.root()), Some(&ModuleKind::Parallel));
197        assert_eq!(md.children(md.root()).count(), 11);
198    }
199}
modular_decomposition/lib.rs

modular_decomposition/
lib.rs
