## modular-decomposition

A library for computing the modular decomposition of a graph

### 2 unstable releases

 0.2.0 Jun 10, 2024 Mar 12, 2024

#531 in Algorithms

64KB
1.5K SLoC

# Modular Decomposition

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)?;

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

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

~2.5MB
~35K SLoC