Rosetta Code

Kosaraju: Difference between revisions

Page Discussion

Kosaraju (view source)

Revision as of 11:58, 12 December 2023

1,531 bytes added ,  6 months ago
m
→‎{{header|Wren}}: Changed to Wren S/H
(Insert a working python3 version of the python code)
m (→‎{{header|Wren}}: Changed to Wren S/H)
(7 intermediate revisions by 2 users not shown)
Line 487:
 
Implementation:
<syntaxhighlight lang="j">visitkosaraju=: {{
coerase([cocurrent)cocreate''
if.y{unvisited do.
visit=: {{
unvisited=: 0 y} unvisited
visit if.y{::outunvisited do.
L unvisited=: 0 y,L} unvisited
visit y{::out
end.
L=: y,L
}}"0
end.
 
}}"0
assign=: {{
assign=: {{
if._1=y{assigned do.
if._1=y{assigned do.
assigned=: x y} assigned
assigned=: x y} assigned
x&assign y{::in
x&assign y{::in
end.
end.
}}"0
}}"0
 
kosaraju=: {{
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, and:
 
<syntaxhighlight lang="j">
assign=: {{
if.-.y e.;assigned do.
assigned=: (y,L:0~x{assigned) x} assigned
x&assign y{::in
end.
}}"0
 
 
<syntaxhighlight lang="j">kosarajud=: {{
kosaraju=: {{
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:
}}
 
kosarajukosarajud 1;2;0;1 2 4;3 5;2 6;5;4 6 7
┌─────┬┬┬───┬┬───┬┬─┐
│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 1,217 ⟶ 1,266:
</pre>
 
=={{header|Python3Python}}==
Works with Python 2
<syntaxhighlight lang="python3">def kosaraju(g):
<syntaxhighlight lang="python">def kosaraju(g):
class nonlocal: pass
 
# 1. For each vertex u of the graph, mark u as unvisited. Let l be empty.
size = len(g)
 
vis = [False] * size
lvis = [0False] * size # vertexes that have been visited
xl = [0]*size
tnonlocal.x = [[] for _ in range(size)]
t = [[]]*size # transpose graph
 
def visit(u):
nonlocal x
if not vis[u]:
vis[u] = True
for v in g[u]:
visit(v)
t[v].append( = t[v] + [u)]
nonlocal.x -= nonlocal.x - 1
l[nonlocal.x] = u
 
# 2. For each vertex u of the graph do visit(u)
for u in range(size):
for u in range(len(g)):
visit(u)
c = [0] * size
 
def assign(u, root):
Line 1,246 ⟶ 1,300:
assign(v, root)
 
# 3: For each element u of l in order, do assign(u, u)
for u in l:
assign(u, u)
Line 1,251 ⟶ 1,306:
return c
 
g = [[1], [2], [0], [1,2,4], [3,5], [2,6], [5], [4,6,7]]
 
print kosaraju(g)</syntaxhighlight>
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>
 
Syntax requirements have changed. This version works with Python 3.
 
<syntaxhighlight lang="python3">def kosaraju(g):
 
=={{header|Python}}==
<syntaxhighlight lang="python">def kosaraju(g):
class nonlocal: pass
 
# 1. For each vertex u of the graph, mark u as unvisited. Let l be empty.
size = len(g)
vis = [False] * size
 
visl = [False0] * size # vertexes that have been visited
lx = [0]*size
nonlocal.xt = [[] for _ in range(size)]
t = [[]]*size # transpose graph
 
def visit(u):
nonlocal x
if not vis[u]:
vis[u] = True
for v in g[u]:
visit(v)
t[v] = t[v] + [.append(u])
nonlocal.x -= nonlocal.x - 1
l[nonlocal.x] = u
 
for u in range(size):
# 2. For each vertex u of the graph do visit(u)
for u in range(len(g)):
visit(u)
c = [0] * size
 
def assign(u, root):
Line 1,293 ⟶ 1,340:
assign(v, root)
 
# 3: For each element u of l in order, do assign(u, u)
for u in l:
assign(u, u)
Line 1,299 ⟶ 1,345:
return c
 
 
g = [[1], [2], [0], [1,2,4], [3,5], [2,6], [5], [4,6,7]]
g = [[1], [2], [0], [1, 2, 4], [3, 5], [2, 6], [5], [4, 6, 7]]
print kosaraju(g)</syntaxhighlight>
print(kosaraju(g))</syntaxhighlight>
 
{{out}}
<pre>[0, 0, 0, 3, 3, 5, 5, 7]</pre>
 
 
=={{header|Racket}}==
Line 1,684 ⟶ 1,733:
=={{header|Wren}}==
{{trans|Go}}
<syntaxhighlight lang="ecmascriptwren">var kosaraju = Fn.new { |g|
var gc = g.count
// 1. For each vertex u of the graph, mark u as unvisited. Let l be empty.
PureFox
9,485

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/339559...353223"