How is 'match' implemented in Haskell's FGL to be O(1)?

Question

In Haskell's Functional Graph Library (FGL), most of the graph algorithms depend on the 'match' function, which, given a Node n and a Graph g, returns c & g', where c is the Context of the n, and g' is the rest of the graph (which contains no references to n).

The only way I can see of doing this is be examining each of the contexts in g and removing any edges which refer to n and adding them to the context c. This would take linear time, I believe.

Martin Erwig, who wrote the library, suggests in this paper that this transformation can be done in constant or at least sub-linear time. Can anyone explain to me how this is accomplished?

Answer 1

match is defined in the Graph typeclass, so the implementation of that function depends on the datatype that implements the typeclass.

The package comes with two implementations, one using Patricia trees, one using regular trees. You can view the source for either yourself.

For example, the Patricia tree implementation:

import           Data.Graph.Inductive.Graph
import           Data.IntMap (IntMap)
import qualified Data.IntMap as IM
import           Data.List
import           Data.Maybe
import           Control.Arrow(second)


newtype Gr a b = Gr (GraphRep a b)

type GraphRep a b = IntMap (Context' a b)
type Context' a b = (IntMap [b], a, IntMap [b])

type UGr = Gr () ()


instance Graph Gr where
    -- ...
    match           = matchGr
    -- ...

matchGr :: Node -> Gr a b -> Decomp Gr a b
matchGr node (Gr g)
    = case IM.lookup node g of
        Nothing
            -> (Nothing, Gr g)

        Just (p, label, s)
            -> let !g1 = IM.delete node g
                   !p' = IM.delete node p
                   !s' = IM.delete node s
                   !g2 = clearPred g1 node (IM.keys s')
                   !g3 = clearSucc g2 node (IM.keys p')
               in
                 (Just (toAdj p', node, label, toAdj s), Gr g3)

lookup and delete on IntMaps have O(min(n,W)) runtime, which is effectively constant on a given machine with a set integer width (W).

So that just leaves clearPred, clearSucc, and toAdj:

clearSucc :: GraphRep a b -> Node -> [Node] -> GraphRep a b
clearSucc g _ []       = g
clearSucc g v (p:rest) = clearSucc g' v rest
    where
      g' = IM.adjust f p g
      f (ps, l, ss) = (ps, l, IM.delete v ss)


clearPred :: GraphRep a b -> Node -> [Node] -> GraphRep a b
clearPred g _ []       = g
clearPred g v (s:rest) = clearPred g' v rest
    where
      g' = IM.adjust f s g
      f (ps, l, ss) = (IM.delete v ps, l, ss)

adjust is also O(min(n,W)), so we don't need to worry about that. Both clearSucc and clearPred recurse through each element in the adjacency list, though, so that's O(degree) combined.

toAdj :: IntMap [b] -> Adj b
toAdj = concatMap expand . IM.toList
  where
    expand (n,ls) = map (flip (,) n) ls

toAdj creates a new edge list, which is O(max(|V|,|E|)), but this is constructed lazily, so we don't need to worry about this unless it's used.