Crate modular_decomposition

This is a library to compute the modular decomposition of a simple, undirected graph.

A node set M is a module if every node has the same neighborhood outside M. The set of all nodes V and the sets with a single node {u} are trivial modules.

Examples

The smallest prime graph is the path graph on 4 nodes.

use petgraph::graph::UnGraph;
use modular_decomposition::{ModuleKind, modular_decomposition};

// a path graph with 4 nodes
let graph = UnGraph::<(), ()>::from_edges([(0, 1), (1, 2), (2, 3)]);
let md = modular_decomposition(&graph)?;

assert_eq!(md.module_kind(md.root()), Some(&ModuleKind::Prime));

Determining whether a graph is a cograph.

use petgraph::graph::UnGraph;
use modular_decomposition::{ModuleKind, modular_decomposition};

// a complete graph with 3 nodes
let graph = UnGraph::<(), ()>::from_edges([(0, 1), (0, 2), (1, 2)]);
let md = modular_decomposition(&graph)?;

// a graph is a cograph exactly if none of its modules is prime
let is_cograph = md.module_kinds().all(|kind| *kind != ModuleKind::Prime);
assert!(is_cograph);

Generics

The algorithm is implemented for structs that implement the petgraph traits NodeCompactIndexable, IntoNeighbors, and GraphProp<EdgeType = Undirected>.

References

• [HPV99]: Michel Habib, Christophe Paul, and Laurent Viennot. “Partition Refinement Techniques: An Interesting Algorithmic Tool Kit”. https://doi.org/10.1142/S0129054199000125.
• [CHM02]: Christian Capelle, Michel Habib, and Fabien Montgolfier. “Graph Decompositions and Factorizing Permutations”. https://doi.org/10.46298/dmtcs.298.

Re-exports

pub use fracture::modular_decomposition;

Modules

fracture

A modular decomposition algorithm.

Structs

MDTree

A modular decomposition tree.

ModuleIndex

Module identifier.

Enums

ModuleKind

Module kinds of nodes in a MDTree.