如何在Haskell的FGL中实现"匹配"为O(1)？

Question

在Haskell的函数图像库(FGL),大部分的图形算法依赖于"匹配"功能,其中,由于一Node n和Graph g,退货c & g',其中c是Context的n,并且g'是图的其余部分(其中包含没有引用n).

我能看到这样做的唯一方法是检查每个上下文g并删除任何引用n并将它们添加到上下文中的边c.我相信,这需要线性时间.

马丁Erwig,谁写的图书馆,表明在这个文件,这个转换可以在不断的或至少子线性时间来完成.任何人都可以向我解释这是如何实现的吗？

Answer 1

match在图类型类中定义,因此该函数的实现取决于实现类型类的数据类型.

该软件包有两个实现,一个使用Patricia树,一个使用常规树.您可以自己查看来源.

例如,Patricia树实现:

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并且delete在IntMaps上有O(min(n,W))运行时,它在具有设置整数宽度(W)的给定机器上实际上是常量.

使刚刚离开clearPred,clearSucc和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也是O(min(n,W)),所以我们不需要担心.双方clearSucc并clearPred通过在相邻列表中的每个元素递归,虽然如此,这是O(度)合并.

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

toAdj 创建一个新的边列表,即O(max(| V |,| E |)),但这是懒惰构造的,所以除非使用它,否则我们不需要担心.