Graph::ModularDecomposition

Graph::ModularDecomposition is a Perl module that:

implements modular decomposition of directed graphs, using the O(n*n) runtime Ehrenfeucht-Gabow-McConnell-Sullivan algorithm from 1994;
extends Jarkko Hietaniemi's Graph module; and
adds a few generally useful methods, such as creation of a graph directly from a comma-separated string of edges, like the output of Graph::Directed::stringify().

For the algorithm, see 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.

You can get this module at CPAN, in directory /authors/id/A/AZ/AZS/graph/ or download from here:

Graph-ModularDecomposition-0.13.tar.gz (md5) 11-Dec-2005 (now supports multicharacter vertex labels)
Graph-ModularDecomposition-0.12.tar.gz (md5) 28-Oct-2005 (fixed nondeterministic test 12, added pod tests, tested with Graph-0.67)
Graph-ModularDecomposition-0.11.tar.gz (md5) 31-Oct-2004 (less verbose test output, compatible with Graph-0.50 beta)
Graph-ModularDecomposition-0.10.tar.gz (md5) 18-Oct-2004 (now needs Graph-0.20105)
Graph-ModularDecomposition-0.09.tar.gz (md5) 27-May-2004