Content deleted Content added
syntaxhighlight & fix lint |
|||
| (19 intermediate revisions by 15 users not shown) | |||
Line 1:
{{WikiProject banner shell|class=C|
{{WikiProject Mathematics|priority=Low}}
}}
== Pseudocode is not good ==
Line 34 ⟶ 36:
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 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:
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?
:::The [https://www.sciencedirect.com/science/article/abs/pii/S0020019015001532?via%3Dihub 2015 paper] linked from the Complexity section does basically <code>v.lowlink=min(v.lowlink,w.lowlink)</code> in Algorithm 3 PEA_FIND_SCC2(V,E). Perhaps we could have a section discussing variations to the algorithm? --[[User:Thomasda|Thomasda]] ([[User talk:Thomasda|talk]]) 10:20, 27 May 2020 (UTC)
[[Special:Contributions/195.190.84.155|195.190.84.155]] ([[User talk:195.190.84.155|talk]]) 12:04, 11 April 2017 (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:
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 ==
Line 150 ⟶ 164:
== Counterexample ==
<syntaxhighlight lang="text">
node size : 12
map :
Line 166 ⟶ 179:
0 1 1 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0
</syntaxhighlight>
In this case the whole graph is strongly connected
Line 242 ⟶ 255:
: Well that would bring the pseudocode back to Tarjan's original. MattGiuca considered this above under Status of the algorithm and reasoned that v, just numbered, would have to be greater than any existing number. But while numbering v happens before looping over successors, it does seems that a recursive call to strongconnect on one successor of v could number a later successor of v. I'm inclined to agree that this looks like a problem but a test case might show it clearly. Do you have an example of a graph that shows this failure? —[[User:Fifteen Minutes Of Fame|Fifteen Minutes Of Fame]] ([[User talk:Fifteen Minutes Of Fame|talk]]) 15:56, 28 March 2015 (UTC)
:: <code>v.lowlink</code> can't be bigger than <code>v.index</code>, so if <code>w.index > v.index</code> nothing will happen anyway. --[[User:Igor Yalovecky|Igor Yalovecky]] ([[User talk:Igor Yalovecky|talk]]) 15:52, 3 September 2022 (UTC)
== Relation to Kosaraju's algorithm ==
Line 248 ⟶ 262:
: Although proposed earlier, [Tarjan's algorithm] can be seen as an improved version of Kosaraju's algorithm
then it should be removed. It ''could'' simply have been meant as a claim that Tarjan's algorithm is superior to Kosaraju's algorithm, but in that case this needs to be clearer, and such a statement probably shouldn't appear that early in the article. [[Special:Contributions/130.243.94.123|130.243.94.123]] ([[User talk:130.243.94.123|talk]]) 13:58, 9 December 2015 (UTC)
== Is there a minimal set of test cases somewhere? ==
A set of test cases should include a simple root, an SCC root (no incoming edges), interior SCCs (with and without multiple incoming and or outgoing edges, and a terminal SCC (no outgoing edges). <!-- Template:Unsigned --><small class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Encyclopedant|Encyclopedant]] ([[User talk:Encyclopedant#top|talk]] • [[Special:Contributions/Encyclopedant|contribs]]) 03:54, 23 April 2020 (UTC)</small> <!--Autosigned by SineBot-->
== Year of the invention? ==
It was published by Tarjan in 1972, but I am pretty sure it was known to him and other before that. Just hard to pin point it. [[Special:Contributions/2A02:168:2000:5B:CC4D:BB9A:938:B537|2A02:168:2000:5B:CC4D:BB9A:938:B537]] ([[User talk:2A02:168:2000:5B:CC4D:BB9A:938:B537|talk]]) 03:59, 25 June 2020 (UTC)
== Links to implementations ==
Previously this article listed a number of external links to implementations in various programming languages. Last time in this revision: https://en.wikipedia.org/w/index.php?title=Tarjan%27s_strongly_connected_components_algorithm&direction=prev&oldid=898857841 It is hard to find these on the internet. I know how hard it was to develop the PHP version, for example. Could we either reinstate these links or have a related page about implementations of this Tarjan's algorithm? Or perhaps there are better ideas? <!-- Template:Unsigned --><small class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Vacilandois|Vacilandois]] ([[User talk:Vacilandois#top|talk]] • [[Special:Contributions/Vacilandois|contribs]]) 17:29, 6 November 2020 (UTC)</small> <!--Autosigned by SineBot-->
:[[Rosetta Code]] has become established as a site for "implementations in various programming languages". I have added a link to their site, which hopefully will not be deleted. I suggest you contribute your implementation there. --[[User:Mathnerd314159|Mathnerd314159]] ([[User talk:Mathnerd314159|talk]]) 17:47, 25 February 2022 (UTC)
:I was looking at your code links today, and it struck me that it did not look like the Tarjan algorithm. I think it might be the path-based strong component algorithm, as there is no "point_stack" in Tarjan, like there appears to be in your code. [[Special:Contributions/50.170.44.210|50.170.44.210]] ([[User talk:50.170.44.210|talk]]) 21:00, 9 December 2022 (UTC)
== ...and pseudocode is still buggy ==
For a graph with a single vertex with no edges (i.e. adjacency matrix 0 -> []), fails at w := S.pop(), because stack is empty at that moment. [[Special:Contributions/87.241.189.187|87.241.189.187]] ([[User talk:87.241.189.187|talk]]) 04:07, 6 December 2022 (UTC)
:It shouldn't fail, since the single vertex is pushed at line 16 of the algorithm before it is popped. [[User:PoleoMenta|PoleoMenta]] ([[User talk:PoleoMenta|talk]]) 14:25, 21 February 2024 (UTC)
| |||