Content deleted Content added
→Bug in second subcase: My comment on this issue. I think it's fine. |
|||
Line 34:
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-->
* I agree that both versions give equivalent results. Note that v'.index is '''not''' always the same as v'.lowlink (as v' is not always a root). But it does always get the same result, as you have for both approaches identified another node with a smaller index than this one which is in the same SCC, and set your lowlink to the index of another node in the same SCC (it doesn't matter which, as long as the root and only the root node's lowlink is equal to its index). In any case, I consulted Tarjan's original paper, and he uses index in the latter branch (as [[Special:Contributions/128.9.216.61|128.9.216.61]] changed it to) -- even though I think this is poorer style, we should stick with the original algorithm. '''Not an issue.''' —[[User:MattGiuca|MattGiuca]] ([[User talk:MattGiuca|talk]]) 06:22, 8 February 2011 (UTC)
== Algorithm is still broken ==
| |||