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

Revision as of 17:35, 4 January 2016

Revision as of 23:32, 17 July 2016

Line 1:

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

== Pseudocode is not good ==

Line 10:

--[[Special:Contributions/211.25.51.200|211.25.51.200]] ([[User talk:211.25.51.200|talk]]) 07:05, 23 April 2008 (UTC)

* This has been corrected in the article. '''No longer an issue.''' —[[User:MattGiuca|MattGiuca]] ([[User talk:MattGiuca|talk]]) 05:38, 8 February 2011 (UTC)

== Bug in second subcase ==

Line 34 ⟶ 33:

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 agree that both versions give equivalent results. Note that v'.index is '''not''' always the same as v'.lowlink (as v' is not always a root). But it does always get the same result, as you have for both approaches identified another node with a smaller index than this one which is in the same SCC, and set your lowlink to the index of another node in the same SCC (it doesn't matter which, as long as the root and only the root node's lowlink is equal to its index). In any case, I consulted Tarjan's original paper, and he uses index in the latter branch (as [[Special:Contributions/128.9.216.61|128.9.216.61]] changed it to) -- even though I think this is poorer style, we should stick with the original algorithm. '''Not an issue.''' &mdash;[[User:MattGiuca|MattGiuca]] ([[User talk:MattGiuca|talk]]) 06:22, 8 February 2011 (UTC)

* 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:

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)

== Algorithm is still broken ==

There are two issues :

1. The conditions on the branches (below) are strictly opposite:

<pre>

if (v'.index is undefined) // Was successor v' visited?

tarjan(v') // Recurse

v.lowlink = min(v.lowlink, v'.lowlink)

else if (v' is in S) // Was successor v' in stack S?

v.lowlink = min(v.lowlink, v'.index ) //v' is in stack but it isn't in the dfs tree

</pre>

that is because the only region where we modify .index and push into S is the following:

<pre>

v.index = index // Set the depth index for v

v.lowlink = index

index = index + 1

S.push(v)

</pre>

Which prooves that outside this region the following holds:

<pre>

bool(v'.index is undefined) != bool(v' is in S)

</pre>

Therefore in *any* case exactly one branch will be executed and therefore the whole block could be simplyfied by:

<pre>

if (v'.index is undefined) // Was successor v' visited?

tarjan(v') // Recurse

v.lowlink = min(v.lowlink, v'.lowlink)

</pre>

* The above analysis is incorrect. You are assuming that nothing ever gets popped off the stack. Note that nodes which are identified as SCC roots are popped off the stack ''during the algorithm''. Therefore, once a complete SCC has been identified, all of the nodes in that SCC are a) already visited (have an index), and b) not on the stack. Thus, there is a third (implicit) "else" branch which does nothing -- that is for the case where a node's successor is already in an SCC which is already complete, and therefore it cannot possibly include the current node, so it is safe to ignore it. '''Do not make the above change'''. &mdash;[[User:MattGiuca|MattGiuca]] ([[User talk:MattGiuca|talk]]) 06:30, 8 February 2011 (UTC)

2. The SCC printed at the end is incorrect because algorithm never pops out nodes. Imagine the SCC is found for the last sucessor of v. In that case *every* sucessor will be printed, which is clearly not correct.

Anonymous - 18:16, 16 june 2010 <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/145.248.195.1|145.248.195.1]] ([[User talk:145.248.195.1|talk]]) </span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

* Again, this misses the point that nodes are popped '''during''' the algorithm, '''not''' at the end. There is not just a single SCC identified; this identifies all of them. This does correctly pop nodes once an SCC is found (and as far as I can tell did also at the date of the comment). &mdash;[[User:MattGiuca|MattGiuca]] ([[User talk:MattGiuca|talk]]) 06:30, 8 February 2011 (UTC)

== Algorithm fixed ==

Line 115 ⟶ 55:

(The "forall (v, v') loop is not executed). It results in such a node to be always reported as strongly connected root, while in my understanding it can't be. <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/90.80.39.42|90.80.39.42]] ([[User talk:90.80.39.42|talk]]) 10:50, 10 December 2009 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

If v'.index undefined then call Tarjan,

then v'.index = v'.lowlink = 0;

they cannot change since there will not be any lowlink < 0.

So the first vertex will always result to belong to the strongly connected component.

The algorithm is not fixed :-(

Ok, I'll work on it and I'll give you the right pseudocode.

You make me waste my time. [[User:Jimifiki|Jimifiki]] ([[User talk:Jimifiki|talk]]) 12:17, 21 March 2010 (UTC) <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/89.226.101.99|89.226.101.99]] ([[User talk:89.226.101.99|talk]]) 11:26, 21 March 2010 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

* The algorithm is correct in this regard. A node without a successor ''is'' always a SCC root. By definition, it forms its own single-node SCC, because it is not part of any loops. (In other words, it is like a leaf of a tree.) As for "the first vertex will always result to belong to the strongly connected component" -- yes, this is also true. ''All'' vertices belong to some SCC, it is just a matter of which. The first vertex is always the root of some SCC. The root of an SCC is defined as the node with the lowest index in the SCC, so the node with index 0 will always be the root of whichever SCC it ends up inside of. '''None of the above comments are issues with the algorithm''' &mdash;[[User:MattGiuca|MattGiuca]] ([[User talk:MattGiuca|talk]]) 06:35, 8 February 2011 (UTC)

==Algorithm Fixed==

Ok, I worked on it!!

In my opinion the pseudocode is wrong. The right order when calling Tarjan is:

v.index = index;

index = index + 1;

v.lowindex = index;

then the law to update v.lowindex is

v.lowindex <- min(v'.lowindex, v'.index, v.lowindex);

What you have as result is that

# All the vertices such that v.index >= v.lowindex belong to the Scc,

# All the vertices such that v.index = v.lowindex are root of a Scc

# All the vertices such that v.index < v.lowindex belong to the tree part of the graph.

I hope my modifications respect the original Tarjan algorithm,

please proove all my claims before copying them on the main page.

Remark that my modifications answer to the Node-without-successor problem above mentioned :-)

* I don't see why you should set v.lowindex to v.index + 1. (By lowindex do you mean lowlink?) The lowlink is the index of the lowest-known root in the current node's SCC, which is initially assumed to be ''this'' node, not the ''next'' node. It ''is'' the case that "All the vertices such that v.index = v.lowlink are root of a Scc", but it is ''not'' the case that "All the vertices such that v.index >= v.lowlink belong to the Scc" -- rather, I would say that all the vertices with v.index > v.lowlink belong to ''some'' SCC, and are not the root of it. There *are* no vertices with v.index < v.lowlink -- the min checks ensure that no vertex has a lowlink greater than its own index. There is also no "tree part of the graph" -- every node belongs to an SCC (though nodes which are not involved in cycles form a single-node SCC). Therefore these modifications are not useful. '''Not an issue''' &mdash;[[User:MattGiuca|MattGiuca]] ([[User talk:MattGiuca|talk]]) 06:58, 8 February 2011 (UTC)

== Counterexample ==

<code>

<pre>

node size : 12

map :

0 0 0 0 0 0 0 0 0 1 0 0

0 0 0 0 0 0 0 0 1 0 0 0

0 0 0 0 0 0 0 1 0 0 0 0

0 0 0 0 0 0 1 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 1

0 0 0 0 0 0 0 0 0 0 1 0

0 1 1 0 0 0 0 0 0 0 0 0

1 0 0 0 1 0 0 0 0 0 0 0

1 0 1 0 1 0 0 0 0 0 0 0

0 0 0 0 0 1 0 0 0 0 0 0

0 1 1 0 0 0 0 0 0 0 0 0

0 0 0 1 0 0 0 0 0 0 0 0

</pre></code>

In this case the whole graph is strongly connected

But the result of algorithm is not <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/119.202.92.81|119.202.92.81]] ([[User talk:119.202.92.81|talk]]) 07:58, 23 October 2010 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

* What output did the algorithm give you? I ported the algorithm to Python and ran it on precisely this input, assuming your adjacency matrix rows are sources and columns are sinks, and naming each vertex after its row/column ID starting from 0. The output I got was a single SCC: "6 3 11 4 7 2 8 1 10 5 9 0". I don't think this is a valid counterexample. '''Not an issue''' &mdash;[[User:MattGiuca|MattGiuca]] ([[User talk:MattGiuca|talk]]) 05:34, 8 February 2011 (UTC)

== Status of the algorithm ==

After seeing the large number of bug discussions on this page, I thought it would be prudent to put up a dispute-section template on that page. I intend to address each of the above concerns. Can anybody who is more of an expert in the field check that the algorithm is correct so we can remove the box? I have ported it to Python and it seems to be working okay. &mdash;[[User:MattGiuca|MattGiuca]] ([[User talk:MattGiuca|talk]]) 05:37, 8 February 2011 (UTC)

* 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.

For reference, the exact algorithm as listed in Tarjan, ''Depth-first search and linear graph algorithms'':

BEGIN

INTEGER i;

PROCEDURE STRONGCONNECT (v);

BEGIN

LOWLINK (v) := NUMBER (v) := i := i + 1;

put v on stack of points;

FOR w in the adjacency list of v DO

BEGIN

IF w is not yet numbered THEN

BEGIN comment (v, w) is a tree arc;

STRONGCONNECT (w);

LOWLINK (v) := min (LOWLINK (v), LOWLINK (w));

END

ELSE IF NUMBER (w) < NUMBER (v) DO

BEGIN comment (v, w) is a frond or cross-link;

if w is on stack of points THEN

LOWLINK (v) := min (LOWLINK (v), NUMBER (w));

END;

END;

If (LOWLINK (v) = NUMBER (v)) THEN

BEGIN comment v is the root of a component;

start new strongly connected component;

WHILE w on top of point stack satisfies NUMBER (w) >= NUMBER (v) DO

delete w from point stack and put w in current component

END;

END;

i := 0;

empty stack of points;

FOR w a vertex IF w is not yet numbered THEN STRONGCONNECT (w);

END;

&mdash;[[User:MattGiuca|MattGiuca]] ([[User talk:MattGiuca|talk]]) 10:36, 8 February 2011 (UTC)

== Where to store "lowlink" ==

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. &mdash;[[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)

== 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)