Tarjan's Strongly Connected Component algorithm

Question

I am trying to understand Tarjan's strongly connected component algorithm and I have a few questions (the line numbers I am referring to are from Algoritmy.net):

1. On line 33 why is node.lowlink = min(node.lowlink, n.index) — shouldn't it be same as line 31: node.lowlink = min(node.lowlink, **n.lowlink**)?

2. Do we have to generate the components on line 40 in the while loop as we pop? Isn't it true that when the algorithm finishes, all the vertices grouped by lowLink should be the SCC?

3. Is it ever true that after we recurse in line 30, n may not be in stack? If not and (1) is true we can simplify line 29-33 as follows:

   if n.index == -1 
      tarjanAlgorithm(n, scc, s, index)
   if stack.contains(n)
      node.lowlink = min(node.lowlink, n.lowlink)
   

4. I went ahead and implemented the algorithm in Scala. However, I dislike the code - it is very imperative/procedural with lots of mutating states and book-keeping indices. Is there a more "functional" version of the algorithm? I believe imperative versions of algorithms hide the core ideas behind the algorithm unlike the functional versions. I found someone else encountering the same problem with this particular algorithm but I have not been able to translate his Clojure code into idomatic Scala.

Note: If anyone wants to experiment, I have a good setup that generates random graphs and tests your SCC algorithm vs running Floyd-Warshall

Here is the full pseudocode (© Algoritmy.net, MIT licensed).

index = 0

/*
* Runs Tarjan's algorithm
* @param g graph, in which the SCC search will be performed
* @return list of components
*/
List executeTarjan(Graph g)
Stack s = {}
List scc = {} //list of strongly connected components
for Node node in g
if (v.index is undefined)
tarjanAlgorithm(node, scc, s)

return scc

/*
* Tarjan's algorithm
* @param node processed node
* @param SCC list of strongly connected components
* @param s stack
*/
procedure tarjanAlgorithm(Node node, List scc, Stack s)
v.index = index
v.lowlink = index
index++
s.push(node) //add to the stack
for each Node n in Adj(node) do //for all descendants
if n.index == -1 //if the node was not discovered yet                  // <--- line 29
tarjanAlgorithm(n, scc, s, index) //search
node.lowlink = min(node.lowlink, n.lowlink) //modify parent's lowlink  // <--- line 31
else if stack.contains(n) //if the component was not closed yet
node.lowlink = min(node.lowlink, n.index) //modify parents lowlink     // <--- line 33

if node.lowlink == node.index //if we are in the root of the component
Node n = null
List component //list of nodes contained in the component
do
n = stack.pop() //pop a node from the stack
component.add(n) //and add it to the component                         // <--- line 40
while(n != v) //while we are not in the root
scc.add(component) //add the compoennt to the SCC list

Answer 1

1... On line 33 why is node.lowlink = min(node.lowlink, n.index) — shouldn't it be same as line 31: node.lowlink = min(node.lowlink, n.lowlink)?

The code works either way. The two possibilities are:

I. n.index == node.index, which means the assignment will never change the value of node.lowlink, or

II. n.index < node.index, which means setting node.lowlink to either n.index or n.lowlink will cause node.index to be unequal to node.lowlink, guaranteeing that node will be part of the SCC containing everything on the stack back to the node with an index matching n.lowlink.

2... Do we have to generate the components on line 40 in the while loop as we pop? Isn't it true that when the algorithm finishes, all the vertices grouped by lowLink should be the SCC?

No, that's not true. The components of any particular SCC are not guaranteed to have the same .lowlink value, so you can't partition the vertices into SCCs that way. The .lowlink values are used to determine when to pop the stack; the stack determines what is in an SCC.

3... Is it ever true that after we recurse in line 30, n may not be in stack?

Yes, n may not be in the stack. n could be a vertex belonging to a previously identified SCC. There's a forward link to n obviously but there may be no back link from n or its SCC to the current SCC.