Tarjan: Difference between revisions
m
order entries
Walterpachl (talk | contribs) m (add REXX) |
Walterpachl (talk | contribs) m (order entries) |
||
Line 1,023:
Strongly connected components: (Andy Bart Carl)(Dave Earl)(Fred Gary)(Hank)</pre>
=={{header|REXXl}}==
Line 1,188 ⟶ 1,118:
[8]</pre>
=={{header|Sidef}}==
{{trans|Raku}}
<lang ruby>func tarjan (k) {
var(:onstack, :index, :lowlink, *stack, *connected)
func strong_connect (vertex, i=0) {
index{vertex} = i
lowlink{vertex} = i+1
onstack{vertex} = true
stack << vertex
for connection in (k{vertex}) {
if (index{connection} == nil) {
strong_connect(connection, i+1)
lowlink{vertex} `min!` lowlink{connection}
}
elsif (onstack{connection}) {
lowlink{vertex} `min!` index{connection}
}
}
if (lowlink{vertex} == index{vertex}) {
var *node
do {
node << stack.pop
onstack{node.tail} = false
} while (node.tail != vertex)
connected << node
}
}
{ strong_connect(_) if !index{_} } << k.keys
return connected
}
var tests = [
Hash(
0 => <1>,
1 => <2>,
2 => <0>,
3 => <1 2 4>,
4 => <3 5>,
5 => <2 6>,
6 => <5>,
7 => <4 6 7>,
),
Hash(
:Andy => <Bart>,
:Bart => <Carl>,
:Carl => <Andy>,
:Dave => <Bart Carl Earl>,
:Earl => <Dave Fred>,
:Fred => <Carl Gary>,
:Gary => <Fred>,
:Hank => <Earl Gary Hank>,
)
]
tests.each {|t|
say ("Strongly connected components: ", tarjan(t).map{.sort}.sort)
}</lang>
{{out}}
<pre>
Strongly connected components: [["0", "1", "2"], ["3", "4"], ["5", "6"], ["7"]]
Strongly connected components: [["Andy", "Bart", "Carl"], ["Dave", "Earl"], ["Fred", "Gary"], ["Hank"]]
</pre>
=={{header|zkl}}==
| |||