/ 
Graph-ModularDecomposition-0.09
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 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 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.

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.

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.

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-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::vertices_unsorted is set.

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.

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 = $h->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 '|', 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

strongly_connected_graph(), TransitiveClosure_Floyd_Warshall(), APSP_Floyd_Warshall(), MST_Kruskal(), complete(), copy()

Stub constructors, included only if the version of Graph which is installed has broken inheritance behaviour. See Graph::Base. This is a horrible hack and you should rather patch Graph as suggested in the README for this module.

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, <andras@dns.net>

COPYRIGHT

Copyright 2004, Andras Salamon.

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

SEE ALSO

perl, Graph::Undirected, Graph::Base, Graph::Bitvector2.