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

Revision as of 12:04, 11 April 2017

Revision as of 19:38, 21 August 2018

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.''' &mdash;[[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)

* :The first is correct. The second leads to a bug where a node that is higher up in the chain pointing to an already established set of connected components to not be included as part of the stack pop. The following graph shows this error. 2 should be include as a strongly connected component but it is not because lowlink of 2 is 1 and index of 5 is 3; however lowlink of 5 is 0. In the first case 1 is the min leading to 2 being poped by it self. second case 2 gets a lowlink of 0 and pops all the elements off the stack

* 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)

* The first is correct. The second leads to a bug where a node that is higher up in the chain pointing to an already established set of connected components to not be included as part of the stack pop. The following graph shows this error. 2 should be include as a strongly connected component but it is not because lowlink of 2 is 1 and index of 5 is 3; however lowlink of 5 is 0. In the first case 1 is the min leading to 2 being poped by it self. second case 2 gets a lowlink of 0 and pops all the elements off the stack

input:

Line 53 ⟶ 51:

2

014567

** ::No, I just tried out this case; both versions of code give the same output. [[User:MaigoAkisame|MaigoAkisame]] ([[User talk:MaigoAkisame|talk]]) 17:35, 4 January 2016 (UTC)

** ::This was changed once more, and I reverted the change. If someone wants to have w.lowlink in that line they should provide a REVIEWED reference proving that it works, and indicate that the original differed. Someone looking for Tarjan's algorithm on Wikipedia is likely looking for his algorithm - not some other algorithm that may or may not be correct. Assuming the modified algorithm was correct and faster (neither is clear) - how would you compare them: stating that Tarjan's algorithm is better than Tarjan's algorithm? [[Special:Contributions/195.190.84.155|195.190.84.155]] ([[User talk:195.190.84.155|talk]]) 12:04, 11 April 2017 (UTC)

** No, I just tried out this case; both versions of code give the same output. [[User:MaigoAkisame|MaigoAkisame]] ([[User talk:MaigoAkisame|talk]]) 17:35, 4 January 2016 (UTC)

:Use v.lowlink = min(v.lowlink, w.index) give lowlink a more meaningful definition: it is the node with the smallest index v can reach with only one back edge. If min(v.lowlink, w.lowlink) is used, the lowlink will loss its meaning (for clarity, let's call this definition lowlink'). If w is a parent of v in the DFS tree, its lowlink' is not finalized, and could still change. This means you can not just define v.lowlink' as the smallest index v can reach, because that is not necessarily true.

:For example:

** This was changed once more, and I reverted the change. If someone wants to have w.lowlink in that line they should provide a REVIEWED reference proving that it works, and indicate that the original differed. Someone looking for Tarjan's algorithm on Wikipedia is likely looking for his algorithm - not some other algorithm that may or may not be correct. Assuming the modified algorithm was correct and faster (neither is clear) - how would you compare them: stating that Tarjan's algorithm is better than Tarjan's algorithm? [[Special:Contributions/195.190.84.155|195.190.84.155]] ([[User talk:195.190.84.155|talk]]) 12:04, 11 April 2017 (UTC)

Input:

0->1

1->2

2->1

1->3

3->0

:If 2 is reached before 3, its lowlink' will be 1, which is not the lowest node it can reach (which is 0, because 2->1->3->0). [[Special:Contributions/82.34.54.1|82.34.54.1]] ([[User talk:82.34.54.1|talk]]) 19:38, 21 August 2018 (UTC)

== Algorithm is still broken ==