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

Revision as of 10:21, 27 May 2020

Latest revision as of 17:05, 14 January 2025

(11 intermediate revisions by 9 users not shown)

Line 1:

{{WikiProject banner shell|class=C|

{{maths rating|class=C|priority=Low|field=discrete}}

{{WikiProject Mathematics|priority=Low}}

}}

== Pseudocode is not good ==

Line 162 ⟶ 164:

== Counterexample ==

<syntaxhighlight lang="text">

<code>

<pre>

node size : 12

map :

Line 178 ⟶ 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>

</pre></code>

In this case the whole graph is strongly connected

Line 254 ⟶ 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 264 ⟶ 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">—&nbsp;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">—&nbsp;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)