Tarjan: Difference between revisions
Content added Content deleted
(J) |
|||
Line 622: | Line 622: | ||
[7] |
[7] |
||
</pre> |
</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}}== |
=={{header|Java}}== |