NAME
Graph::ChuLiuEdmonds  Find minimum spanning trees in a directed graph.
VERSION
Version 0.05
SYNOPSIS
This module implements ChuLiuEdmonds [1],[2] algorithm for finding a minimum spanning tree (MST) in a directed graph.
use Graph;
use Graph::Directed;
use Graph::ChuLiuEdmonds;
my $graph = Graph::Directed>new(vertices=>[qw(a b c d)]);
$graph>add_weighted_edges(qw(a b 3 c d 7 d a 2 d b 1 c a 2));
my $msts = $graph>MST_ChuLiuEdmonds($graph);
...
EXPORT
None.
FUNCTIONS
MST_ChuLiuEdmonds
my $msts = $graph>MST_ChuLiuEdmonds();
Returns a Graph object that is a forest consisting of MSTs for a given directed graph.
Minimum Spanning Trees or MSTs are directed tree subgraphs derived from a directed graph that "span the graph" (covering all the vertices) using as lightly weighted (hence the "minimum") edges as possible.
MST_ChuLiuEdmonds_no_copy
my $msts = $graph>MST_ChuLiuEdmonds();
Like the method above, only avoiding deepcopying the graph; the method prunes $graph so as only the MSTs remain of it.
AUTHOR
Petr Pajas, <pajas at matfyz.cz>
CAVEATS
 o

The implementation was not tested on complex examples.
 o

Vertices cannot be perl objects (or references).
 o

Vertex and edge attributes are not copied from the source graph to the resulting graph (except for edge weights).
 o

The author did not attempt to compute the actual algorithmic complexity of this particular implementation.
 o

The algorithm implemented in this module returns the optimal MSTs. To obtain kbest MSTs, one could implement Camerini's algorithm [4] (also described in [5]).
BUGS
Please report any bugs or feature requests to buggraphchuliuedmonds at rt.cpan.org
, or through the web interface at http://rt.cpan.org/NoAuth/ReportBug.html?Queue=GraphChuLiuEdmonds. I will be notified, and then you'll automatically be notified of progress on your bug as I make changes.
SUPPORT
You can find documentation for this module with the perldoc command.
perldoc Graph::ChuLiuEdmonds
You can also look for information at:
AnnoCPAN: Annotated CPAN documentation
CPAN Ratings
RT: CPAN's request tracker
http://rt.cpan.org/NoAuth/Bugs.html?Dist=GraphChuLiuEdmonds
Search CPAN
SEE ALSO
The implementation follows the algorithm published by Edmonds [1] and independently Chu and Liu [2], as scatched in the 3rd section of [3]. Note that possibly more efficient implementation is suggested in [3].
 [1]

J. Edmonds. 1967. Optimum branchings. Journal of Research of the National Bureau of Standards, 71B:233240.
 [2]

Y.J. Chu and T.H. Liu. 1965. On the shortest arborescence of a directed graph. Science Sinica, 14:13961400.
 [3]

H. N. Gabow, Z. Galil, T. Spencer and R. E. Tarjan. 1986 Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica 6 (2) 109122
 [4]

Paolo M. Camerini, Luigi Fratta, and Francesco Maffioli. 1980. The k best spanning arborescences of a network. Networks, 10:91110.
 [5]

Keith Hall. 2007. kbest spanning tree parsing. In (To Appear) Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics.
ACKNOWLEDGEMENTS
The development of this module was supported by grant GA AV CR 1ET101120503.
COPYRIGHT & LICENSE
Copyright 2008 Petr Pajas, all rights reserved.
This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.