Tarjan: Difference between revisions
J
(J) |
|||
Line 622:
[7]
</pre>
=={{header|J}}==
Brute force implementation from wikipedia pseudocode:
<syntaxhighlight lang=J>tarjan=: {{
cocurrent temp=. cocreate''
coerase temp
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.
component=. (stack i. y) }. stack
onstack=: 0 component} onstack
result=: result,<component
stack=: stack -. component
end.
}}
for_Y. i.#graph do.
if. undef=Y{indices do.
strongconnect Y
end.
end.
result
}}</syntaxhighlight>
Graph from wikipedia animated example:
<syntaxhighlight lang=J>digraph1=: I.@do each}:cutLF{{)n
0 1 NB. 0
0 0 1 NB. 1
1 0 NB. 2
0 1 1 0 1 NB. 3
0 0 0 1 0 1 NB. 4
0 0 1 0 0 0 1 NB. 5
0 0 0 0 0 1 NB. 6
0 0 0 0 1 0 1 1 NB. 7
NB. 0 1 2 3 4 5 6 7
}}</syntaxhighlight>
example use:
<syntaxhighlight lang=J> tarjan digraph1
┌─────┬───┬───┬─┐
│0 1 2│5 6│3 4│7│
└─────┴───┴───┴─┘
</syntaxhighlight>
=={{header|Java}}==
| |||