Rosetta Code

Tarjan: Difference between revisions

Page Discussion

Tarjan (view source)

Revision as of 13:07, 12 April 2022

12,721 bytes added ,  2 years ago
m
→‎{{header|Phix}}: syntax coloured
m (→‎{{header|jq}}: simplify)
m (→‎{{header|Phix}}: syntax coloured)
Line 997:
{{trans|Go}}
Same data as other examples, but with 1-based indexes.
<!--<lang Phix>(phixonline)-->
<lang Phix>constant g = {{2}, {3}, {1}, {2,3,5}, {6,4}, {3,7}, {6}, {5,8,7}}
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
 
<span style="color: #008080;">constant</span> <span style="color: #000000;">g</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">6</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">}}</span>
sequence index, lowlink, stacked, stack
integer x
<span style="color: #004080;">sequence</span> <span style="color: #000000;">index</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">lowlink</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">stacked</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">stack</span>
 
<span style="color: #004080;">integer</span> <span style="color: #000000;">x</span>
function strong_connect(integer n, r_emit)
index[n] = x
<span style="color: #008080;">function</span> <span style="color: #000000;">strong_connect</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">emit</span><span style="color: #0000FF;">)</span>
lowlink[n] = x
<span style="color: #000000;">index</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span>
stacked[n] = 1
<span style="color: #000000;">lowlink</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span>
stack &= n
<span style="color: #000000;">stacked</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
x += 1
<span style="color: #000000;">stack</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">n</span>
for b=1 to length(g[n]) do
<span style="color: #000000;">x</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
integer nb = g[n][b]
<span style="color: #008080;">for</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">g</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
if index[nb] == 0 then
<span style="color: #004080;">integer</span> <span style="color: #000000;">nb</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">g</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">][</span><span style="color: #000000;">b</span><span style="color: #0000FF;">]</span>
if not strong_connect(nb,r_emit) then
<span style="color: #008080;">if</span> <span style="color: #000000;">index</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nb</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
return false
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">strong_connect</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nb</span><span style="color: #0000FF;">,</span><span style="color: #000000;">emit</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
end if
<span style="color: #008080;">return</span> <span style="color: #004600;">false</span>
if lowlink[nb] < lowlink[n] then
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
lowlink[n] = lowlink[nb]
<span style="color: #008080;">if</span> <span style="color: #000000;">lowlink</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nb</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">lowlink</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
end if
<span style="color: #000000;">lowlink</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">lowlink</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nb</span><span style="color: #0000FF;">]</span>
elsif stacked[nb] == 1 then
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if index[nb] < lowlink[n] then
<span style="color: #008080;">elsif</span> <span style="color: #000000;">stacked</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nb</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
lowlink[n] = index[nb]
<span style="color: #008080;">if</span> <span style="color: #000000;">index</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nb</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">lowlink</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
end if
<span style="color: #000000;">lowlink</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">index</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nb</span><span style="color: #0000FF;">]</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if lowlink[n] == index[n] then
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
sequence c = {}
<span style="color: #008080;">if</span> <span style="color: #000000;">lowlink</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">index</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
while true do
<span style="color: #004080;">sequence</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
integer w := stack[$]
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
stack = stack[1..$-1]
<span style="color: #004080;">integer</span> <span style="color: #000000;">w</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">stack</span><span style="color: #0000FF;">[$]</span>
stacked[w] = 0
<span style="color: #000000;">stack</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">stack</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..$-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
c = prepend(c, w)
<span style="color: #000000;">stacked</span><span style="color: #0000FF;">[</span><span style="color: #000000;">w</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
if w == n then
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">prepend</span><span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">w</span><span style="color: #0000FF;">)</span>
call_proc(r_emit,{c})
<span style="color: #008080;">if</span> <span style="color: #000000;">w</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">n</span> <span style="color: #008080;">then</span>
exit
<span style="color: #000000;">emit</span><span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #008080;">exit</span>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
return true
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end function
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
 
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
procedure tarjan(sequence g, integer r_emit)
index = repeat(0,length(g))
<span style="color: #008080;">procedure</span> <span style="color: #000000;">tarjan</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">g</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">emit</span><span style="color: #0000FF;">)</span>
lowlink = repeat(0,length(g))
<span style="color: #000000;">index</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">g</span><span style="color: #0000FF;">))</span>
stacked = repeat(0,length(g))
<span style="color: #000000;">lowlink</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">g</span><span style="color: #0000FF;">))</span>
stack = {}
<span style="color: #000000;">stacked</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">g</span><span style="color: #0000FF;">))</span>
x := 1
<span style="color: #000000;">stack</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
for n=1 to length(g) do
<span style="color: #000000;">x</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
if index[n] == 0
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">g</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
and not strong_connect(n,r_emit) then
<span style="color: #008080;">if</span> <span style="color: #000000;">index</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">0</span>
return
<span style="color: #008080;">and</span> <span style="color: #008080;">not</span> <span style="color: #000000;">strong_connect</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">emit</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
end if
<span style="color: #008080;">return</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end procedure
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
 
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
procedure emit(object c)
-- called for each component identified.
<span style="color: #008080;">procedure</span> <span style="color: #000000;">emit</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">)</span>
-- each component is a list of nodes.
<span style="color: #000080;font-style:italic;">-- called for each component identified.
?c
-- each component is a list of nodes.</span>
end procedure
<span style="color: #0000FF;">?</span><span style="color: #000000;">c</span>
 
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
tarjan(g,routine_id("emit"))</lang>
<span style="color: #000000;">tarjan</span><span style="color: #0000FF;">(</span><span style="color: #000000;">g</span><span style="color: #0000FF;">,</span><span style="color: #000000;">emit</span><span style="color: #0000FF;">)</span>
<!--</lang>-->
{{out}}
<pre>
Petelomax
7,820

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/274253"