Kosaraju: Difference between revisions
m
→{{header|11l}}: Void
Alextretyak (talk | contribs) m (→{{header|11l}}: Void) |
|||
| (15 intermediate revisions by 7 users not shown) | |||
Line 23:
{{trans|Python}}
<
V size = g.len
V vis = [0B] * size
Line 30:
V t = [[Int]()] * size
F visit(Int u) ->
I !@vis[u]
@vis[u] = 1B
Line 43:
V c = [0] * size
F assign(Int u, root) ->
I @vis[u]
@vis[u] = 0B
Line 55:
V g = [[1], [2], [0], [1, 2, 4], [3, 5], [2, 6], [5], [4, 6, 7]]
print(kosaraju(g))</
{{out}}
Line 63:
=={{header|C sharp|C#}}==
<
using System.Collections.Generic;
Line 134:
Assign(u, u);
}
}</
=={{header|C++}}==
{{trans|D}}
<
#include <iostream>
#include <ostream>
Line 224:
return 0;
}</
{{out}}
<pre>[0, 0, 0, 3, 3, 5, 5, 7]</pre>
Line 230:
=={{header|D}}==
{{trans|Kotlin}} (mostly) with output like {{trans|Go}}
<
import std.stdio;
Line 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 360 ⟶ 478:
}
return c
}</
{{out}}
<pre>
Line 369 ⟶ 487:
Implementation:
<
coerase([cocurrent)cocreate''
visit=: {{
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
Line 393 ⟶ 510:
assign~L
assigned
}}</
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
Line 422 ⟶ 544:
}}
┌─────┬┬┬───┬┬───┬┬─┐
│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:
<
┌─────┬┬┬───┬┬───┬┬─┐
│0 1 2│││3 4││5 6││7│
└─────┴┴┴───┴┴───┴┴─┘</
=={{header|Java}}==
{{trans|Kotlin}}
Output is like Go instead of what Kotlin outputs.
<
import java.util.Arrays;
import java.util.List;
Line 524 ⟶ 646:
System.out.println(output);
}
}</
{{out}}
<pre>[0, 0, 0, 3, 3, 5, 5, 7]</pre>
Line 530 ⟶ 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 588 ⟶ 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 599 ⟶ 721:
{{trans|Go}}
<
# 1. For each vertex u of the graph, mark u as unvisited. Let L be empty.
vis = falses(length(g))
Line 641 ⟶ 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 706 ⟶ 873:
fun main(args: Array<String>) {
println(kosaraju(g).joinToString("\n"))
}</
{{out}}
Line 718 ⟶ 885:
=={{header|Lua}}==
{{trans|C++}}
<
io.write("[")
for i=0,#a do
Line 812 ⟶ 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 863 ⟶ 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 870 ⟶ 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 942 ⟶ 1,203:
kosaraju(%test1);
say '';
kosaraju(%test2);</
{{out}}
<pre>0 1 2
Line 955 ⟶ 1,216:
=={{header|Phix}}==
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
Line 999 ⟶ 1,260:
<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>
<!--</
{{out}}
<pre>
Line 1,006 ⟶ 1,267:
=={{header|Python}}==
Works with Python 2
<syntaxhighlight lang="python">def kosaraju(g):
class nonlocal: pass
Line 1,045 ⟶ 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 1,082 ⟶ 1,386:
(3 1 2 4) ; equvalent to (3 . (1 2 4))
(4 5 3)
(7 4 7 6))))</
{{out}}
Line 1,095 ⟶ 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,145 ⟶ 1,449:
:Gary<Fred>,
:Hank<Earl Gary Hank>)
)</
{{out}}
<pre>
Line 1,154 ⟶ 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,200 ⟶ 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,207 ⟶ 1,511:
=={{header|Standard ML}}==
<
fun node x = Node (x, ref false, ref nil, ref nil)
Line 1,282 ⟶ 1,586:
val ns = make (16, is, ijs)
val xs = kosaraju ns</
{{out}}
<pre>
Line 1,293 ⟶ 1,597:
{{trans|D}}
<
let size = graph.count
var x = size
Line 1,352 ⟶ 1,656:
]
print(kosaraju(graph: graph))</
{{out}}
Line 1,360 ⟶ 1,664:
=={{header|Visual Basic .NET}}==
{{trans|Java}}
<
Function Kosaraju(g As List(Of List(Of Integer))) As List(Of Integer)
Line 1,423 ⟶ 1,727:
End Sub
End Module</
{{out}}
<pre>[0, 0, 0, 3, 3, 5, 5, 7]</pre>
Line 1,429 ⟶ 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,466 ⟶ 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,474 ⟶ 1,778:
=={{header|zkl}}==
<
fcn visit(u,G,L){ // u is ((visited,assigned), (id,edges))
Line 1,514 ⟶ 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,521 ⟶ 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>
| |||