modular_decomposition/md_tree/
mod.rs

1mod functions;
2
3use std::fmt::{Debug, Display, Formatter};
4use std::iter::from_fn;
5
6use petgraph::graph::DiGraph;
7use petgraph::{Incoming, Outgoing};
8
9use crate::index::make_index;
10
11make_index!(pub(crate) NodeIndex);
12
13/// Module kinds of nodes in a [MDTree].
14///
15/// Each module corresponds to a set of nodes in the original graph, the leaves of the subtree
16/// rooted at that node.
17///
18/// The module kinds are determined by the quotient graph of a module that is obtained by taking a
19/// single node from each child module.
20#[derive(Copy, Clone, Hash, Eq, PartialEq, Ord, PartialOrd)]
21pub enum ModuleKind<NodeId: Copy + PartialEq> {
22    /// A prime module. Its quotient graph has only trivial modules.
23    Prime,
24    /// A series module. Its quotient graph is a complete graph.
25    Series,
26    /// A parallel module. Its quotient graph is an empty graph.
27    Parallel,
28    /// A trivial module with a single node. This is leaf node in the [MDTree].
29    Node(NodeId),
30}
31
32impl<NodeId: Debug + Copy + PartialEq> Debug for ModuleKind<NodeId> {
33    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
34        match self {
35            ModuleKind::Prime => {
36                write!(f, "Prime")
37            }
38            ModuleKind::Series => {
39                write!(f, "Series")
40            }
41            ModuleKind::Parallel => {
42                write!(f, "Parallel")
43            }
44            ModuleKind::Node(v) => {
45                write!(f, "{v:?}")
46            }
47        }
48    }
49}
50
51/// A modular decomposition tree.
52///
53/// The tree is non-empty and rooted.
54///
55/// A node in the tree is a strong module of the original graph.
56/// The modules have a type: `Prime`, `Series`, or `Parallel` for inner nodes and `Node(_)` for leaf nodes.
57///
58/// The nodes at the leaves are exactly the nodes of the original graph.
59///
60/// The leaves of a subtree rooted at a module are the set of nodes of the original graph that are a strong module. They can be obtained by [MDTree::nodes].
61#[derive(Clone, Debug)]
62pub struct MDTree<NodeId: Copy + PartialEq> {
63    tree: DiGraph<ModuleKind<NodeId>, ()>,
64    root: ModuleIndex,
65}
66
67/// Module identifier.
68#[derive(Copy, Clone, Eq, PartialEq, Hash, Ord, PartialOrd)]
69pub struct ModuleIndex(pub(crate) petgraph::graph::NodeIndex);
70
71impl Debug for ModuleIndex {
72    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
73        f.debug_tuple("ModuleIndex").field(&self.0.index()).finish()
74    }
75}
76
77impl ModuleIndex {
78    /// Create new index from `usize`.
79    pub fn new(x: usize) -> Self {
80        Self(petgraph::graph::NodeIndex::new(x))
81    }
82
83    /// Returns the index as `usize`.
84    pub fn index(&self) -> usize {
85        self.0.index()
86    }
87}
88
89impl<NodeId: Copy + PartialEq> MDTree<NodeId> {
90    /// Create a new modular decomposition tree.
91    ///
92    /// Assumes that the input `DiGraph` is rooted tree with node weights
93    /// `Prime`, `Series`, and `Parallel` for inner nodes and `Vertex(_)`
94    /// for leaf nodes. This is not checked explicitly.
95    ///
96    /// Return `NullGraph` if the input graph does not have any nodes.
97    ///
98    /// Panics if all nodes have a non-zero in-degree.
99    pub(crate) fn from_digraph(tree: DiGraph<ModuleKind<NodeId>, ()>) -> Result<Self, NullGraphError> {
100        if tree.node_count() == 0 {
101            return Err(NullGraphError);
102        }
103        let root = tree.externals(Incoming).next().expect("non-null trees must have a root");
104        let root = ModuleIndex(root);
105        Ok(Self { tree, root })
106    }
107
108    /// Return the number of strong modules in the modular decomposition tree.
109    ///
110    /// These are all the nodes of the tree.
111    #[inline(always)]
112    pub fn strong_module_count(&self) -> usize {
113        self.tree.node_count()
114    }
115
116    /// Return the root module index.
117    #[inline(always)]
118    pub fn root(&self) -> ModuleIndex {
119        self.root
120    }
121
122    /// Access the [ModuleKind] of a module.
123    ///
124    /// If the module does not exist, return None.
125    pub fn module_kind(&self, module: ModuleIndex) -> Option<&ModuleKind<NodeId>> {
126        self.tree.node_weight(module.0)
127    }
128
129    /// Return an iterator yielding references to [ModuleKind]s for all modules.
130    pub fn module_kinds(&self) -> impl Iterator<Item = &ModuleKind<NodeId>> {
131        self.tree.node_weights()
132    }
133
134    /// Return an iterator for the children of a module.
135    pub fn children(&self, module: ModuleIndex) -> impl Iterator<Item = ModuleIndex> + '_ {
136        self.tree.neighbors_directed(module.0, Outgoing).map(ModuleIndex)
137    }
138
139    /// Return the nodes of a module.
140    ///
141    /// The nodes represent nodes of the original graph and not modules of the [MDTree].
142    /// These are the leaves of the subtree rooted at `module` in the [MDTree].
143    pub fn nodes(&self, module: ModuleIndex) -> impl Iterator<Item = NodeId> + '_ {
144        let mut stack = vec![module.0];
145        from_fn(move || {
146            while let Some(next) = stack.pop() {
147                if let Some(ModuleKind::Node(node)) = self.tree.node_weight(next) {
148                    return Some(*node);
149                } else {
150                    let children = self.tree.neighbors_directed(next, Outgoing);
151                    stack.extend(children);
152                }
153            }
154            None
155        })
156    }
157
158    /// Convert to [DiGraph].
159    ///
160    /// This allows the use of [petgraph] algorithms. Use [ModuleIndex::index] and
161    /// [petgraph::graph::NodeIndex::new] to convert the root index.
162    ///
163    /// ```rust
164    /// # use std::error::Error;
165    /// #
166    /// # fn main() -> Result<(), Box<dyn Error>> {
167    /// use petgraph::graph::{NodeIndex, UnGraph};
168    /// use petgraph::visit::Dfs;
169    /// use modular_decomposition::{modular_decomposition, ModuleKind};
170    ///
171    /// let graph = UnGraph::<(), ()>::from_edges([(0, 2), (1, 2), (2, 3), (3, 4), (3, 5)]);
172    /// let md = modular_decomposition(&graph)?;
173    ///
174    /// let root = NodeIndex::new(md.root().index());
175    /// let digraph = md.into_digraph();
176    ///
177    /// let mut dfs = Dfs::new(&digraph, root);
178    /// let mut node_order = vec![];
179    /// while let Some(node) = dfs.next(&digraph) { node_order.push(*digraph.node_weight(node).unwrap()); }
180    ///
181    /// let expected_node_order = [
182    ///     ModuleKind::Prime,
183    ///     ModuleKind::Node(NodeIndex::new(2)),
184    ///     ModuleKind::Parallel,
185    ///     ModuleKind::Node(NodeIndex::new(0)),
186    ///     ModuleKind::Node(NodeIndex::new(1)),
187    ///     ModuleKind::Node(NodeIndex::new(3)),
188    ///     ModuleKind::Parallel,
189    ///     ModuleKind::Node(NodeIndex::new(4)),
190    ///     ModuleKind::Node(NodeIndex::new(5)),
191    /// ];
192    /// assert_eq!(node_order, expected_node_order);
193    /// # Ok(())
194    /// # }
195    /// ```
196    pub fn into_digraph(self) -> DiGraph<ModuleKind<NodeId>, ()> {
197        self.tree
198    }
199}
200
201/// A graph does not contain any nodes or edges.
202#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash, Ord, PartialOrd)]
203pub struct NullGraphError;
204
205impl Display for NullGraphError {
206    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
207        f.write_str("graph does not contain any nodes or edges")
208    }
209}
210
211impl std::error::Error for NullGraphError {}
212
213#[cfg(test)]
214mod test {
215    use petgraph::graph::{DiGraph, NodeIndex};
216    use petgraph::visit::IntoNodeIdentifiers;
217    use petgraph::Outgoing;
218
219    use crate::md_tree::NullGraphError;
220    use crate::tests::{complete_graph, pace2023_exact_024};
221    use crate::{modular_decomposition, MDTree, ModuleIndex, ModuleKind};
222
223    #[test]
224    fn nodes() {
225        let graph = pace2023_exact_024();
226        let md = modular_decomposition(&graph).unwrap();
227        let mut module_nodes: Vec<(ModuleKind<_>, Vec<_>)> = (0..md.strong_module_count())
228            .map(ModuleIndex::new)
229            .map(|module| (*md.module_kind(module).unwrap(), md.nodes(module).map(|node| node.index()).collect()))
230            .collect();
231        module_nodes.iter_mut().for_each(|(_, nodes)| nodes.sort());
232        module_nodes.sort();
233
234        for (kind, nodes) in &module_nodes {
235            if nodes.len() == 1 {
236                assert_eq!(*kind, ModuleKind::Node(NodeIndex::new(nodes[0])));
237            }
238            if nodes.len() == graph.node_count() {
239                assert_eq!(*nodes, graph.node_identifiers().map(|node| node.index()).collect::<Vec<_>>());
240            }
241        }
242
243        module_nodes.retain(|(_, nodes)| nodes.len() > 1);
244
245        let expected = [
246            (
247                ModuleKind::Prime,
248                vec![
249                    0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 20, 21, 22, 23, 26, 27, 28, 29, 30, 31,
250                    32, 33, 34, 35, 36, 37, 38, 39,
251                ],
252            ),
253            (ModuleKind::Series, vec![17, 18, 19]),
254            (ModuleKind::Series, vec![24, 25]),
255            (
256                ModuleKind::Parallel,
257                vec![
258                    0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26,
259                    27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
260                ],
261            ),
262            (ModuleKind::Parallel, vec![20, 30]),
263        ];
264        assert_eq!(module_nodes, expected);
265    }
266
267    #[test]
268    fn mdtree_and_digraph_are_equivalent() {
269        let graph = complete_graph(5);
270        let md = modular_decomposition(&graph).unwrap();
271        let root = md.root();
272
273        assert_eq!(md.module_kind(root), Some(&ModuleKind::Series));
274
275        let children: Vec<_> = md.children(root).collect();
276        assert_eq!(md.module_kind(children[0]), Some(&ModuleKind::Node(NodeIndex::new(0))));
277
278        let md = md.into_digraph();
279        let root = NodeIndex::new(root.index());
280
281        let children: Vec<_> = md.neighbors_directed(root, Outgoing).collect();
282        assert_eq!(md.node_weight(root), Some(&ModuleKind::Series));
283        assert_eq!(md.node_weight(children[0]), Some(&ModuleKind::Node(NodeIndex::new(0))));
284    }
285
286    #[test]
287    fn null_graph_error() {
288        let digraph: DiGraph<ModuleKind<NodeIndex>, ()> = Default::default();
289        let err = MDTree::from_digraph(digraph).unwrap_err();
290        assert_eq!(err, NullGraphError);
291        assert_eq!(format!("{}", err), "graph does not contain any nodes or edges".to_string());
292    }
293
294    #[test]
295    fn module_index_fmt() {
296        let idx = ModuleIndex::new(42);
297        assert_eq!(format!("{:?}", idx), "ModuleIndex(42)".to_string())
298    }
299}
modular_decomposition/md_tree/mod.rs

modular_decomposition/md_tree/
mod.rs
