Home  |  About Us  |  Link To Us  |  FAQ  |  Contact

# Graph::ModularDecomposition 0.13

Date Added: October 09, 2010  |  Visits: 808

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