Kosaraju: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
m (→{{header|Wren}}: Changed to Wren S/H) |
|||
(19 intermediate revisions by 7 users not shown) | |||
Line 4:
<br>
Kosaraju's algorithm (also known as the Kosaraju–Sharir algorithm) is a linear time algorithm to find the strongly connected components of a directed graph. Aho, Hopcroft and Ullman credit it to an unpublished paper from 1978 by S. Rao Kosaraju. The same algorithm was independently discovered by Micha Sharir and published by him in 1981. It makes use of the fact that the transpose graph (the same graph with the direction of every edge reversed) has exactly the same strongly connected components as the original graph.
<br>
For this task consider the directed graph with these connections:
0 -> 1
1 -> 2
2 -> 0
3 -> 1, 3 -> 2, 3 -> 4
4 -> 3, 4 -> 5
5 -> 2, 5 -> 6
6 -> 5
7 -> 4, 7 -> 6, 7 -> 7
And report the kosaraju strongly connected component for each node.
<br>
;References:
Line 11 ⟶ 23:
{{trans|Python}}
<
V size = g.len
V vis = [0B] * size
Line 43 ⟶ 55:
V g = [[1], [2], [0], [1, 2, 4], [3, 5], [2, 6], [5], [4, 6, 7]]
print(kosaraju(g))</
{{out}}
Line 51 ⟶ 63:
=={{header|C sharp|C#}}==
<
using System.Collections.Generic;
Line 122 ⟶ 134:
Assign(u, u);
}
}</
=={{header|C++}}==
{{trans|D}}
<
#include <iostream>
#include <ostream>
Line 212 ⟶ 224:
return 0;
}</
{{out}}
<pre>[0, 0, 0, 3, 3, 5, 5, 7]</pre>
Line 218 ⟶ 230:
=={{header|D}}==
{{trans|Kotlin}} (mostly) with output like {{trans|Go}}
<
import std.stdio;
Line 284 ⟶ 296:
void main() {
writeln(kosaraju(g));
}</
{{out}}
<pre>[0, 0, 0, 3, 3, 5, 5, 7]</pre>
=={{header|Delphi}}==
{{libheader| System.SysUtils}}
{{Trans|Go}}
<syntaxhighlight lang="delphi">
program KosarajuApp;
uses
System.SysUtils;
type
TKosaraju = TArray<TArray<Integer>>;
var
g: TKosaraju;
procedure Init();
begin
SetLength(g, 8);
g[0] := [1];
g[1] := [2];
g[2] := [0];
g[3] := [1, 2, 4];
g[4] := [3, 5];
g[5] := [2, 6];
g[6] := [5];
g[7] := [4, 6, 7];
end;
procedure Println(vector: TArray<Integer>);
var
i: Integer;
begin
write('[');
if (Length(vector) > 0) then
for i := 0 to High(vector) do
begin
write(vector[i]);
if (i < high(vector)) then
write(', ');
end;
writeln(']');
end;
function Kosaraju(g: TKosaraju): TArray<Integer>;
var
vis: TArray<Boolean>;
L, c: TArray<Integer>;
x: Integer;
t: TArray<TArray<Integer>>;
Visit: TProc<Integer>;
u: Integer;
Assign: TProc<Integer, Integer>;
begin
// 1. For each vertex u of the graph, mark u as unvisited. Let L be empty.
SetLength(vis, Length(g));
SetLength(L, Length(g));
x := Length(L);
// index for filling L in reverse order
SetLength(t, Length(g)); // transpose graph
// 2. recursive subroutine:
Visit := procedure(u: Integer)
begin
if (not vis[u]) then
begin
vis[u] := true;
for var v in g[u] do
begin
Visit(v);
t[v] := concat(t[v], [u]);
// construct transpose
end;
dec(x);
L[x] := u;
end;
end;
// 2. For each vertex u of the graph do Visit(u)
for u := 0 to High(g) do
begin
Visit(u);
end;
SetLength(c, Length(g)); // result, the component assignment
// 3: recursive subroutine:
Assign := procedure(u, root: Integer)
begin
if vis[u] then
// repurpose vis to mean "unassigned"
begin
vis[u] := false;
c[u] := root;
for var v in t[u] do
Assign(v, root);
end;
end;
// 3: For each element u of L in order, do Assign(u,u)
for u in L do
Assign(u, u);
Result := c;
end;
begin
Init;
Println(Kosaraju(g));
end.</syntaxhighlight>
{{out}}
<pre>[0, 0, 0, 3, 3, 5, 5, 7]</pre>
=={{header|Go}}==
<
import "fmt"
Line 348 ⟶ 478:
}
return c
}</
{{out}}
<pre>
[0 0 0 3 3 5 5 7]
</pre>
=={{header|J}}==
Implementation:
<syntaxhighlight lang="j">kosaraju=: {{
coerase([cocurrent)cocreate''
visit=: {{
if.y{unvisited do.
unvisited=: 0 y} unvisited
visit y{::out
L=: y,L
end.
}}"0
assign=: {{
if._1=y{assigned do.
assigned=: x y} assigned
x&assign y{::in
end.
}}"0
out=: y
in=: <@I.|:y e.S:0~i.#y
unvisited=: 1#~#y
assigned=: _1#~#y
L=: i.0
visit"0 i.#y
assign~L
assigned
}}</syntaxhighlight>
Task example (tree representation: each value here is the index of the parent node):
<syntaxhighlight lang="j"> kosaraju 1;2;0;1 2 4;3 5;2 6;5;4 6 7
0 0 0 3 3 5 5 7</syntaxhighlight>
Alternatively, we could represent the result as a graph of the same type as our argument graph. The implementation of <tt>visit</tt> remains the same:
<syntaxhighlight lang="j">kosarajud=: {{
coerase([cocurrent)cocreate''
visit=: {{
if.y{unvisited do.
unvisited=: 0 y} unvisited
visit y{::out
L=: y,L
end.
}}"0
assign=: {{
if.-.y e.;assigned do.
assigned=: (y,L:0~x{assigned) x} assigned
x&assign y{::in
end.
}}"0
out=: y
in=: <@I.|:y e.S:0~i.#y
unvisited=: 1#~#y
assigned=: a:#~#y
L=: i.0
visit"0 i.#y
assign~L
assigned
}}
kosarajud 1;2;0;1 2 4;3 5;2 6;5;4 6 7
┌─────┬┬┬───┬┬───┬┬─┐
│0 2 1│││3 4││5 6││7│
└─────┴┴┴───┴┴───┴┴─┘
</syntaxhighlight>
But it would probably be simpler to convert the result from the tree representation to our directed graph representation:
<syntaxhighlight lang="j"> ((<@I.@e."1 0)i.@#) 0 0 0 3 3 5 5 7
┌─────┬┬┬───┬┬───┬┬─┐
│0 1 2│││3 4││5 6││7│
└─────┴┴┴───┴┴───┴┴─┘</syntaxhighlight>
=={{header|Java}}==
{{trans|Kotlin}}
Output is like Go instead of what Kotlin outputs.
<
import java.util.Arrays;
import java.util.List;
Line 443 ⟶ 646:
System.out.println(output);
}
}</
{{out}}
<pre>[0, 0, 0, 3, 3, 5, 5, 7]</pre>
Line 449 ⟶ 652:
=={{header|jq}}==
{{trans|Go}}
<syntaxhighlight lang="jq">
# Fill an array of the specified length with the input value
def dimension($n): . as $in | [range(0;$n) | $in];
Line 507 ⟶ 710:
];
korasaju(g)</
{{out}}
With the jq program above in korasaju.jq, the invocation `jq -nc -f korasaju.jq` produces:
<syntaxhighlight lang="sh">
[0,0,0,3,3,5,5,7]
</syntaxhighlight>
=={{header|Julia}}==
Line 518 ⟶ 721:
{{trans|Go}}
<
# 1. For each vertex u of the graph, mark u as unvisited. Let L be empty.
vis = falses(length(g))
Line 560 ⟶ 763:
g = [[2], [3], [1], [2, 3, 5], [4, 6], [3, 7], [6], [5, 7, 8]]
println(korasaju(g))</
{{out}}
<pre>[1, 1, 1, 4, 4, 6, 6, 8]</pre>
=={{header|K}}==
{{works with|ngn/k}}
<syntaxhighlight lang=K>F:{[g] / graph
n: #g / number of vertices
v::&n / visited?
L::!0 / dfs order
V: {[g;x] $[v x;;[v[x]:1;o[g]'g x;L::x,L]];}[g]
V'!n / Visit
G: @[n#,!0;g;,;!n] / transposed graph
c::n#-1 / assigned components
A: {[G;x;y] $[-1=c x;[c[x]:y;G[x]o[G]'y];]}[G]'
A'/2#,L / Assign
.=c}</syntaxhighlight>
<syntaxhighlight lang=K> F(1;2;0;1 2 4;3 5;2 6;5;4 6 7)
(0 1 2
3 4
5 6
,7)</syntaxhighlight>
Alternative implementation, without global assignments:
<syntaxhighlight lang=K>F:{[g] /graph
n:#g /number of vertices
G:@[n#,!0;g;,;!n] /transposed graph
V:{[g;L;x]$[^L?x;(1_(x,L)o[g]/g x),x;L]}[g]
L:|V/[!0;!#g] /Visit
A:{[G;c;u;r]$[0>c u;o[G]/[@[c;u;:;r];G u;r];c]}[G]
.=A/[n#-1;L;L]} /Assign</syntaxhighlight>
(result is the same)
{{works with|Kona}}<syntaxhighlight lang=K>F:{[g] / graph
n: #g / number of vertices
v::&n / visited?
L::!0 / dfs order
V: {[g;x] :[v x;;[v[x]:1;_f[g]'g x;L::x,L]];}[g]
V'!n / Visit
G: @[n#,!0;g;,;!n] / transposed graph
c::n#-1 / assigned components
A: {[G;x;y] :[-1=c x;[c[x]:y;G[x]_f[G]'y];]}[G]'
A'/2#,L / Assign
.=c}</syntaxhighlight>
(result is the same)
=={{header|Kotlin}}==
{{trans|Go}}
<
/* the list index is the first vertex in the edge(s) */
Line 625 ⟶ 873:
fun main(args: Array<String>) {
println(kosaraju(g).joinToString("\n"))
}</
{{out}}
Line 637 ⟶ 885:
=={{header|Lua}}==
{{trans|C++}}
<
io.write("[")
for i=0,#a do
Line 731 ⟶ 979:
write_array(kosaraju(g))
print()</
{{out}}
<pre>[0, 0, 0, 3, 3, 5, 5, 7]</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">g = Graph[{0 -> 1, 1 -> 2, 2 -> 0, 3 -> 1, 3 -> 2, 3 -> 4, 4 -> 3,
4 -> 5, 5 -> 2, 5 -> 6, 6 -> 5, 7 -> 4, 7 -> 6, 7 -> 7}];
cc = ConnectedComponents[g]
Catenate[ConstantArray[Min[#], Length[#]] & /@ SortBy[cc, First]]</syntaxhighlight>
{{out}}
<pre>{{0, 1, 2}, {5, 6}, {3, 4}, {7}}
{0, 0, 0, 3, 3, 5, 5, 7}</pre>
=={{header|Nim}}==
{{trans|Kotlin}}
<
Vertex = int
Graph = seq[seq[Vertex]]
Line 782 ⟶ 1,039:
when isMainModule:
let g = @[@[1], @[2], @[0], @[1, 2, 4], @[3, 5], @[2, 6], @[5], @[4, 6, 7]]
for scc in korasaju(g): echo $scc</
{{out}}
Line 789 ⟶ 1,046:
@[5, 6]
@[7]</pre>
=={{header|Pascal}}==
Works with FPC (tested with version 3.2.2).
<syntaxhighlight lang="pascal">
program Kosaraju_SCC;
{$mode objfpc}{$modeswitch arrayoperators}
{$j-}{$coperators on}
type
TDigraph = array of array of Integer;
procedure PrintComponents(const g: TDigraph);
var
Visited: array of Boolean = nil;
RevPostOrder: array of Integer = nil;
gr: TDigraph = nil; //reversed graph
Counter, Next: Integer;
FirstItem: Boolean;
procedure Dfs1(aNode: Integer);
begin
Visited[aNode] := True;
for Next in g[aNode] do begin
gr[Next] += [aNode];
if not Visited[Next] then
Dfs1(Next);
end;
RevPostOrder[Counter] := aNode;
Dec(Counter);
end;
procedure Dfs2(aNode: Integer);
begin
Visited[aNode] := True;
for Next in gr[aNode] do
if not Visited[Next] then
Dfs2(Next);
if FirstItem then begin
FirstItem := False;
Write(aNode);
end else
Write(', ', aNode);
end;
var
Node: Integer;
begin
SetLength(Visited, Length(g));
SetLength(RevPostOrder, Length(g));
SetLength(gr, Length(g));
Counter := High(g);
for Node := 0 to High(g) do
if not Visited[Node] then
Dfs1(Node);
FillChar(Pointer(Visited)^, Length(Visited), 0);
for Node in RevPostOrder do
if not Visited[Node] then begin
FirstItem := True;
Write('[');
Dfs2(Node);
WriteLn(']');
end;
end;
const
g: TDigraph = (
(1),
(2),
(0),
(1, 2, 4),
(3, 5),
(2, 6),
(5),
(4, 6, 7)
);
begin
PrintComponents(g);
end.
</syntaxhighlight>
{{out}}
<pre>
[7]
[4, 3]
[6, 5]
[1, 2, 0]
</pre>
=={{header|Perl}}==
{{trans|Raku}}
<
use warnings;
use feature 'say';
Line 861 ⟶ 1,203:
kosaraju(%test1);
say '';
kosaraju(%test2);</
{{out}}
<pre>0 1 2
Line 874 ⟶ 1,216:
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">visited</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">c</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">visit</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">g</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">u</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">visited</span><span style="color: #0000FF;">[</span><span style="color: #000000;">u</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">visited</span><span style="color: #0000FF;">[</span><span style="color: #000000;">u</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">g</span><span style="color: #0000FF;">[</span><span style="color: #000000;">u</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">v</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">g</span><span style="color: #0000FF;">[</span><span style="color: #000000;">u</span><span style="color: #0000FF;">][</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">visit</span><span style="color: #0000FF;">(</span><span style="color: #000000;">g</span><span style="color: #0000FF;">,</span><span style="color: #000000;">v</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">v</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">v</span><span style="color: #0000FF;">])</span> <span style="color: #0000FF;">&</span> <span style="color: #000000;">u</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">l</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">u</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">assign</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">u</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">root</span><span style="color: #0000FF;">=</span><span style="color: #000000;">u</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">visited</span><span style="color: #0000FF;">[</span><span style="color: #000000;">u</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">visited</span><span style="color: #0000FF;">[</span><span style="color: #000000;">u</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
<span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">u</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">root</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">v</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">u</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">assign</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">u</span><span style="color: #0000FF;">][</span><span style="color: #000000;">v</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">root</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">korasaju</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">g</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">len</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">g</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">visited</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #000000;">len</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">({},</span><span style="color: #000000;">len</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">u</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">len</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">visit</span><span style="color: #0000FF;">(</span><span style="color: #000000;">g</span><span style="color: #0000FF;">,</span><span style="color: #000000;">u</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">len</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">u</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">assign</span><span style="color: #0000FF;">(</span><span style="color: #000000;">l</span><span style="color: #0000FF;">[</span><span style="color: #000000;">u</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">c</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</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;">4</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;">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;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">}}</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">korasaju</span><span style="color: #0000FF;">(</span><span style="color: #000000;">g</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 921 ⟶ 1,267:
=={{header|Python}}==
Works with Python 2
<syntaxhighlight lang="python">def kosaraju(g):
class nonlocal: pass
Line 960 ⟶ 1,307:
g = [[1], [2], [0], [1,2,4], [3,5], [2,6], [5], [4,6,7]]
print kosaraju(g)</
{{out}}
<pre>[0, 0, 0, 3, 3, 5, 5, 7]</pre>
Syntax requirements have changed. This version works with Python 3.
<syntaxhighlight lang="python3">def kosaraju(g):
size = len(g)
vis = [False] * size
l = [0] * size
x = size
t = [[] for _ in range(size)]
def visit(u):
nonlocal x
if not vis[u]:
vis[u] = True
for v in g[u]:
visit(v)
t[v].append(u)
x -= 1
l[x] = u
for u in range(size):
visit(u)
c = [0] * size
def assign(u, root):
if vis[u]:
vis[u] = False
c[u] = root
for v in t[u]:
assign(v, root)
for u in l:
assign(u, u)
return c
g = [[1], [2], [0], [1, 2, 4], [3, 5], [2, 6], [5], [4, 6, 7]]
print(kosaraju(g))</syntaxhighlight>
{{out}}
<pre>[0, 0, 0, 3, 3, 5, 5, 7]</pre>
=={{header|Racket}}==
<
(require racket/dict)
Line 997 ⟶ 1,386:
(3 1 2 4) ; equvalent to (3 . (1 2 4))
(4 5 3)
(7 4 7 6))))</
{{out}}
Line 1,010 ⟶ 1,399:
Accepts a hash of lists/arrays holding the vertex (name => (neighbors)) pairs. No longer limited to continuous, positive, integer vertex names.
<syntaxhighlight lang="raku"
my %g = %k.keys.sort Z=> flat ^%k;
my %h = %g.invert;
Line 1,060 ⟶ 1,449:
:Gary<Fred>,
:Hank<Earl Gary Hank>)
)</
{{out}}
<pre>
Line 1,069 ⟶ 1,458:
=={{header|Sidef}}==
{{trans|Julia}}
<
# 1. For each vertex u of the graph, mark u as unvisited. Let L be empty.
var vis = g.len.of(false)
Line 1,115 ⟶ 1,504:
var g = [[1], [2], [0], [1, 2, 4], [3, 5], [2, 6], [5], [4, 6, 7]]
say korasaju(g)</
{{out}}
<pre>
Line 1,122 ⟶ 1,511:
=={{header|Standard ML}}==
<
fun node x = Node (x, ref false, ref nil, ref nil)
Line 1,197 ⟶ 1,586:
val ns = make (16, is, ijs)
val xs = kosaraju ns</
{{out}}
<pre>
Line 1,208 ⟶ 1,597:
{{trans|D}}
<
let size = graph.count
var x = size
Line 1,267 ⟶ 1,656:
]
print(kosaraju(graph: graph))</
{{out}}
Line 1,275 ⟶ 1,664:
=={{header|Visual Basic .NET}}==
{{trans|Java}}
<
Function Kosaraju(g As List(Of List(Of Integer))) As List(Of Integer)
Line 1,338 ⟶ 1,727:
End Sub
End Module</
{{out}}
<pre>[0, 0, 0, 3, 3, 5, 5, 7]</pre>
Line 1,344 ⟶ 1,733:
=={{header|Wren}}==
{{trans|Go}}
<
var gc = g.count
// 1. For each vertex u of the graph, mark u as unvisited. Let l be empty.
Line 1,381 ⟶ 1,770:
var g = [ [1], [2], [0], [1, 2, 4], [3, 5], [2, 6], [5], [4, 6, 7] ]
System.print(kosaraju.call(g))</
{{out}}
Line 1,389 ⟶ 1,778:
=={{header|zkl}}==
<
fcn visit(u,G,L){ // u is ((visited,assigned), (id,edges))
Line 1,429 ⟶ 1,818:
return(components);
}</
<
// with vertices id zero based (vs 1 based in article)
// ids start at zero and are consecutive (no holes), graph is unsorted
Line 1,436 ⟶ 1,825:
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) );
kosaraju(graph);</
{{out}}
<pre>
|