Graph::ModularDecomposition 0.13

Graph::ModularDecomposition is a Perl module for 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 "yesn" if check_transitive( $h ); print "yesn" 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)..

Requirements:	No special requirements
Platforms:	Linux
Keyword:	Decomposition,  Directed,  Graph,  Graphmodulardecomposition,  Libraries,  Modular,  Modular Decomposition,  Modulardecomposition,  Module,  Perl Module,  Programming,  Tree
Users rating:	0/10