Tarjan

From Rosetta Code
Tarjan is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
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

C#[edit]

using System;
using System.Collections.Generic;
 
class Node
{
public int LowLink { get; set; }
public int Index { get; set; }
public int N { get; }
 
public Node(int n)
{
N = n;
Index = -1;
LowLink = 0;
}
}
 
class Graph
{
public HashSet<Node> V { get; }
public Dictionary<Node, HashSet<Node>> Adj { get; }
 
/// <summary>
/// Tarjan's strongly connected components algorithm
/// </summary>
public void Tarjan()
{
var index = 0; // number of nodes
var S = new Stack<Node>();
 
Action<Node> StrongConnect = null;
StrongConnect = (v) =>
{
// Set the depth index for v to the smallest unused index
v.Index = index;
v.LowLink = index;
 
index++;
S.Push(v);
 
// Consider successors of v
foreach (var w in Adj[v])
if (w.Index < 0)
{
// Successor w has not yet been visited; recurse on it
StrongConnect(w);
v.LowLink = Math.Min(v.LowLink, w.LowLink);
}
else if (S.Contains(w))
// Successor w is in stack S and hence in the current SCC
v.LowLink = Math.Min(v.LowLink, w.Index);
 
// If v is a root node, pop the stack and generate an SCC
if (v.LowLink == v.Index)
{
Console.Write("SCC: ");
 
Node w;
do
{
w = S.Pop();
Console.Write(w.N + " ");
} while (w != v);
 
Console.WriteLine();
}
};
 
foreach (var v in V)
if (v.Index < 0)
StrongConnect(v);
}
}

Go[edit]

package main
 
import (
"fmt"
"math/big"
)
 
// (same data as zkl example)
var g = [][]int{
0: {1},
2: {0},
5: {2, 6},
6: {5},
1: {2},
3: {1, 2, 4},
4: {5, 3},
7: {4, 7, 6},
}
 
func main() {
tarjan(g, func(c []int) { fmt.Println(c) })
}
 
// the function calls the emit argument for each component identified.
// each component is a list of nodes.
func tarjan(g [][]int, emit func([]int)) {
var indexed, stacked big.Int
index := make([]int, len(g))
lowlink := make([]int, len(g))
x := 0
var S []int
var sc func(int) bool
sc = func(n int) bool {
index[n] = x
indexed.SetBit(&indexed, n, 1)
lowlink[n] = x
x++
S = append(S, n)
stacked.SetBit(&stacked, n, 1)
for _, nb := range g[n] {
if indexed.Bit(nb) == 0 {
if !sc(nb) {
return false
}
if lowlink[nb] < lowlink[n] {
lowlink[n] = lowlink[nb]
}
} else if stacked.Bit(nb) == 1 {
if index[nb] < lowlink[n] {
lowlink[n] = index[nb]
}
}
}
if lowlink[n] == index[n] {
var c []int
for {
last := len(S) - 1
w := S[last]
S = S[:last]
stacked.SetBit(&stacked, w, 0)
c = append(c, w)
if w == n {
emit(c)
break
}
}
}
return true
}
for n := range g {
if indexed.Bit(n) == 0 && !sc(n) {
return
}
}
}
Output:
[2 1 0]
[6 5]
[4 3]
[7]

Kotlin[edit]

// version 1.1.3
 
import java.util.Stack
 
typealias Nodes = List<Node>
 
class Node(val n: Int) {
var index = -1 // -1 signifies undefined
var lowLink = -1
var onStack = false
 
override fun toString() = n.toString()
}
 
class DirectedGraph(val vs: Nodes, val es: Map<Node, Nodes>)
 
fun tarjan(g: DirectedGraph): List<Nodes> {
val sccs = mutableListOf<Nodes>()
var index = 0
val s = Stack<Node>()
 
fun strongConnect(v: Node) {
// Set the depth index for v to the smallest unused index
v.index = index
v.lowLink = index
index++
s.push(v)
v.onStack = true
 
// consider successors of v
for (w in g.es[v]!!) {
if (w.index < 0) {
// Successor w has not yet been visited; recurse on it
strongConnect(w)
v.lowLink = minOf(v.lowLink, w.lowLink)
}
else if (w.onStack) {
// Successor w is in stack s and hence in the current SCC
v.lowLink = minOf(v.lowLink, w.index)
}
}
 
// If v is a root node, pop the stack and generate an SCC
if (v.lowLink == v.index) {
val scc = mutableListOf<Node>()
do {
val w = s.pop()
w.onStack = false
scc.add(w)
}
while (w != v)
sccs.add(scc)
}
}
 
for (v in g.vs) if (v.index < 0) strongConnect(v)
return sccs
}
 
