Tarjan: Difference between revisions
→{{header|Perl 6}}: Add a Perl 6 example
(Added Kotlin) |
Thundergnat (talk | contribs) (→{{header|Perl 6}}: Add a Perl 6 example) |
||
Line 252:
</pre>
=={{header|Perl 6}}==
{{works with|Rakudo|2018.09}}
<lang perl6>sub tarjan (%k) {
my %onstack;
my %index;
my %lowlink;
my @stack;
my @connected;
sub strong-connect ($v) {
state $index = 0;
%index{$v} = $index;
%lowlink{$v} = $index;
++$index;
@stack.push: $v;
%onstack{$v} = True;
for |%k{$v} -> $w {
if not %index{$w}.defined {
strong-connect($w);
%lowlink{$v} = %lowlink{$v} min %lowlink{$w};
}
elsif %onstack{$w} {
%lowlink{$v} = %lowlink{$v} min %index{$w};
}
}
if %lowlink{$v} eq %index{$v} {
my @node;
repeat {
@node.push: @stack.pop;
%onstack{@node.tail} = False;
} while @node.tail ne $v;
@connected.push: @node;
}
}
.&strong-connect unless %index{$_} for %k.keys.sort;
@connected
}
# TESTING
-> $test { say "\nStrongly connected components: ", |tarjan($test).sort».sort } for
# hash of vertex, edge list pairs
(((1),(2),(0),(1,2,4),(3,5),(2,6),(5),(4,6,7)).pairs.hash),
# Same layout test data with named vertices instead of numbered.
%(:Andy<Bart>,
:Bart<Carl>,
:Carl<Andy>,
:Dave<Bart Carl Earl>,
:Earl<Dave Fred>,
:Fred<Carl Gary>,
:Gary<Fred>,
:Hank<Earl Gary Hank>
)</lang>
{{out}}
<pre>
Strongly connected components: (0 1 2)(3 4)(5 6)(7)
Strongly connected components: (Andy Bart Carl)(Dave Earl)(Fred Gary)(Hank)</pre>
=={{header|zkl}}==
<lang zkl>class Tarjan{
| |||