Kosaraju: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
| (10 intermediate revisions by 4 users not shown) | |||
Line 487:
Implementation:
<syntaxhighlight lang="j">
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 518 ⟶ 517:
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 540 ⟶ 544:
}}
┌─────┬┬┬───┬┬───┬┬─┐
│0 2 1│││3 4││5 6││7│
Line 763 ⟶ 767:
{{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}}==
Line 997 ⟶ 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}}==
Line 1,133 ⟶ 1,267:
=={{header|Python}}==
Works with Python 2
<syntaxhighlight lang="python">def kosaraju(g):
class nonlocal: pass
Line 1,175 ⟶ 1,310:
{{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}}==
Line 1,556 ⟶ 1,733:
=={{header|Wren}}==
{{trans|Go}}
<syntaxhighlight lang="
var gc = g.count
// 1. For each vertex u of the graph, mark u as unvisited. Let l be empty.
| |||