Tarjan: Difference between revisions

;References:

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

<br><br>

 

{{trans|Python: As class}}

 

String name

[Char = [Char]] graph

.tarjan_algo()

 

‘

Recursive function that finds SCC's

print(‘ LOW of ’(g.name‘:’)‘ ’sorted(g.low.items()).map((_, v) -> v))

V scc = (I !g.scc.empty {String(g.scc).replace(‘'’, ‘’).replace(‘,’, ‘’)[1 .< (len)-1]} E ‘’)

 

{{out}}

 

=={{header|C|C}}==

#include <stdlib.h>

#include <stdbool.h>

return tj.head;

}

 

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

using System.Collections.Generic;

 

StrongConnect(v);

}

 

=={{header|C++}}==

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

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

print_vector(s);

return 0;

 

{{out}}

 

=={{header|Go}}==

 

import (

}

}

{{out}}

<pre>

[4 3]

[7]

</pre>

 

* the output of `tarjan` is an array each item of which is an array of Node ids.

<br>

def Node:

{ n: .,

| if $wn == $vn then .stop = true else . end )

| .sccs += [.scc]

end

;

 

{ vs: vs, es: es }

{{out}}

<pre>

[[2,1,0],[6,5],[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

val sccs = tarjan(g)

println(sccs.joinToString("\n"))

 

{{out}}

=={{header|Nim}}==

{{trans|Kotlin}}

 

type

var g = DirectedGraph(nodes: vs, edges: es)

let sccs = g.tarjan()

 

{{out}}

=={{header|Perl}}==

{{trans|Raku}}

use warnings;

use feature <say state current_sub>;

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:

 

 

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

[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]

 

=={{header|Rust}}==

 

// Using a naked BTreeMap would not be very nice, so let's make a simple graph representation

println!("{:?}", component);

}

 

{{out}}

=={{header|Sidef}}==

{{trans|Raku}}

 

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

tests.each {|t|

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

{{out}}

<pre>

{{libheader|Wren-seq}}

{{libheader|Wren-dynamic}}

 

class Node {

var g = DirectedGraph.new(vs, es)

var sccs = tarjan.call(g)

 

{{out}}

 

=={{header|zkl}}==

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

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

}

}

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