Graph::ModularDecomposition 0.13 review
DownloadGraph::ModularDecomposition is a Perl module for modular decomposition of directed graphs. SYNOPSIS use Graph::ModularDecom


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 nontransitive, or for transitive digraphs, as seriesparallel (linear or parallel modules only), decomposable (not seriesparallel, but with at least one nonprimitive 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).
Requirements:
Perl
Graph::ModularDecomposition 0.13 search tags