### 2 unstable releases

0.2.0 | Jun 10, 2024 |
---|---|

0.1.0 | Mar 12, 2024 |

#**531** in Algorithms

**141** downloads per month

**MIT**license

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

traits `petgraph`

, `NodeCompactIndexable`

, and `IntoNeighbors`

.`GraphProp <EdgeType = Undirected>`

## Evaluation

As part of a thesis, we evaluated four implementations of modular decomposition algorithms.
The

algorithm performs best and is provided in this library. For more information see
the repository.`fracture`

#### Dependencies

~2.5MB

~35K SLoC