NAME
Graph::ModularDecomposition  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 "yes\n" if check_transitive( $h );
print "yes\n" if $h>check_transitive; # same thing
my $m = $h>modular_decomposition_EGMS;
print tree_to_string( $m );
DESCRIPTION
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).
RELATED WORK
Several recent graph algorithms have used the modular decomposition tree as a basic building block. 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 nodeseriesparallel. Checking if a digraph is seriesparallel can also be determined using the O(m+n) ValdesTarjanLawler algorithm published in 1982, but this only constructs a decomposition tree if the input is seriesparallel: other inputs are simply classified as nonseriesparallel.
The code here is based on algorithm 6.1 for modular decomposition of twostructures, from
A. Ehrenfeucht, H. N. Gabow, R. M. McConnell, and S. J. Sullivan, "An O(n^2) DivideandConquer Algorithm for the Prime Tree Decomposition of TwoStructures and Modular Decomposition of Graphs", Journal of Algorithms 16 (1994), pp. 283294.
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) runtime 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. 147168.
EXPORT
None by default. Methods tree_to_string() and partition_to_string() can be imported. Methods setminus() and setunion() are for internal use but can also be imported.
METHODS
 debug()

my $g = new Graph::ModularDecomposition; Graph::ModularDecomposition>debug(1); # turn on debugging Graph::ModularDecomposition>debug(2); # extra debugging $g>debug(2); # same thing $g>debug(0); # off (default)
Manipulates the debug level of this module. Debug output is sent to STDERR. Objectlevel debugging is not yet supported.
 canonical_form()

my $g = new Graph::ModularDecomposition; Graph::ModularDecomposition>canonical_form(1); # on (default) Graph::ModularDecomposition>canonical_form(0); # turn it off $g>canonical_form(1); # same thing $g>canonical_form(0); # off print "yes" if $g>canonical_form();
Manipulates whether this module keeps modular decomposition trees in "canonical" form, where lists of vertices are kept sorted. This allows tree_to_string() on two isomorphic decomposition trees to produce the same output (well, sometimes  a more general solution requires an isomorphism test). Canonical form forces sorting of vertices in several places, which will slow down some of the algorithms. When called with no arguments, returns the current state.
 new()

my $g = new Graph::ModularDecomposition; $g = Graph::ModularDecomposition>new; # same thing my $h = $g>new;
Constructor. The instance method style
$object
new> is an extension and was not present in Graph::Directed.  pairstring_to_graph

my $g = Graph::ModularDecomposition >pairstring_to_graph( 'ac, ad, bd' ); my $h = $g>pairstring_to_graph( 'ac, ad,bd' ); # same thing my $h = $g>pairstring_to_graph( 'a,b,c,d,ac,ad,bd' ); # same thing use Graph::ModularDecomposition qw( pairstring_to_graph ); my $k = pairstring_to_graph( 'Graph::ModularDecomposition', 'ac,ad,bd' ); # same thing
Convert string of pairs input to Graph::ModularDecomposition output. Allows either 'ab,bc,d' or 'ab,bc,d' style notation but these should not be mixed in one string. Vertex labels should not include the '' character. Use the '' style if multicharacter vertex labels are in use. Single label "pairs" are interpreted as vertices to add.
 check_transitive()

my $g = new Graph::ModularDecomposition; # add some edges... print "transitive" if $g>check_transitive;
Returns 1 if input digraph is transitive, '' otherwise. May break if Graph::stringify lists vertices in unsorted order.
 setminus()

my @d = setminus( ['a','b','c'], ['b','d'] ); # ('a','c')
Given two references to lists, returns the set difference of the two lists as a list. Can be imported.
 setunion()

my @u = setunion(['a','bc',42], [42,4,'a','c']); # ('a','bc',42,4,'c')
Given two references to lists, returns the set union of the two lists as a list. Can be imported.
 restriction()

