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.

The modular decomposition algorithm in this library has a O(n + m log n) running time and is based on [HPV99] and [CHM02]. Although linear time algorithms exists, they perform worse in comparison.

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).unwrap();

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).unwrap();

// 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>.

Evaluation

As part of a thesis, we evaluated four implementations of modular decomposition algorithms. The fracture algorithm performs best and is provided in this library. For more information see the repository.