Content deleted Content added
→Status of the algorithm: Finish analysis of the above bugs and discuss differences with the original (includes full copy of original) |
|||
Line 35:
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)
* I noticed this quirk and wanted to comment. While I agree that strictly speaking the algorithm is correct, if someone wants to make a very tiny change in the end use of the algorithm this is a crippling bug. SCC's are a disjoint set, so a useful operation is to check whether two arbitrary nodes are in the same SCC. If you change it to v.lowlink, then I believe that two nodes are in the same SCC iff they have the same lowlink value. Ultimately the goal should be to inform the reader about this algorithm; should we restrict our information based on the original publication? Surely improvements or knowledge discovered since original publication are worth mentioning? I think this is worth mentioning in the notes section.[[User:Nirf|Nirf]] ([[User talk:Nirf|talk]]) 00:23, 1 February 2013 (UTC)
== Algorithm is still broken ==
| |||