Graph::ModularDecomposition is a Perl module for modular decomposition of directed graphs.

SYNOPSIS

use Graph::ModularDecomposition qw(pairstring_to_graph tree_to_string);
my $g = new Graph::ModularDecomposition;

my $h = $g->pairstring_to_graph( ab,ac,bc );
print "yesn" if check_transitive( $h );
print "yesn" if $h->check_transitive; # same thing
my $m = $h->modular_decomposition_EGMS;
print tree_to_string( $m );

This module extends Graph::Directed by providing new methods related to modular decomposition.

The most important new method is modular_decomposition_EGMS(), which for a directed graph with n vertices finds the modular decomposition tree of the graph in O(n^2) time. Method tree_to_string() may be useful to represent the decomposition tree in a friendlier format; this needs to be explicitly imported.

If you need to decompose an undirected graph, represent it as a directed graph by adding two directed edges for each undirected edge.

The method classify() uses the modular decomposition tree to classify a directed graph as non-transitive, or for transitive digraphs, as series-parallel (linear or parallel modules only), decomposable (not series-parallel, but with at least one non-primitive module), indecomposable (primitive), decomposable but consisting of primitive or series modules only (only applies to graphs of at least 7 vertices), or unclassified (should never apply).