Tarjan: Difference between revisions

=={{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>