Graph/ModularDecomposition version 0.09
=======================================
Graph::ModularDecomposition implements finding the modular
decomposition tree of a directed graph in O(n^2) time, where n is
the number of vertices in the graph. Several recent graph algorithms
have used the modular decomposition tree as a basic building block.
This implementation derives from Graph::Directed, providing additional
methods. If you need to decompose an undirected graph, represent it as
a directed graph by adding two directed edges for each undirected edge.
A simple example application of these routines is to construct and
search the modular decomposition tree of a directed graph to determine
if it is node-series-parallel. This can also be determined using
the Valdes-Tarjan-Lawler algorithm published in 1982, but modular
decomposition is more general. 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).
The code here is based on algorithm 6.1 for modular decomposition of
two-structures, from
A. Ehrenfeucht, H. N. Gabow, R. M. McConnell, and S. J. Sullivan,
"An O(n^2) Divide-and-Conquer Algorithm for the Prime Tree
Decomposition of Two-Structures and Modular Decomposition of
Graphs", Journal of Algorithms 16 (1994), pp. 283-294.
I am not aware of any other publicly available implementations.
Any errors and omissions are of course my fault. Better algorithms
are known: O(m+n) run-time can be achieved using sophisticated data
structures (where m is the number of edges in the graph). For a
recent discussion of the history of modular decomposition, see
E. Dahlhaus, J. Gustedt and R. M. McConnell, "Partially
Complemented Representations of Digraphs", Discrete Mathematics
and Theoretical Computer Science 5 (2002), pp. 147-168.
On a make test, Devel::Cover currently reports the following test
coverage statistics (with Bitvector2 present):
File stmt branch cond sub pod time total
---------------------------- ------ ------ ------ ------ ------ ------ ------
...h/ModularDecomposition.pm 99.7 83.7 74.1 100.0 100.0 100.0 93.4
INSTALLATION
To install this module, do the usual:
perl Makefile.PL
make
make test
make install
DEPENDENCIES
This module is for Perl 5.006 or later, and depends on standard
modules Carp and Exporter.
Graph::ModularDecomposition is derived from Graph::Directed, which is
part of Jarkko Hietaniemi's Graph module. At least version 0.20104
of Graph is required, since older versions had problems computing the
graph of connected components. The implementation of Graph::directed
in version 0.20104 unfortunately breaks inheritance, so if this problem
is detected, several stub routines are defined as a work-around.
A more elegant fix is to apply the following patch to Graph::Base.
This has been sent to Jarkko, but he is often very busy; hopefully
the next release of Graph fixes this issue.
--- Base.pm.orig 2004-05-05 22:54:25.000000000 +0200
+++ Base.pm 2004-05-25 09:19:57.000000000 +0200
@@ -214,15 +214,16 @@
my $o = $G->{ D }; # Old directedness.
$G->{ D } = $d;
- if (not $o) {
+ if (defined $o and not $o) {
my @E = $G->edges;
while (my ($u, $v) = splice(@E, 0, 2)) {
$G->add_edge($v, $u);
}
+ return bless $G, 'Graph::Directed'; # Re-bless.
}
- return bless $G, 'Graph::Directed'; # Re-bless.
+ return $G; # Don't re-bless unless needed.
} else {
return $G->undirected(not $d);
}
Two routines to convert to Graph::Bitvector2 objects are available if
Graph::Bitvector2 is installed. This module has not been released yet.
COPYRIGHT AND LICENCE
This module is licensed on the same copyright terms as Perl.
Copyright (C) 2004 by Andras Salamon