Graph/ModularDecomposition version 0.13 ======================================= 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. 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. 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). On a make test, Devel::Cover currently reports the following test coverage statistics (without Bitvector2 present): File stmt branch cond sub pod time total ---------------------------- ------ ------ ------ ------ ------ ------ ------ ...h/ModularDecomposition.pm 99.7 85.7 74.1 100.0 100.0 100.0 93.8 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. For the Pod tests, Test::More is required. Graph::ModularDecomposition is derived from Graph::Directed, which is part of Jarkko Hietaniemi's Graph module. At least version 0.20105 of Graph is required, since older versions had problems computing the graph of connected components and had broken inheritance behaviour. 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-5 by Andras Salamon