#graph-node #decomposition #modular #graph #graph-algorithms #undirected-graph

modular-decomposition

A library for computing the modular decomposition of a graph

2 unstable releases

0.2.0 Jun 10, 2024
0.1.0 Mar 12, 2024

#531 in Algorithms

Download history 128/week @ 2024-03-11 2/week @ 2024-03-18 23/week @ 2024-04-01 141/week @ 2024-06-10

141 downloads per month

MIT license

64KB
1.5K SLoC

Modular Decomposition

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

docs.rs Coverage Status Crates.io Crates.io

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.

Dependencies

~2.5MB
~35K SLoC