3
$\begingroup$

Below is Tarjan's SCC algorithm as described in wikipedia.

Input: Graph G = (V, E)

1.  index = 0                                         // DFS node number counter 
2.  S = empty                                         // An empty stack of nodes 
3.  for all v in V do 
4.   if (v.index is undefined)                       // Start a DFS at each node 
5.     tarjan(v)                                     // we haven't visited yet 

6.  procedure tarjan(v) 
7.   v.index = index                                 // Set the depth index for v 
8.   v.lowlink = index                               
9.   index = index + 1 
10.  S.push(v)                                       // Push v on the stack 
11.  for all (v, v') in E do                         // Consider successors of v 
12.    if (v'.index is undefined)                    // Was successor v' visited? 
13.        tarjan(v')                                // Recurse 
14.        v.lowlink = min(v.lowlink, v'.lowlink) 
15.    else if (v' is in S)                          // Was successor v' in stack S? 
16.        v.lowlink = min(v.lowlink, v'.index)      // v' is in stack but it isn't in the dfs tree 
17.  if (v.lowlink == v.index)                       // Is v the root of an SCC? 
18.    print "SCC:" 
19.    repeat 
20.      v' = S.pop                                   
21.      print v' 
22.    until (v' == v)

In line 16, I could not determine why I could or could not replace line 16 with that of line 14. In other words, it seems to me that taking the min(v.lowlink, v'.lowlink) is the proper approach as opposed to min(v.lowlink, v'.index) in the above example. I have seen one other example on the web that mimics the pseudocode above.

I have considered the unusual use of stack S in the algorithm above in which S may contain items from previous "dead" stack frames. These leftover items aren't removed because they are not the roots of their own strongly connected component.

$\endgroup$
  • $\begingroup$ Implementation and programming questions like this are more appropriate for StackOverflow, this site is for theoretical computer science questions. I also don't see a question in this post. Voting to close as off-topic. $\endgroup$ – Kaveh Nov 16 '10 at 4:24
  • $\begingroup$ I have to agree... I can't find anything concrete in the question that asks about the concepts of the algorithm itself. Instead, just questions about/problems with the implementation... You should consider StackOverflow $\endgroup$ – Daniel Apon Nov 16 '10 at 4:35
  • $\begingroup$ If I understand him correctly, he's unsure if line 16 is correct. That is, he wants to know if one shouldn't put v'.lowlink instead of v'.index for the algorithm to be correct. $\endgroup$ – Michael Nov 16 '10 at 5:24
  • $\begingroup$ @Michael: I don't think that is a theoretical computer science question (let alone a research-level one, it can be answered by looking at the proof of correctness of the algorithm in textbooks on graph algorithms). $\endgroup$ – Kaveh Nov 16 '10 at 5:48
  • 2
    $\begingroup$ @Michael: I understand that you want to help, and proving correctness of algorithms (not implementations) can count as theoretical computer science, but answering this kind of questions can have a longer term effect on the level of question posted on the site. (ps: I am not saying this is not worthy of answering, just saying this is not the right place for this question and StackOverflow is more suitable for it, please see the discussions on the meta about homework questions to understand my point.) $\endgroup$ – Kaveh Nov 16 '10 at 5:54
1
$\begingroup$

v.lowlink = min(v.lowlink, v'.index) in line 16 is indeed correct. For a full proof you can consult Tarjan's original paper which can also be found here.

Robert Tarjan: Depth-first search and linear graph algorithms. In: SIAM Journal on Computing. Vol. 1 (1972), No. 2, P. 146-160.

Completely unrelated to the question, there is an amusing 1983 retrospective by Bob Tarjan here on the paper cited above.

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.