use v6;
unit class Algorithm::Kruskal:ver<0.0.1>:auth<zef:titsuki>;

use Algorithm::MinMaxHeap;
use Algorithm::SetUnion;
use Algorithm::MinMaxHeap::Comparable;

has $.vertex-size is required;
has Algorithm::MinMaxHeap $!heap;

submethod BUILD(:$!vertex-size) {
    $!heap = Algorithm::MinMaxHeap[Algorithm::MinMaxHeap::Comparable].new;
}

method add-edge(Int $from, Int $to, Num $weight) {
    my class State {
        also does Algorithm::MinMaxHeap::Comparable[State];

        has ($.from, $.to);
        has $.weight;
        submethod BUILD (:$!from, :$!to, :$!weight) {}
        method compare-to(State $s) {
            if self.weight == $s.weight {
                return Order::Same;
            }
            if self.weight > $s.weight {
                return Order::More;
            }
            if self.weight < $s.weight {
                return Order::Less;
            }
        }
    }
    $!heap.insert: State.new(from => $from, to => $to, weight => $weight);
}

method compute-minimal-spanning-tree(--> List) {
    my $weight = 0;
    my @edges;
    my $prev-heap = $!heap.clone;
    my Algorithm::SetUnion $set-union .= new(size => $!vertex-size);
    until $!heap.is-empty {
        my $state = $!heap.pop-min;
        if $set-union.union($state.from, $state.to) {
            $weight += $state.weight;
            @edges.push: [$state.from, $state.to];
        }
    }
    $!heap = $prev-heap;
    return :@edges, :$weight;
}



head

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


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]]


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


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


item

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


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


Adds a edge to the graph. C<<$weight>> is the weight between vertex C<<$from>> and vertex C<<$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.


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.


root

README

React

=begin React :component<HeaderCol> :id<menu> 
=para L<Documentation|/doc/introduction>
=para L<Modules| /mods>
=para L<Examples| file:../examples/index.podlite>
=para L<Download |file:../download/index.podlite>
=para L<About|file:../about/index.podlite>
=para 🔍 K<⌘K>/K<ctrl-K>
=end React


=begin React :component<HeaderCol> :id<footer>  
=begin nested :!nested
=item1 B<Language>
    =item2 L<Get started|file:../getting-started/getting-started.podlite>
    =item2 L<Why Raku?|/doc/language/faq#Why-should-I-learn-Raku-What's-so-great-about-it>
    =item2 L<Try Raku|https://glot.io/new/raku>
    =item2 L<Raku cheat sheet|https://github.com/Raku/mu/blob/master/docs/Perl6/Cheatsheet/cheatsheet.txt>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<Raku on Exercism|https://exercism.org/tracks/raku>
    =item2 L<Wikipedia|https://en.wikipedia.org/wiki/Raku_(programming_language)>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>

=end nested
=begin nested :!nested

=item1 B<L<Documentation|/doc>>
    =item2 L<Getting started, Migration guides from other languages, & Tutorials | file:../doc/introduction.podlite>
    =item2 L<Language References|file:../doc/reference.podlite>
    =item2 L<Type Reference| file:../doc/types.podlite>
    =item2 L<Miscellaneous| file:../doc/miscellaneous.podlite>
    =item2 L<FAQs (Frequently Asked Questions)|/doc/language/faq>
    =item2 L<Community|/doc/language/community>
    =item2 L<The list of all documents|file:../doc/index.podlite>

=item1 B<Resources>
    =item2 L<The Raku Guide|https://raku.guide/>
    =item2 L<Books |https://perl6book.com/>
    =item2 L<Rosetta Code | https://www.raku.org/community/rosettacode>

=end nested
=begin nested :!nested

=item1 B<Resoures>
    =item2 L<Download | file:../download/index.podlite>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>

=item1 B<Learning>
    =item2 L<The Raku Guide|https://raku.guide/>
    =item2 L<Wikibook |https://en.wikibooks.org/wiki/Raku_Programming>
    =item2 L<Books |https://perl6book.com/>
    =item2 L<Rosetta Code | https://www.raku.org/community/rosettacode>
    =item2 L<Learn Raku in Y minutes|https://learnxinyminutes.com/docs/raku/>
    =item2 L<Golfing |https://github.com/AlexDaniel/raku-golf-cheatsheet>
=end nested
=begin nested :!nested

=item1 B<Explore>
    =item2 L<Raku Blog Aggregator|https://planet.raku.org/>
    =item2 L<Rakudo Weekly|https://rakudoweekly.blog/>
    =item2 L<The Weekly Challenge |https://perlweeklychallenge.org/>
    =item2 L<Raku Advent Calendar|https://raku-advent.blog/>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>

=end nested
=end React


=begin React :component<CookieConsent> :id<CookieConsent> :buttonCaption("Got it!")
=para
This website uses cookies for analytics.
=end React


Kruskal

NAME

SYNOPSIS

DESCRIPTION

CONSTRUCTOR

OPTIONS

METHODS

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

compute-minimal-spanning-tree() returns List

AUTHOR

COPYRIGHT AND LICENSE

Algorithm::Kruskal v0.0.1

Authors

License

Dependencies

Test Dependencies

Provides

Documentation