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

Revision as of 02:53, 24 June 2014

Revision as of 03:03, 24 June 2014

Line 37:

* 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 of this line of code.

input:

0->1;0->2

1->3;1->4

2->5

4->5

5->6;5->7;5->0

6->4

7->5

Output:

3

2

014567 <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/198.244.105.129|198.244.105.129]] ([[User talk:198.244.105.129|talk]]) 02:52, 24 June 2014 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

== Algorithm is still broken ==