Graph::ChuLiuEdmonds - Find minimum spanning trees in a directed graph.

Version 0.04

This module implements Chu-Liu-Edmonds [1],[2] algorithm for finding a minimum spanning tree (MST) in a directed graph.

    use Graph;
    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);
    ...

None.

  my $msts = $graph->MST_ChuLiuEdmond();

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.

  my $msts = $graph->MST_ChuLiuEdmond();

Like the method above, only avoiding deep-copying the graph; the method prunes $graph so as only the MSTs remain of it.

Petr Pajas, <pajas at matfyz.cz>

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 k-best MSTs, one could implement Camerini's algorithm [4] (also described in [5]).

Please report any bugs or feature requests to bug-graph-chuliuedmonds at rt.cpan.org, or through the web interface at http://rt.cpan.org/NoAuth/ReportBug.html?Queue=Graph-ChuLiuEdmonds. I will be notified, and then you'll automatically be notified of progress on your bug as I make changes.

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

http://annocpan.org/dist/Graph-ChuLiuEdmonds

* CPAN Ratings

http://cpanratings.perl.org/d/Graph-ChuLiuEdmonds

* RT: CPAN's request tracker

http://rt.cpan.org/NoAuth/Bugs.html?Dist=Graph-ChuLiuEdmonds

* Search CPAN

http://search.cpan.org/dist/Graph-ChuLiuEdmonds

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:233-240.

[2]

Y.J. Chu and T.H. Liu. 1965. On the shortest arborescence of a directed graph. Science Sinica, 14:1396-1400.

[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) 109-122

[4]

Paolo M. Camerini, Luigi Fratta, and Francesco Maffioli. 1980. The k best spanning arborescences of a network. Networks, 10:91-110.

[5]

Keith Hall. 2007. k-best spanning tree parsing. In (To Appear) Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics.

The development of this module was supported by grant GA AV CR 1ET101120503.

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.