Tarjan: Difference between revisions
Rename Perl 6 -> Raku, alphabetize, minor clean-up
m (C++ classes made non-copyable) |
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
||
Line 313:
[7]
</pre>
=={{header|Julia}}==
Line 498 ⟶ 497:
Dave, Earl
Hank</pre>
=={{header|Phix}}==
Line 1,023 ⟶ 959:
'((7) (3 4) (5 6) (1 0 2))
</pre>
=={{header|Raku}}==
(formerly 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 ($vertex) {
state $index = 0;
%index{$vertex} = $index;
%lowlink{$vertex} = $index++;
%onstack{$vertex} = True;
@stack.push: $vertex;
for |%k{$vertex} -> $connection {
if not %index{$connection}.defined {
strong-connect($connection);
%lowlink{$vertex} min= %lowlink{$connection};
}
elsif %onstack{$connection} {
%lowlink{$vertex} min= %index{$connection};
}
}
if %lowlink{$vertex} eq %index{$vertex} {
my @node;
repeat {
@node.push: @stack.pop;
%onstack{@node.tail} = False;
} while @node.tail ne $vertex;
@connected.push: @node;
}
}
.&strong-connect unless %index{$_} for %k.keys;
@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|Sidef}}==
| |||