/ 
Graph-ChuLiuEdmonds-0.06
River stage one • 2 direct dependents • 7 total dependents
/ Graph::ChuLiuEdmonds

NAME

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

VERSION

Version 0.05

SYNOPSIS

This module implements Chu-Liu-Edmonds [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 deep-copying 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 k-best MSTs, one could implement Camerini's algorithm [4] (also described in [5]).

BUGS

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.

SUPPORT

You can find documentation for this module with the perldoc command.

perldoc Graph::ChuLiuEdmonds

You can also look for information at:

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

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.