Tarjan: Difference between revisions

{{trans|Python: As class}}

String name

[Char = [Char]] graph

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>

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

<br>

def Node:

{ n: .,

{ vs: vs, es: es }

{{out}}

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

=={{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.

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">constant</span> <span style="color: #000000;">g</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">6</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">}}</span>

<span style="color: #000000;">tarjan</span><span style="color: #0000FF;">(</span><span style="color: #000000;">g</span><span style="color: #0000FF;">,</span><span style="color: #000000;">emit</span><span style="color: #0000FF;">)</span>

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

import "/dynamic" for Tuple

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>