use Graph::ModularDecomposition; my $G = new Graph::ModularDecomposition; foreach ( 'ac', 'ad', 'bd' ) { $G>add_edge( split // ) } restriction( $G, split(//, 'abdefgh') ); # ad,bd $G>restriction( split(//, 'abdefgh') ); # same thing
Compute GX, the subgraph of G induced by X. X is represented as a list of vertices.
 factor()

$h = factor( $g, [['a','b'], ['c'], ['d','e','f']] ); $h = $g>factor( [[qw(a b)], ['c'], [qw(d e f)]] ); # same thing
Compute G/P for partition P containing modules. Will fail in odd ways if members of P are not modules.
 partition_subsets()

@part = partition_subsets( $G, ['a','b','c'], $w ); @part = $G>partition_subsets( ['a','b','c'], $w ); # same thing
Partition set of vertices into maximal subsets not distinguished by w in G.
 partition()

my $p = partition( $g, $v ); $p = $g>partition( $v ); # same thing
For a graph, calculate maximal modules not including a given vertex.
 distinguishes()

print "yes" if distinguishes( $g, $x, $y, $z ); print "yes" if $g>distinguishes( $x, $y, $z ); # same thing
True if vertex $x distinguishes vertices $y and $z in graph $g.
 G()

$G = G( $g, $v ); $G = $g>G( $v ); # same thing
"Trivially" calculate G(g,v). dom(G(g,v)) = dom(g)\{v}, and (x,y) is an edge of G(g,v) whenever x distinguishes y and v in g.
 tree_to_string()

print tree_to_string( $t );
String representation of decomposition tree. Returns empty string for an empty decomposition tree. Needs to be explicitly imported. If Graph::vertices returns the vertices in unsorted order, then isomorphic trees can have different string representations.
 partition_to_string

print partition_to_string([['h'], [qw(c a b)], [qw(d e f g)]]); # a+b+c,d+e+f+g,h
String representation of partition. Returns empty string for an empty partition. Needs to be explicitly imported.
 modular_decomposition_EGMS()

use Graph::ModularDecomposition; $g = new Graph::ModularDecomposition; $m = $g>modular_decomposition_EGMS;
Compute modular decomposition tree of the input, which must be a Graph::ModularDecomposition object, using algorithm 6.1 of A. Ehrenfeucht, H. N. Gabow, R. M. McConnell, S. J. Sullivan, "An O(n^2) DivideandConquer Algorithm for the Prime Tree Decomposition of TwoStructures and Modular Decomposition of Graphs", Journal of Algorithms 16 (1994), pp. 283294.
The decomposition tree consists of nodes with attributes: 'type' is a string matching /^leafprimitivecompletelinear$/, 'children' is a reference to a potentially empty list of pointers to other nodes, 'value' is a string with the vertices in the decomposition defined by the tree, separated by '' (VSEP), and 'col' is a string containing the colour of the module, matching /^0101$/. A node with 'type' of 'complete' is parallel if 'col' is '0' and series if 'col' is '1'. A node with 'type' of 'linear' has 'col' of '01'. Use the function tree_to_string() to convert the tree into a more generally usable form.
 classify()

use Graph::ModularDecomposition; my $g = new Graph::ModularDecomposition; my $c = classify( $g ); $c = $g>classify; # same thing
Based on the modular decomposition tree, returns: n nontransitive i indecomposable d decomposable but not SP, at least one nonprimitive node s seriesparallel p decomposable but each module is primitive or series u unclassified: should not happen
 to_bitvector2()

$b = $g>to_bitvector2;
Convert input graph to Bitvector2 output. Graph::Directed version 20104 permits multiedges; these will be collapsed into a single edge in the output Bitvector2. The Bitvector2 is relative to the unique lexicographic ordering of the vertices. This method is only present if Graph::Bitvector2 is found.
AUTHOR
Andras Salamon, <andras@dns.net>
COPYRIGHT
Copyright 20045, Andras Salamon.
This code is distributed under the same copyright terms as Perl itself.