Content deleted Content added
→Where to store "lowlink": new section |
syntaxhighlight & fix lint |
||
| (30 intermediate revisions by 19 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-->
: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:
▲* 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)
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
::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 134 ⟶ 164:
== Counterexample ==
<syntaxhighlight lang="text">
node size : 12
map :
Line 150 ⟶ 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 161 ⟶ 190:
* Well, I just went through every one of the above claims and added a comment there. I don't think any of them present a problem for the algorithm in its current state. However, there are a number of small differences between the algorithm as it currently stands on Wikipedia, and the original Tarjan paper (see below). I don't think any of them actually change the behaviour of the algorithm though.
** Tarjan surrounds the "was successor on the stack" clause with "ELSE IF NUMBER (w) < NUMBER (v) DO", which in our algorithm would be written as "<code>else if v'.number < v.number</code>". I don't see a reason for this, though. By definition, all nodes which already have an index will have one less than the current node, so I think we can leave this out.
**: ''This is because Tarjan in his paper states that he will only consider (i) edges that are in the search tree, (ii) edges that connect back to some search tree ancestor ([[frond]]s), and (iii) edges between sibling branches in the search tree (cross-links); the fourth class of edges that go to an already visited direct descendant are to be ignored, and that is what this test achieves. But it is indeed a pointless test, as the min in that fourth case is just the current lowlink anyway.'' [[Special:Contributions/130.243.94.123|130.243.94.123]] ([[User talk:130.243.94.123|talk]]) 13:47, 9 December 2015 (UTC)
** Tarjan's "pop" loop is "WHILE w on top of point stack satisfies NUMBER (w) >= NUMBER (v) DO", which in our algorithm would be written as "<code>while v'.index >= v.index</code>". First, it is a while loop rather than a do-while loop (it is required to succeed on the first iteration). Second, it succeeds for v' == v (hence the do-while loop is not needed). Third, it fails if a node is encountered with an index smaller than the current node. I think you could reason that this accomplishes the same thing as popping all nodes up to and including the current node: the nodes on the stack should always be sorted by index, so popping until a node is found with a smaller index than the current is the same as popping until the current node is found.
** Therefore, I would consider the Wikipedia version to be functionally equivalent to the original. I will therefore remove the "dispute" box I put up earlier.
Line 201 ⟶ 231:
As I see, we read the parameter "lowlink" only from child nodes and current node and we write it only to current node. Therefore, we can have this parameter as a local variable and return it from "strongconnect". I. e. we can store "lowlink" on the stack for recursive calls (= [[Depth-first search|DFS]] algorithm stack). In such a way, this algorithm is connected to [[path-based strong component algorithm]]. From the stack of lowlinks we can compute the ''P'' stack. --[[User:Beroal|Beroal]] ([[User talk:Beroal|talk]]) 14:55, 24 June 2013 (UTC)
== Constant time check for a node (vertex) on the stack ==
A recent edit, {{oldid2|647184742|01:55, 15 February 2015}}, attempts a technique to determine in constant time if a node is on the stack. The cited original paper by Tarjan mentions, "Testing to see if a vertex is on the point stack can be done in a fixed time if a Boolean array is kept which answers this question for each vertex." The recent edit however, introduces an "isRemoved" value per node, which is the opposite sense of "on the stack." The algorithm may work with this change, but it's difficult to see. It does not "answer the question for each vertex" as Tarjan suggested because the value is meaningless until the node is visited. Much more clear and following Tarjan's suggestion would be an "onStack" value. Further, if all onStack values were initialized to false at the start of the algorithm, then it would be clear that all nodes have valid values. —[[User:Fifteen Minutes Of Fame|Fifteen Minutes Of Fame]] ([[User talk:Fifteen Minutes Of Fame|talk]]) 04:26, 27 February 2015 (UTC)
== The pseudocode didn't work for me ==
I've carefully implemented the pseudocode and it produced incorrect results for me. I found a link above ([http://web.cecs.pdx.edu/~herb/cs410f99/scc.htm web.cecs.pdx.edu]) that helped me out.
It seems that an extra condition is missing here:
'''else if''' (''w''.onStack) '''then'''
''// Successor w is in stack S and hence in the current SCC''
''v''.lowlink := min(''v''.lowlink, ''w''.index)
'''end if'''
This version worked for me:
'''else if''' (''w''.index < ''v''.index '''and''' ''w''.onStack) '''then'''
''// Successor w is in stack S and hence in the current SCC''
''v''.lowlink := min(''v''.lowlink, ''w''.index)
'''end if'''
--[[User:Kalmankeri|Kalmankeri]] ([[User talk:Kalmankeri|talk]]) 15:15, 10 March 2015 (UTC)
: 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 ==
Thinking about the matter a bit more, I find it highly unlikely that Tarjan's algorithm can be derived from [[Kosaraju's algorithm]]. Unless anyone can come up with a source for the claim
: 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)
| |||