perl6 implementation of Tarjan algorithm
Switch branches/tags
Nothing to show
Clone or download
Latest commit c277e1f Oct 22, 2018
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.precomp rm tmp files Oct 22, 2018
lib/Algorithm rm tmp files Oct 22, 2018
logotype change logo name Jun 4, 2016
t put space after comma in list Oct 22, 2018
.gitignore new gitignore Oct 22, 2018
.travis.yml using example from travis web site May 25, 2017
LICENSE Initial commit May 26, 2016
META6.json typo May 28, 2016
README.md Update README.md Jun 4, 2016

README.md

p6-Algorithm-Tarjan

A perl6 implementation of Tarjan's algorithm for finding strongly connected components in a directed graph.

More information can be found at wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm.

If there is a cycle, then it will be within a strongly connected component. This implies that the absence of strongly connected components (other than a node with itself) means there are no cycles. It is possible there may be no cycles, but a strongly connected component may still exist (if I have interpreted the theory correctly). I was interested in the absence of cycles.

use Algorithm::Tarjan;

my Algorithm::Tarjan $a .= new();

my %h;
# code to fill %h node->[successor nodes]

$a.init(%h);
say 'There are ' ~ $a.find-cycles() ~ ' cycle(s) in the input graph';

If there is a need for the sets of strongly connected components, they can be retrieved from $a.strongly-connected (an array of node names).