Kosaraju: Difference between revisions
→{{header|Perl 6}}: Updated to be able to use named vertices instead of limiting to consecutive positive integer vertices
Thundergnat (talk | contribs) (→{{header|Perl 6}}: Add a Perl 6 example) |
Thundergnat (talk | contribs) (→{{header|Perl 6}}: Updated to be able to use named vertices instead of limiting to consecutive positive integer vertices) |
||
Line 343:
=={{header|Perl 6}}==
{{works with|Rakudo|2018.09}}
Accepts a hash of lists/arrays holding the vertex (name => (neighbors)) pairs. No longer limited to continuous, positive, integer vertex names.
<lang perl6>sub kosaraju (*@g) {▼
my %g = %k.keys.sort Z=> flat ^%k;
my %h = %g.invert;
my %visited;
my @stack;
my @transpose;
my @connected;
sub visit ($u) {
unless %visited{$u} {
%visited{$u} = True;
for |
visit($v);
@transpose[%g{$v}].push: $u;
}
@stack.
}
}
sub assign ($u, $root) {
if %visited{$u} {
%visited{$u} = False;
@connected[%g{$u}] = $root;
assign($_, $root) for |@transpose[%g{$u}];
}
}
assign($_, $_) for @stack.reverse;▼
(|%g{@connected}).pairs.categorize( *.value, :as(*.key) ).values.map: { %h{|$_} };
▲ .&visit for ^@g;
▲ assign($_, $_) for @stack;
}
# TESTING
my @verticies = (1),(2),(0),(1,2,4),(3,5),(2,6),(5),(4,6,7);▼
-> $test { say "\nStrongly connected components: ", |kosaraju($test).sort } for
# Same test data as all other entries, converted to a hash of lists
# 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:
Strongly connected components: (Andy Bart Carl)(Dave Earl)(Fred Gary)(Hank)</pre>
=={{header|Python}}==
| |||