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

Tarjan's algorithm is an algorithm in graph theory for finding the strongly connected components of a graph.

It runs in linear time, matching the time bound for alternative methods including Kosaraju's algorithm and the path-based strong component algorithm.

Tarjan's Algorithm is named for its discoverer, Robert Tarjan.

References

* The article on Wikipedia.

See also: Kosaraju
assistant
(formerly Perl 6)

**Works with**: Rakudo version 2018.09

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