Tarjan: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→{{header|Wren}}: Minor tidy) |
|||
| (13 intermediate revisions by 2 users not shown) | |||
Line 13:
;References:
* The article on [[wp:Tarjan's_strongly_connected_components_algorithm|Wikipedia]].
See also: [[Kosaraju]]
<br><br>
Line 623 ⟶ 625:
</pre>
=={{header|
Brute force implementation from wikipedia pseudocode:
<syntaxhighlight>▼
<syntaxhighlight lang=J>tarjan=: {{
coerase ([ cocurrent) cocreate'' NB. following =: declarations are temporary, expiring when we finish
graph=: y NB. connection matrix of a directed graph
result=: stack=: i.index=: 0
undef=: #graph
lolinks=: indices=: undef"_1 graph
onstack=: 0"_1 graph
strongconnect=: {{
indices=: index y} indices
lolinks=: index y} lolinks
onstack=: 1 y} onstack
stack=: stack,y
index=: index+1
for_w. y{::graph do.
if. undef = w{indices do.
strongconnect w
lolinks=: (<./lolinks{~y,w) y} lolinks
elseif. w{onstack do.
lolinks=: (<./lolinks{~y,w) y} lolinks
end.
end.
if. lolinks =&(y&{) indices do.
loc=. stack i. y
component=. loc }. stack
onstack=: 0 component} onstack
result=: result,<component
stack=: loc {. stack
end.
}}
for_Y. i.#graph do.
if. undef=Y{indices do.
strongconnect Y
end.
end.
result
▲}}</syntaxhighlight>
Example use, with graph from wikipedia animated example:
<syntaxhighlight lang=J> tarjan 1;2;0;1 2 4;3 5;2 6;5;4 6 7
┌─────┬───┬───┬─┐
│0 1 2│5 6│3 4│7│
└─────┴───┴───┴─┘</syntaxhighlight>
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.HashMap;
Line 840 ⟶ 888:
Results in the zero-base scheme: Array{Int64,1}[[2, 1, 0], [6, 5], [4, 3], [7]]
</pre>
=={{header|K}}==
Implementation:
<syntaxhighlight lang=K>F:{[g]
r::s::!i::0
t::+`o`j`k!(#g)#'0,2##g
L::{[g;v]
t[v]:1,i,i; s,:v; i+:1
{[g;v;w]
$[t[`k;w]=#g; L w; ~t[`o;w]; :0N]
t[`j;v]&:t[`j;w]}[g;v]'g v
$[=/t[`j`k;v]
[a:*&v=s; c:a_s; t[`o;c]:0; s::a#s; r,:,c]
]}[g]
{[g;v] $[t[`k;v]=#g; L v; ]}[g]'!#g
r}</syntaxhighlight>
Example:
<syntaxhighlight lang=K>F (1;2;0;1 2 4;3 5;2 6;5;4 6 7)
(0 1 2
5 6
3 4
,7)</syntaxhighlight>
tested with ngn/k
=={{header|Kotlin}}==
Line 1,961 ⟶ 2,035:
{{libheader|Wren-seq}}
{{libheader|Wren-dynamic}}
<syntaxhighlight lang="
import "./dynamic" for Tuple
class Node {
| |||