fun main(args: Array<String>) {
val vs = (0..7).map { Node(it) }
val es = mapOf(
vs[0] to listOf(vs[1]),
vs[2] to listOf(vs[0]),
vs[5] to listOf(vs[2], vs[6]),
vs[6] to listOf(vs[5]),
vs[1] to listOf(vs[2]),
vs[3] to listOf(vs[1], vs[2], vs[4]),
vs[4] to listOf(vs[5], vs[3]),
vs[7] to listOf(vs[4], vs[7], vs[6])
)
val g = DirectedGraph(vs, es)
val sccs = tarjan(g)
println(sccs.joinToString("\n"))
}
Output:
[2, 1, 0]
[6, 5]
[4, 3]
[7]

Perl[edit]

Translation of: Perl 6
use feature 'state';
use List::Util qw(min);
 
sub tarjan {
our(%k) = @_;
our(%onstack, %index, %lowlink, @stack);
our @connected = ();
 
sub strong_connect {
my($vertex) = @_;
state $index = 0;
$index{$vertex} = $index;
$lowlink{$vertex} = $index++;
push @stack, $vertex;
$onstack{$vertex} = 1;
for my $connection (@{$k{$vertex}}) {
if (not $index{$connection}) {
strong_connect($connection);
$lowlink{$vertex} = min($lowlink{$connection},$lowlink{$vertex});
} elsif ($onstack{$connection}) {
$lowlink{$vertex} = min($lowlink{$connection},$lowlink{$vertex});
}
}
if ($lowlink{$vertex} eq $index{$vertex}) {
my @node;
do {
push @node, pop @stack;
$onstack{$node[-1]} = 0;
} while $node[-1] ne $vertex;
push @connected, [@node];
}
}
 
for (sort keys %k) {
strong_connect($_) unless $index{$_}
}
@connected
}
 
my %test1 = (
0 => [1],
1 => [2],
2 => [0],
3 => [1, 2, 4],
4 => [3, 5],
5 => [2, 6],
6 => [5],
7 => [4, 6, 7]
);
 
my %test2 = (
'Andy' => ['Bart'],
'Bart' => ['Carl'],
'Carl' => ['Andy'],
'Dave' => [qw<Bart Carl Earl>],
'Earl' => [qw<Dave Fred>],
'Fred' => [qw<Carl Gary>],
'Gary' => ['Fred'],
'Hank' => [qw<Earl Gary Hank>]
);
 
print "Strongly connected components:\n";
print join(', ', sort @$_) . "\n" for tarjan(%test1);
print "\nStrongly connected components:\n";
print join(', ', sort @$_) . "\n" for tarjan(%test2);
Output:
Strongly connected components:
0, 1, 2
5, 6
3, 4
7

Strongly connected components:
Andy, Bart, Carl
Fred, Gary
Dave, Earl
Hank

Perl 6[edit]

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)

Phix[edit]

Translation of: Go

Same data as other examples, but with 1-based indexes.

constant g = {{2}, {3}, {1}, {2,3,5}, {6,4}, {3,7}, {6}, {5,8,7}}
 
sequence index, lowlink, stacked, stack
integer x
 
function strong_connect(integer n, r_emit)
index[n] = x
lowlink[n] = x
stacked[n] = 1
stack &= n
x += 1
for b=1 to length(g[n]) do
integer nb = g[n][b]
if index[nb] == 0 then
if not strong_connect(nb,r_emit) then
return false
end if
if lowlink[nb] < lowlink[n] then
lowlink[n] = lowlink[nb]
end if
elsif stacked[nb] == 1 then
if index[nb] < lowlink[n] then
lowlink[n] = index[nb]
end if
end if
end for
if lowlink[n] == index[n] then
sequence c = {}
while true do
integer w := stack[$]
stack = stack[1..$-1]
stacked[w] = 0
c = prepend(c, w)
if w == n then
call_proc(r_emit,{c})
exit
end if
end while
end if
return true
end function
 
procedure tarjan(sequence g, integer r_emit)
index = repeat(0,length(g))
lowlink = repeat(0,length(g))
stacked = repeat(0,length(g))
stack = {}
x := 1
for n=1 to length(g) do
if index[n] == 0
and not strong_connect(n,r_emit) then
return
end if
end for
end procedure
 
