C++ library to compute Lutz complexity of a graph
C++
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
Makefile
README.md
main.cpp
references.bib

README.md

lutz

Computes the Lutz complexity of a directed graph (see Lutz, 2002).

Description

This C++ program computes the Lutz complexity of a Boost Graph Library graph. The graph must be directed and have an associated boolean map indiciating which vertices are considered "modules".

Lutz complexity is the length of a description of the graph structure in bits. More complex graphs will require more bits to describe. As such, Lutz complexity can be used to compare different hierarchical modular decompositions (HMDs) of a given system.

Example

$ make
$ ./bin/hmd
Lutz complexities of various models (see Lutz, 2002)
flat model: 711.422
BUNCH model: 661.05
Lutz example model: 649.213