(phixonline)-->
with javascript_semantics
constant g = {{2}, {3}, {1}, {2,3,5}, {6,4}, {3,7}, {6}, {5,8,7}}
sequence index, lowlink, stacked, stack
integer x
function strong_connect(integer n, emit)
index[n] = x
lowlink[n] = x
stacked[n] = 1
stack &= n
x += 1
for b=1 to length(g[n]) do
integer nb = g[n][b]
if index[nb] == 0 then
if not strong_connect(nb,emit) then
return false
end if
if lowlink[nb] < lowlink[n] then
lowlink[n] = lowlink[nb]
end if
elsif stacked[nb] == 1 then
if index[nb] < lowlink[n] then
lowlink[n] = index[nb]
end if
end if
end for
if lowlink[n] == index[n] then
sequence c = {}
while true do
integer w := stack[$]
stack = stack[1..$-1]
stacked[w] = 0
c = prepend(c, w)
if w == n then
emit(c)
exit
end if
end while
end if
return true
end function
procedure tarjan(sequence g, integer emit)
index = repeat(0,length(g))
lowlink = repeat(0,length(g))
stacked = repeat(0,length(g))
stack = {}
x = 1
for n=1 to length(g) do
if index[n] == 0
and not strong_connect(n,emit) then
return
end if
end for
end procedure
procedure emit(object c)
-- called for each component identified.
-- each component is a list of nodes.
?c
end procedure
tarjan(g,emit)