1 unstable release
0.1.0 | Mar 12, 2024 |
---|
#566 in Algorithms
153 downloads per month
60KB
1.5K
SLoC
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.
Dependencies
~2MB
~35K SLoC