Graph::ModularDecompositionGraph::ModularDecomposition is a Perl module for modular decomposition of directed graphs. | |
Download |
Graph::ModularDecomposition Ranking & Summary
Advertisement
- License:
- Perl Artistic License
- Price:
- FREE
- Publisher Name:
- Andras Salamon
- Publisher web site:
- http://search.cpan.org/~azs/
Graph::ModularDecomposition Tags
Graph::ModularDecomposition Description
Graph::ModularDecomposition is a Perl module for modular decomposition of directed graphs. 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: · Perl
Graph::ModularDecomposition Related Software