63 lines
1.4 KiB
Plaintext
63 lines
1.4 KiB
Plaintext
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)
|
|
}
|