11

在 Haskell 的函数图库 (FGL) 中，大多数图算法依赖于“匹配”函数，给定a和a Node n，该函数Graph g返回）。c & g'cContextng'n

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

编写该库的 Martin Erwig 在本文中建议，这种转换可以在恒定或至少亚线性时间内完成。谁能向我解释这是如何完成的？

4

1 回答 1

7

match在Graph类型类中定义，因此该函数的实现取决于实现该类型类的数据类型。

该软件包有两种实现，一种使用 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(degree) 的组合。

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

toAdj创建一个新的边列表，即 O(max(|V|,|E|))，但这是延迟构造的，因此除非使用它，否则我们无需担心。

于 2013-08-03T19:04:59.733 回答