Tarjan
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>
)
Output:
Strongly connected components: (0 1 2)(3 4)(5 6)(7)
Strongly connected components: (Andy Bart Carl)(Dave Earl)(Fred Gary)(Hank)
Last updated