user
|  |
| --- |
| This page uses content from **Wikipedia**. The original article was at Graph. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance) |

Kosaraju's algorithm (also known as the Kosaraju–Sharir algorithm) is a linear time algorithm to find the strongly connected components of a directed graph. Aho, Hopcroft and Ullman credit it to an unpublished paper from 1978 by S. Rao Kosaraju. The same algorithm was independently discovered by Micha Sharir and published by him in 1981. It makes use of the fact that the transpose graph (the same graph with the direction of every edge reversed) has exactly the same strongly connected components as the original graph.
  
For this task consider the directed graph with these connections:

```
 0 -> 1
 1 -> 2
 2 -> 0
 3 -> 1,  3 -> 2,  3 -> 4
 4 -> 3,  4 -> 5
 5 -> 2,  5 -> 6
 6 -> 5
 7 -> 4, 7  -> 6, 7 -> 7

```

And report the kosaraju strongly connected component for each node.

References

* The article on Wikipedia.
assistant
(formerly Perl 6)

**Works with**: Rakudo version 2018.09

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.

```
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 |%k{$u} -> $v {
                visit($v);
                @transpose[%g{$v}].push: $u;
            }
            @stack.push: $u;
        }
    }
 
    sub assign ($u, $root) {
        if %visited{$u} {
            %visited{$u}   = False;
            @connected[%g{$u}] = $root;
            assign($_, $root) for |@transpose[%g{$u}];
        }
    }
 
    .&visit for %g.keys;
    assign($_, $_) for @stack.reverse;

    (|%g{@connected}).pairs.categorize( *.value, :as(*.key) ).values.map: { %h{|$_} };
}

# TESTING

-> $test { say "\nStrongly connected components: ", |kosaraju($test).sort } for

# 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>)
)

```

Output:

```
Strongly connected components: (0 1 2)(3 4)(5 6)(7)

Strongly connected components: (Andy Bart Carl)(Dave Earl)(Fred Gary)(Hank)
```