/ 
Graph-ModularDecomposition-0.15
River stage zero No dependents
/ Graph::ModularDecomposition

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 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

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. Object-level debugging is not yet supported.

canonical_form()
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.

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( '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.

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') ); # 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.

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) 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.

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 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

to_bitvector2()
$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.

AUTHOR

Andras Salamon, <azs@cpan.org>

COPYRIGHT

Copyright 2004-17, Andras Salamon.

This code is distributed under the same copyright terms as Perl itself.

SEE ALSO

perl, Graph, Graph::Bitvector2.