Content deleted Content added
m Signing comment by Encyclopedant - "→Is there a minimal set of test cases somewhere?: new section" |
syntaxhighlight & fix lint |
||
| (12 intermediate revisions by 10 users not shown) | |||
Line 1:
{{WikiProject banner shell|class=C|
{{WikiProject Mathematics|priority=Low}}
}}
== Pseudocode is not good ==
Line 52 ⟶ 54:
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:
Line 159 ⟶ 164:
== Counterexample ==
<syntaxhighlight lang="text">
node size : 12
map :
Line 175 ⟶ 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 251 ⟶ 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 261 ⟶ 266:
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)
| |||