Bug in Tarjan.strongconnect()

[Mykolas Mickus]

Hello,
Today I've been trying out Grph. In particular, I needed implementation of strongly connected compoents search algorithm, which this library has. Unfortunately, it has a bug inside the Tarjan.stongconnect() method. Here is the problematic code:

// Consider successors of v
for (int w : g.getOutNeighbors(v).toIntArray())
{
   if (indexes[w] == -1)
   {
      // Successor w has not yet been visited; recurse on it
      strongconnect(w, g, indexes, lowlink, stack, cycles);
      lowlink[v] = Math.min(lowlink[v], lowlink[w]);
   }
   else if (stack.contains(w))
   {
      // Successor w is in stack S and hence in the current SCC
      lowlink[v] = Math.min(lowlink[v], indexes[w]);
   }
}

Problem is that stack.contains() is a O(|N|) operation, where |N| is number of nodes in the graph. For this algorithm to have an upper bound of O(|N| + |E|) checking if a node is on stack should be O(1). I would suggest using an array of booleans or something similar for this purpose. Because at the moment implementation has complexity of O(|N|^2), which is unusable for graphs of larger sizes. Hopefully, my find will be useful.

[Luc Hogie]

Hi,

Sorry for the long delay. This clever change will be available in the next release.