Tarjan: Difference between revisions
m
syntax highlighting fixup automation
m (→{{header|Phix}}: syntax coloured) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 18:
{{trans|Python: As class}}
<
String name
[Char = [Char]] graph
Line 97:
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 ‘’)
print("\n SCC's of "(g.name‘:’)‘ ’scc)</
{{out}}
Line 149:
=={{header|C|C}}==
<
#include <stdlib.h>
#include <stdbool.h>
Line 315:
return tj.head;
}
</syntaxhighlight>
=={{header|C sharp|C#}}==
<
using System.Collections.Generic;
Line 390:
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
Line 529:
print_vector(s);
return 0;
}</
{{out}}
Line 540:
=={{header|Go}}==
<
import (
Line 614:
}
}
}</
{{out}}
<pre>
Line 633:
* the output of `tarjan` is an array each item of which is an array of Node ids.
<br>
<
def Node:
{ n: .,
Line 715:
{ vs: vs, es: es }
| tarjan</
{{out}}
<pre>
Line 723:
=={{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)]
Line 734:
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]]
Line 740:
=={{header|Kotlin}}==
<
import java.util.Stack
Line 814:
val sccs = tarjan(g)
println(sccs.joinToString("\n"))
}</
{{out}}
Line 826:
=={{header|Nim}}==
{{trans|Kotlin}}
<
type
Line 905:
var g = DirectedGraph(nodes: vs, edges: es)
let sccs = g.tarjan()
echo sccs.join("\n")</
{{out}}
Line 915:
=={{header|Perl}}==
{{trans|Raku}}
<
use warnings;
use feature <say state current_sub>;
Line 980:
print join(', ', sort @$_) . "\n" for tarjan(%test1);
print "\nStrongly connected components:\n";
print join(', ', sort @$_) . "\n" for tarjan(%test2);</
{{out}}
<pre>Strongly connected components:
Line 997:
{{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>
Line 1,062:
<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>
Line 1,074:
===Python: As function===
<
def from_edges(edges):
Line 1,130:
for g in trajan(from_edges(table)):
print(g)
print()</
{{out}}
<pre>[6, 7]
Line 1,229:
;Code:
<
Line 1,313:
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]
print("\n SCC's of", g.name + ':', scc)</
{{out}}
Line 1,367:
{{trans|Kotlin}}
<
(require syntax/parse/define
Line 1,428:
[3 1 2 4]
[4 5 3]
[7 4 7 6])))</
{{out}}
Line 1,438:
=== With the graph library ===
<
(require graph)
Line 1,451:
[7 4 7 6])))
(scc g)</
{{out}}
Line 1,462:
{{works with|Rakudo|2018.09}}
<syntaxhighlight lang="raku"
my %onstack;
my %index;
Line 1,515:
:Gary<Fred>,
:Hank<Earl Gary Hank>
)</
{{out}}
<pre>
Line 1,523:
=={{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]'
Line 1,610:
End
Say ol
Return</
{{out}}
<pre>[0 1 2]
Line 1,618:
=={{header|Rust}}==
<
// Using a naked BTreeMap would not be very nice, so let's make a simple graph representation
Line 1,775:
println!("{:?}", component);
}
}</
{{out}}
Line 1,787:
=={{header|Sidef}}==
{{trans|Raku}}
<
var(:onstack, :index, :lowlink, *stack, *connected)
Line 1,848:
tests.each {|t|
say ("Strongly connected components: ", tarjan(t).map{.sort}.sort)
}</
{{out}}
<pre>
Line 1,859:
{{libheader|Wren-seq}}
{{libheader|Wren-dynamic}}
<
import "/dynamic" for Tuple
Line 1,939:
var g = DirectedGraph.new(vs, es)
var sccs = tarjan.call(g)
System.print(sccs.join("\n"))</
{{out}}
Line 1,950:
=={{header|zkl}}==
<
// input: graph G = (V, Es)
// output: set of strongly connected components (sets of vertices)
Line 1,999:
}
}
}</
<
// with vertices id zero based (vs 1 based in article)
// ids start at zero and are consecutive (no holes), graph is unsorted
Line 2,006:
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);</
{{out}}
<pre>
| |||