Tarjan: Difference between revisions
Content added Content deleted
m (→{{header|J}}: cleaner) |
m (→{{header|J}}) |
||
| Line 628: | Line 628: | ||
<syntaxhighlight lang=J>tarjan=: {{ |
<syntaxhighlight lang=J>tarjan=: {{ |
||
cocurrent temp=. cocreate'' |
|||
coerase([cocurrent)cocreate '' NB. (names defined below with =: will be erased on exit from tarjan) |
|||
coerase temp |
|||
graph=: y NB. connection matrix of a directed graph |
graph=: y NB. connection matrix of a directed graph |
||
result=: stack=: i.index=: 0 |
result=: stack=: i.index=: 0 |
||
| Line 649: | Line 650: | ||
end. |
end. |
||
if. lolinks =&(y&{) indices do. |
if. lolinks =&(y&{) indices do. |
||
loc=. stack i. y |
|||
component=. loc }. stack |
|||
onstack=: 0 component} onstack |
onstack=: 0 component} onstack |
||
result=: result,<component |
result=: result,<component |
||
stack=: |
stack=: loc {. stack |
||
end. |
end. |
||
}} |
}} |
||
| Line 663: | Line 665: | ||
}}</syntaxhighlight> |
}}</syntaxhighlight> |
||
Example use, with graph from wikipedia animated example: |
|||
<syntaxhighlight lang=J> |
<syntaxhighlight lang=J> tarjan 1;2;0;1 2 4;3 5;2 6;5;4 6 7 |
||
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│ |
│0 1 2│5 6│3 4│7│ |
||
└─────┴───┴───┴─┘ |
└─────┴───┴───┴─┘</syntaxhighlight> |
||
</syntaxhighlight> |
|||
=={{header|Java}}== |
=={{header|Java}}== |
||