Skip to content

jonasspinner/modular-decomposition

Repository files navigation

Modular Decomposition

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

docs.rs Coverage Status Crates.io Crates.io DOI

This project implements several algorithms for computing the modular decomposition and evaluates them. It is structures as follows.

Library

Algorithms

  • crates/linear-ref-sys/crates/linear-ref Bindings and wrapper to reference C++ implementation [Miz23] based on [TCHP08].
  • crates/linear Rust port of [Miz23] based on [TCHP08].
  • crates/skeleton Based on [MS00].
  • crates/fracture Based on [HPV99] and [CHM02]. Uses the implementation in crates/modular-decomposition.

Others

  • crates/common Common utilities shared by the algorithm crate
  • crates/playground A crate to experiment with related algorithms and data structures.
  • crates/evaluation Evaluation of the algorithms on real-world and generated data.

Usage

The crate crates/modular-decomposition provides an API to compute the modular decomposition.

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

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

Evaluation

This figure shows the algorithm performance for some datasets. The time for multiple runs is averaged for each instance and algorithm. The time for each algorithm is divided by the best time and the distribution is plotted. The fracture algorithm performs best for most instances. The evaluation code can be found in crates/evaluation.

Citing

Jonas Spinner. "A Practical Evaluation of Modular Decomposition Algorithms". https://doi.org/10.5445/IR/1000170363

@mastersthesis{Spinner2024,
    doi          = {10.5445/IR/1000170363},
    url          = {https://doi.org/10.5445/IR/1000170363},
    title        = {A Practical Evaluation of Modular Decomposition Algorithms},
    author       = {Spinner, Jonas},
    year         = {2024},
    publisher    = {{Karlsruher Institut für Technologie (KIT)}},
    school       = {Karlsruher Institut für Technologie (KIT)},
    language     = {english}
}

References