procedure emit(object c)
-- called for each component identified.
-- each component is a list of nodes.
 ?c
end procedure
 
tarjan(g,routine_id("emit"))
Output:
{1,2,3}
{6,7}
{4,5}
{8}

Sidef[edit]

Translation of: Perl 6
func tarjan (k) {
 
var(:onstack, :index, :lowlink, *stack, *connected)
 
func strong_connect (vertex, i=0) {
 
index{vertex} = i
lowlink{vertex} = i+1
onstack{vertex} = true
stack << vertex
 
for connection in (k{vertex}) {
if (index{connection} == nil) {
strong_connect(connection, i+1)
lowlink{vertex} `min!` lowlink{connection}
}
elsif (onstack{connection}) {
lowlink{vertex} `min!` index{connection}
}
}
 
if (lowlink{vertex} == index{vertex}) {
var *node
do {
node << stack.pop
onstack{node.tail} = false
} while (node.tail != vertex)
connected << node
}
}
 
{ strong_connect(_) if !index{_} } << k.keys
 
return connected
}
 
var tests = [
Hash(
0 => <1>,
1 => <2>,
2 => <0>,
3 => <1 2 4>,
4 => <3 5>,
5 => <2 6>,
6 => <5>,
7 => <4 6 7>,
),
Hash(
:Andy => <Bart>,
:Bart => <Carl>,
:Carl => <Andy>,
:Dave => <Bart Carl Earl>,
:Earl => <Dave Fred>,
:Fred => <Carl Gary>,
:Gary => <Fred>,
:Hank => <Earl Gary Hank>,
)
]
 
tests.each {|t|
say ("Strongly connected components: ", tarjan(t).map{.sort}.sort)
}
Output:
Strongly connected components: [["0", "1", "2"], ["3", "4"], ["5", "6"], ["7"]]
Strongly connected components: [["Andy", "Bart", "Carl"], ["Dave", "Earl"], ["Fred", "Gary"], ["Hank"]]

zkl[edit]

class Tarjan{
// input: graph G = (V, Es)
// output: set of strongly connected components (sets of vertices)
// Ick: class holds global state for strongConnect(), otherwise inert
const INDEX=0, LOW_LINK=1, ON_STACK=2;
fcn init(graph){
var index=0, stack=List(), components=List(),
G=List.createLong(graph.len(),0);
 
// convert graph to ( (index,lowlink,onStack),(id,links)), ...)
// sorted by id
foreach v in (graph){ G[v[0]]=T( L(Void,Void,False),v) }
 
foreach v in (G){ if(v[0][INDEX]==Void) strongConnect(v) }
 
println("List of strongly connected components:");
foreach c in (components){ println(c.reverse().concat(",")) }
 
returnClass(components); // over-ride return of class instance
}
fcn strongConnect(v){ // v is ( (index,lowlink,onStack), (id,links) )
// Set the depth index for v to the smallest unused index
v0:=v[0]; v0[INDEX]=v0[LOW_LINK]=index;
index+=1;
v0[ON_STACK]=True;
stack.push(v);
 
// Consider successors of v
foreach idx in (v[1][1,*]){ // links of v to other vs
w,w0 := G[idx],w[0]; // well, that is pretty vile
if(w[0][INDEX]==Void){
strongConnect(w); // Successor w not yet visited; recurse on it
v0[LOW_LINK]=v0[LOW_LINK].min(w0[LOW_LINK]);
}
else if(w0[ON_STACK])
// Successor w is in stack S and hence in the current SCC
v0[LOW_LINK]=v0[LOW_LINK].min(w0[INDEX]);
}
// If v is a root node, pop the stack and generate an SCC
if(v0[LOW_LINK]==v0[INDEX]){
strong:=List(); // start a new strongly connected component
do{
w,w0 := stack.pop(), w[0];
w0[ON_STACK]=False;
strong.append(w[1][0]); // add w to strongly connected component
}while(w.id!=v.id);
components.append(strong); // output strongly connected component
}
}
}
   // graph from https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
// with vertices id zero based (vs 1 based in article)
// ids start at zero and are consecutive (no holes), graph is unsorted
graph:= // ( (id, links/Edges), ...)
T( T(0,1), T(2,0), T(5,2,6), T(6,5),
T(1,2), T(3,1,2,4), T(4,5,3), T(7,4,7,6) );
Tarjan(graph);
Output:
0,1,2
5,6
3,4
7