Algorithm::Kruskal is a perl6 implementation of Kruskal's Algorithm for constructing a spanning subtree of minimum length
Perl6
Switch branches/tags
Nothing to show
Latest commit f9ca446 Apr 27, 2017 @titsuki committed on GitHub Merge pull request #2 from titsuki/make-minmax-uptodate
Fix constructor
Permalink
Failed to load latest commit information.
lib/Algorithm Fix constructor Apr 26, 2017
t Initial commit Mar 22, 2016
.gitignore Initial commit Mar 22, 2016
.travis.yml Initial commit Mar 22, 2016
LICENSE Initial commit Mar 22, 2016
META6.json Use SPDX identifier in license field of META6.json Apr 26, 2017
README.md Change mail address Mar 24, 2016

README.md

Build Status

NAME

Algorithm::Kruskal - a perl6 implementation of Kruskal's Algorithm for constructing a spanning subtree of minimum length

SYNOPSIS

use Algorithm::Kruskal;

my $kruskal = Algorithm::Kruskal.new(vertex-size => 4);

$kruskal.add-edge(0, 1, 2);
$kruskal.add-edge(1, 2, 1);
$kruskal.add-edge(2, 3, 1);
$kruskal.add-edge(3, 0, 1);
$kruskal.add-edge(0, 2, 3);
$kruskal.add-edge(1, 3, 5);

my %forest = $kruskal.compute-minimal-spanning-tree();
%forest<weight>.say; # 3
%forest<edges>.say; # [[1 2] [2 3] [3 0]]

DESCRIPTION

Algorithm::Kruskal is a perl6 implementation of Kruskal's Algorithm for constructing a spanning subtree of minimum length

CONSTRUCTOR

my $kruskal = Algorithm::Kruskal.new(%options);

OPTIONS

  • vertex-size => $vertex-size

Sets vertex size. The vertices are numbered from 0 to $vertex-size - 1.

METHODS

add-edge(Int $from, Int $to, Real $weight)

$kruskal.add-edge($from, $to, $weight);

Adds a edge to the graph. $weight is the weight between vertex $from and vertex $to.

compute-minimal-spanning-tree() returns List

my %forest = $kruskal.compute-minimal-spanning-tree();
%forest<edges>.say; # display edges
%forest<weight>.say; # display weight

Computes and returns a minimal spanning tree and its weight.

AUTHOR

titsuki titsuki@cpan.org

COPYRIGHT AND LICENSE

Copyright 2016 titsuki

This library is free software; you can redistribute it and/or modify it under the Artistic License 2.0.

This algorithm is from Kruskal, Joseph B. "On the shortest spanning subtree of a graph and the traveling salesman problem." Proceedings of the American Mathematical society 7.1 (1956): 48-50.