Talk:Tarjan's strongly connected components algorithm

Mathematics Start‑class Low‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
Start	This article has been rated as Start-class on Wikipedia's content assessment scale.
Low	This article has been rated as Low-priority on the project's priority scale.

Pseudocode is not good

In this reference web.cecs.pdx.edu we see that TarjanDfs is called not only for first node v0, but all nodes that are not visited. This should be fixed, I am not expert, but here is suggestion.

index = 0                       // DFS node number counter 
S = empty                       // An empty stack of nodes
for each vertex v
 if v.index is undefined
  tarjan(v)                      // Start a DFS at the non-visited node

--211.25.51.200 (talk) 07:05, 23 April 2008 (UTC)[reply]

Bug in second subcase

Seems to me that the second update case is wrong:

Instead of

   if (v'.index is undefined)  // Was successor v' visited? 
     tarjan(v')                // Recurse
     v.lowlink = min(v.lowlink, v'.lowlink)
   elseif (v' in S)            // Is v' on the stack?
     v.lowlink = min(v.lowlink, v'.lowlink)

shouldn't it be

   if (v'.index is undefined)  // Was successor v' visited? 
     tarjan(v')                // Recurse
     v.lowlink = min(v.lowlink, v'.lowlink)
   elseif (v' in S)            // Is v' on the stack?
     v.lowlink = min(v.lowlink, v'.index)

--128.9.216.61 (talk) 19:11, 6 January 2009 (UTC)[reply]

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. —Preceding unsigned comment added by 192.35.241.121 (talk) 17:55, 4 August 2009 (UTC)[reply]

Algorithm is still broken

There are two issues :

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

    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

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

  v.index = index                                 // Set the depth index for v
  v.lowlink = index
  index = index + 1
  S.push(v)

Which prooves that outside this region the following holds:

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

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

    if (v'.index is undefined)                    // Was successor v' visited?
        tarjan(v')                                // Recurse
    v.lowlink = min(v.lowlink, v'.lowlink)

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 —Preceding unsigned comment added by 145.248.195.1 (talk)

Algorithm fixed

I've fixed the algorithm, it should make much more sense now. I hope there aren't any more bugs. 70.68.114.213 (talk) 02:40, 31 January 2009 (UTC)[reply]

Node with no successor

Isn't there an issue for node that have no successor ? In that case, the main procedure can be seen like :

  v.index = index                 // Set the depth index for v
  v.lowlink = index
  index = index + 1
  S.push(v)                       // Push v on the stack
  if (v.lowlink == v.index)       // Is v the root of an SCC?
    print "SCC:"
    repeat
      v' = S.pop
      print v'
    until (v' == v)

(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. —Preceding unsigned comment added by 90.80.39.42 (talk) 10:50, 10 December 2009 (UTC)[reply]

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. Jimifiki (talk) 12:17, 21 March 2010 (UTC) —Preceding unsigned comment added by 89.226.101.99 (talk) 11:26, 21 March 2010 (UTC)[reply]

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 1) All the vertices such that v.index >= v.lowindex belong to the Scc, 2) All the vertices such that v.index = v.lowindex are root of a Scc 3) 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 :-)

Counterexample

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

In this case the whole graph is strongly connected

But the result of algorithm is not —Preceding unsigned comment added by 119.202.92.81 (talk) 07:58, 23 October 2010 (UTC)[reply]