Kosaraju: Difference between revisions

Content added Content deleted

Inline

@@ Line 343: / Line 343: @@
 =={{header|Perl 6}}==
 {{works with|Rakudo|2018.09}}
-{{trans|Python}}{{trans|Kotlin}}
+Inspired by Python & Kotlin entries.
+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) {
+<lang perl6>sub kosaraju (%k) {
+    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 |@g[$u] -> $v {
+            for |%k{$u} -> $v {
                 visit($v);
-                @transpose[$v].push: $u;
+                @transpose[%g{$v}].push: $u;
             }
-            @stack.unshift: $u;
+            @stack.push: $u;
         }
     }
     sub assign ($u, $root) {
         if %visited{$u} {
             %visited{$u}   = False;
-            @connected[$u] = $root;
+            @connected[%g{$u}] = $root;
-            assign($_, $root) for |@transpose[$u];
+            assign($_, $root) for |@transpose[%g{$u}];
         }
     }
+    .&visit for %g.keys;
+    assign($_, $_) for @stack.reverse;
+    (|%g{@connected}).pairs.categorize( *.value, :as(*.key) ).values.map: { %h{|$_} };
-    .&visit for ^@g;
-    assign($_, $_) for @stack;
-    @connected
 }
+# TESTING
-my @verticies = (1),(2),(0),(1,2,4),(3,5),(2,6),(5),(4,6,7);
-my @connected = kosaraju @verticies;
-my %scc;
-@connected.antipairs.map: { %scc{$_.key}.push: $_.value }
+-> $test { say "\nStrongly connected components: ", |kosaraju($test).sort } for
-say '              Connected graph: ', @connected;
-say 'Strongly connected components: ', |%scc.sort».values».Slip</lang>
+# Same test data as all other entries, converted to a hash of lists
+(((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>
-<pre>              Connected graph: [0 0 0 3 3 5 5 7]
-Strongly connected components: [0 1 2][3 4][5 6][7]</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|Python}}==