SCC Gabow Style
Fists full of stacks

The plan of attack is to keep track of which vertices have been visited, when they were, and which component they belong to. We discover the components by pushing vertices to stacks when visiting and inspecting stacks when leaving. So, the stateful ingredients are:

• enter time/preorder id counter
• component counter
• path stack
• boundary stack
• table mapping \(v \mapsto pre[v]\)
• table mapping \(v \mapsto scc[v]\)
• table of edges, which says if \(u\rightarrow v\) is an edge between components in the condensation, or an edge between vertices inside a component (inside a vertex of condensation).

The core idea is that (back) edges that point from vertices with higher preorder times to lower preorder times induce cycles and cycles induce components. The boundary stack is popped until the vertex not yet assigned to a component with the lowest reachable preorder id is on top. Representative vertices are discovered by looking at the boundary stack at exit. If the vertex being exited is found to also be at the top of the boundary stack, it represents the strongly connected component containing all the path stack up to itself. This process partitions the vertices according to strongly connected components.

Here is the state data type for the haskell implementation. The scheme version just mutates local variables.

Here is a dodgy diagram I made that traces the haskell implementation. The graph (in alga notation) is \(3*1*4*1*5\).

Here is a scheme implementation I wrote while working out the haskell one. It doesn't explicitly build a condensation, only a table mapping vertices to component ids. I find it easier to follow.

(define scc
  (lambda (G)
    (let ((preorder 0)
          (component 0)
          (preorders (make-hash-table))
          (components (make-hash-table))
          (boundary '())
          (path '()))
      (define (preorder-id v)
        (hashtable-ref preorders v #f))
      (define (component-id v)
        (hashtable-ref components v #f))
      (define (set-component! v)
        (hashtable-set! components v component))
      (define (set-preorder! v)
        (hashtable-set! preorders v preorder)
        (inc! preorder))
      (define (enter v)
        (set-preorder! v)
        (push! v boundary)
        (push! v path))
      (define (pop-boundary v)
        (let ((p-v (preorder-id v)))
          (let walk ((x (pop! boundary)))
            (if (< p-v (preorder-id x))
                (walk (pop! boundary))
                (push! x boundary)))))
      (define (exit v)
        (when (= v (car boundary))
          (pop! boundary)
          (set-component! v)
          (let walk ((x (pop! path)))
            (unless (= x v)
              (set-component! x)
              (walk (pop! path))))
          (inc! component)))
      (define (dfs u)
        (enter u)
        (for-all (lambda (v)
                   (if (preorder-id v)
                       (unless (component-id v)
                         (pop-boundary v))
                       (dfs v)))
                 (adjacent u G))
        (exit u))
      (for-all (lambda (v)
                 (unless (preorder-id v)
                   (dfs v)))
               (vertex-list G))
      components)))

In the same way that the verticies are assigned to componnents, so too can edges be classified based on vertex pre-order times. The search state is augmented by including a stack of edges analogous to the path stack. On finding a vertex \(u\) which represents some SCC, edges \(v \rightarrow w\) in this edge stack are in the newly found component/vertex of the condensation exactly when minimum preorder id is greater or equal to that of \(u\), ie \[\min(pre[v],pre[w])\ge pre[u].\] The rest belong to another component. Here's the description for following out edges from the other page adapted to the edge classification point of view.

Before getting to the nitty gritty the final step is the condensing. As components or vertices of the condensation are discovered (see the horrible insertComponent function below), they are constructed and put into (yet) a(nother!) stack, \(innerGraphs\). The first draft of the implmentation used an IntMap, but this trick avoids more logs (err, yeah IntMap lookup is still pretty much log, no matter what they say)

The rest is ceremony to "coerce" the components to type NonEmpty and overlay the vertices and edges of the condensation.

condense :: Ord a => AdjacencyMap a -> StateSCC a
         -> AdjacencyMap (NonEmpty.AdjacencyMap a)
condense g (SCC _ n _ _ _ assignment inner _ outer)
  | n == 1 = vertex $ convert g
  | otherwise = gmap (\c -> inner' Array.! (n-1-c)) outer'
  where inner' = Array.listArray (0,n-1) (convert <$> inner)
        outer' = es `overlay` vs
        vs = vertices [0..n-1]
        es = edges [ (sccid x, sccid y) | (x,y) <- outer ]
        sccid v = assignment Map.! v
        convert = fromJust . NonEmpty.toNonEmpty

Here is the outer call and the hairy state data type. Since haskell map lookups cost a log, we store vertices along with their pre order id in the boundary stack to avoid that.

scc :: Ord a => AdjacencyMap a -> AdjacencyMap (NonEmpty.AdjacencyMap a)
scc g = condense g $ execState (gabowSCC g) initialState where
  initialState = SCC 0 0 [] [] Map.empty Map.empty [] [] []

data StateSCC a
  = SCC { preorder      :: {-# unpack #-} !Int
        , component     :: {-# unpack #-} !Int
        , boundaryStack :: [(Int,a)]
        , pathStack     :: [a]
        , preorders     :: Map.Map a Int
        , components    :: Map.Map a Int
        , innerGraphs   :: [AdjacencyMap a]
        , innerEdges    :: [(Int,(a,a))]
        , outerEdges    :: [(a,a)] }