Tarjan: Difference between revisions

{{wikipedia|Graph}}

[[Category:Algorithm]]

;References:

* The article on [[wp:Tarjan's_strongly_connected_components_algorithm|Wikipedia]].

 

=={{header|C sharp|C#}}==

using System.Collections.Generic;

 

class Node

{

}

 

class Graph

{

 

 

 

 

 

 

 

 

 

=={{header|Go}}==

 

import (

}

}

{{out}}

<pre>

</pre>

 

 

=={{header|Julia}}==

LightGraphs uses Tarjan's algorithm by default. The package can also use Kosaraju's algorithm with the function strongly_connected_components_kosaraju().

 

edge_list=[(1,2),(3,1),(6,3),(6,7),(7,6),(2,3),(4,2),(4,3),(4,5),(5,6),(5,4),(8,5),(8,8),(8,7)]

 

println("Results in the zero-base scheme: $(inzerobase(tarj))")

<pre>

Results in the zero-base scheme: Array{Int64,1}[[2, 1, 0], [6, 5], [4, 3], [7]]

</pre>

 

=={{header|Kotlin}}==

 

import java.util.Stack

typealias Nodes = List<Node>

 

var index = -1 // -1 signifies undefined

var lowLink = -1

var index = 0

val s = Stack<Node>()

// Set the depth index for v to the smallest unused index

v.index = index

v.lowLink = index

s.push(v)

// consider successors of v

for (w in g.es[v]!!) {

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 es = mapOf(

vs[0] to listOf(vs[1]),

val g = DirectedGraph(vs, es)

val sccs = tarjan(g)

 

{{out}}

[7]

</pre>

 

=={{header|Perl}}==

use List::Util qw(min);

 

sub tarjan {

print join(', ', sort @$_) . "\n" for tarjan(%test1);

print "\nStrongly connected components:\n";

{{out}}

<pre>Strongly connected components:

Dave, Earl

Hank</pre>

 

=={{header|Phix}}==

{{trans|Go}}

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

{{out}}

<pre>

 

=={{header|Python}}==

 

def from_edges(edges):

for g in trajan(from_edges(table)):

print(g)

{{out}}

<pre>[6, 7]

['A', 'B', 'C']

</pre>

 

=={{header|Racket}}==

{{trans|Kotlin}}

 

 

(require syntax/parse/define

(define store (make-hash))

(define (make-node v) (hash-ref! store v (thunk (node v #f #f #f))))

;; it's important that we use hasheq instead of hash so that we compare

;; reference instead of actual value. Had we use the actual value,

[3 1 2 4]

[4 5 3]

 

{{out}}

=== With the graph library ===

 

 

(require graph)

[7 4 7 6])))

 

 

{{out}}

<pre>

'((7) (3 4) (5 6) (1 0 2))

</pre>

 

=={{header|Sidef}}==

 

var(:onstack, :index, :lowlink, *stack, *connected)

tests.each {|t|

say ("Strongly connected components: ", tarjan(t).map{.sort}.sort)

{{out}}

<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|zkl}}==

// input: graph G = (V, Es)

// output: set of strongly connected components (sets of vertices)

const INDEX=0, LOW_LINK=1, ON_STACK=2;

fcn init(graph){

G=List.createLong(graph.len(),0);

 

foreach c in (components){ println(c.reverse().concat(",")) }

 

}

fcn strongConnect(v){ // v is ( (index,lowlink,onStack), (id,links) )

// Consider successors of v

foreach idx in (v[1][1,*]){ // links of v to other vs

}

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

}

}

// with vertices id zero based (vs 1 based in article)

// ids start at zero and are consecutive (no holes), graph is unsorted

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

{{out}}

<pre>