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|C++}}==

// C++ implementation of Tarjan's strongly connected components algorithm

// See https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

auto gary = g.add_vertex("Gary");

auto hank = g.add_vertex("Hank");

andy->add_neighbour(bart);

bart->add_neighbour(carl);

gary->add_neighbour(fred);

hank->add_neighbours({earl, gary, hank});

tarjan<std::string> t;

for (auto&& s : t.run(g))

print_vector(s);

return 0;

 

{{out}}

 

=={{header|Go}}==

 

import (

}

}

{{out}}

<pre>

[4 3]

[7]

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

{{trans|Raku}}

use List::Util qw(min);

 

sub tarjan {

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

print "\nStrongly connected components:\n";

{{out}}

<pre>Strongly connected components:

{{trans|Go}}

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

{{out}}

<pre>

 

===Python: As function===

 

def from_edges(edges):

for g in trajan(from_edges(table)):

print(g)

{{out}}

<pre>[6, 7]

 

;Code:

 

 

self.name = name

self.connections = connections

g = defaultdict(list) # map node vertex to direct connections

for n1, n2 in connections:

print(" LOW of", g.name + ':', [v for _, v in sorted(g._low.items())])

scc = repr(g.scc if g.scc else '').replace("'", '').replace(',', '')[1:-1]

 

{{out}}

{{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}}

{{works with|Rakudo|2018.09}}

 

my %onstack;

my %index;

:Gary<Fred>,

:Hank<Earl Gary Hank>

{{out}}

<pre>

 

=={{header|REXX}}==

/* Vertices are numbered 1 to 8 (instead of 0 to 7) */

g='[2] [3] [1] [2 3 5] [4 6] [3 7] [6] [5 7 8]'

End

Say ol

{{out}}

<pre>[0 1 2]

[3 4]

[7]</pre>

 

=={{header|Sidef}}==

{{trans|Raku}}

 

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>