Graph::ModularDecomposition - Modular decomposition of directed graphs
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 );
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 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).
Several graph algorithms use the modular decomposition tree as a 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 node-series-parallel. Checking if a digraph is series-parallel can also be determined using the O(m+n) Valdes-Tarjan-Lawler algorithm published in 1982, but this only constructs a decomposition tree if the input is series-parallel: other inputs are simply classified as non-series-parallel.
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. doi:10.1006/jagm.1994.1013
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), see
R. M. McConnell and F. de Montgolfier, "Linear-time modular decomposition of directed graphs", Discrete Applied Mathematics 145 (2005), pp. 198-209. doi:10.1016/j.dam.2004.02.017
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.
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. Object-level debugging is not yet supported.
my $g = new Graph::ModularDecomposition; Graph::ModularDecomposition->canonical_form(1); # on (default) Graph::ModularDecomposition->canonical_form(0); # 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.
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.
$object->new
my $g = Graph::ModularDecomposition ->pairstring_to_graph( 'ac, ad, bd' ); my $h = $g->pairstring_to_graph( 'a-c, a-d,b-d' ); # same thing my $h = $g->pairstring_to_graph( 'a,b,c,d,a-c,a-d,b-d' ); # 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 'a-b,b-c,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 multi-character vertex labels are in use. Single label "pairs" are interpreted as vertices to add.
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.
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.
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.
use Graph::ModularDecomposition; my $G = new Graph::ModularDecomposition; foreach ( 'ac', 'ad', 'bd' ) { $G->add_edge( split // ) } restriction( $G, split(//, 'abdefgh') ); # a-d,b-d $G->restriction( split(//, 'abdefgh') ); # same thing
Compute G|X, the subgraph of G induced by X. X is represented as a list of vertices.
$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.
@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.
my $p = partition( $g, $v ); $p = $g->partition( $v ); # same thing
For a graph, calculate maximal modules not including a given vertex.
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, $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.
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.
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.
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) 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.
The decomposition tree consists of nodes with attributes: 'type' is a string matching /^leaf|primitive|complete|linear$/, '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 /^0|1|01$/. 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.
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 non-transitive i indecomposable d decomposable but not SP, at least one non-primitive node s series-parallel p decomposable but each module is primitive or series u unclassified: should not happen
$b = $g->to_bitvector2;
Convert input graph to Bitvector2 output. Graph::Directed version 20104 permits multi-edges; 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.
Andras Salamon, <azs@cpan.org>
Copyright 2004-17, Andras Salamon.
This code is distributed under the same copyright terms as Perl itself.
perl, Graph, Graph::Bitvector2.
To install Graph::ModularDecomposition, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Graph::ModularDecomposition
CPAN shell
perl -MCPAN -e shell install Graph::ModularDecomposition
For more information on module installation, please visit the detailed CPAN module installation guide.