Talk:Tarjan's strongly connected components algorithm: Difference between revisions

Revision as of 12:27, 21 March 2010

Revision as of 16:17, 17 June 2010

Line 33:

Both versions are correct, since v'.lowlink is the same as v'.index for the root of a strongly connected component. Therefore, I suggest to revert this change to the previous version, where the update is uniform in both branches. <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/192.35.241.121|192.35.241.121]] ([[User talk:192.35.241.121|talk]]) 17:55, 4 August 2009 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

== Algorithm is still broken ==

There are two issues :

1. The conditions on the branches (below) are strictly opposite:

<pre>

if (v'.index is undefined) // Was successor v' visited?

tarjan(v') // Recurse

v.lowlink = min(v.lowlink, v'.lowlink)

else if (v' is in S) // Was successor v' in stack S?

v.lowlink = min(v.lowlink, v'.index ) //v' is in stack but it isn't in the dfs tree

</pre>

that is because the only region where we modify .index and push into S is the following:

<pre>

v.index = index // Set the depth index for v

v.lowlink = index

index = index + 1

S.push(v)

</pre>

Which prooves that outside this region the following holds:

<pre>

bool(v'.index is undefined) != bool(v' is in S)

</pre>

Therefore in *any* case exactly one branch will be executed and therefore the whole block could be simplyfied by:

<pre>

if (v'.index is undefined) // Was successor v' visited?

tarjan(v') // Recurse

v.lowlink = min(v.lowlink, v'.lowlink)

</pre>

2. The SCC printed at the end is incorrect because algorithm never pops out nodes. Imagine the SCC is found for the last sucessor of v. In that case *every* sucessor will be printed, which is clearly not correct.

Anonymous - 18:16, 16 june 2010

== Algorithm fixed ==