Content deleted Content added
→Bug in second subcase: My comment on this issue. I think it's fine. |
→Algorithm is still broken: Refute that the algorithm is broken |
||
Line 66:
v.lowlink = min(v.lowlink, v'.lowlink)
</pre>
* The above analysis is incorrect. You are assuming that nothing ever gets popped off the stack. Note that nodes which are identified as SCC roots are popped off the stack ''during the algorithm''. Therefore, once a complete SCC has been identified, all of the nodes in that SCC are a) already visited (have an index), and b) not on the stack. Thus, there is a third (implicit) "else" branch which does nothing -- that is for the case where a node's successor is already in an SCC which is already complete, and therefore it cannot possibly include the current node, so it is safe to ignore it. '''Do not make the above change'''. —[[User:MattGiuca|MattGiuca]] ([[User talk:MattGiuca|talk]]) 06:30, 8 February 2011 (UTC)
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 <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/145.248.195.1|145.248.195.1]] ([[User talk:145.248.195.1|talk]]) </span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
* Again, this misses the point that nodes are popped '''during''' the algorithm, '''not''' at the end. There is not just a single SCC identified; this identifies all of them. This does correctly pop nodes once an SCC is found (and as far as I can tell did also at the date of the comment). —[[User:MattGiuca|MattGiuca]] ([[User talk:MattGiuca|talk]]) 06:30, 8 February 2011 (UTC)
== Algorithm fixed ==
| |||