Petr Pajas > Graph-ChuLiuEdmonds > Graph::ChuLiuEdmonds

Download:
Graph-ChuLiuEdmonds-0.06.tar.gz

Dependencies

Annotate this POD

View/Report Bugs
Module Version: 0.06   Source  

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.

syntax highlighting: