11

Haskell の Functional Graph Library (FGL) では、ほとんどのグラフ アルゴリズムは'match' 関数に依存しNode nていGraph gますc & g'。）。cContextng'n

これを行う唯一の方法は、各コンテキストを調べて、g参照するエッジを削除しn、それらをコンテキストに追加することcです。これには直線的な時間がかかると思います。

ライブラリを作成した Martin Erwig は、この論文で、この変換は一定時間または少なくとも準線形時間で実行できることを示唆しています。これがどのように達成されるかを誰かに説明できますか?

4

1 に答える 1

7

matchはGraph型クラスで定義されているため、その関数の実装は型クラスを実装するデータ型に依存します。

パッケージには 2 つの実装が付属しています。1 つはパトリシア ツリーを使用し、もう 1 つは通常のツリーを使用します。いずれかのソースを自分で表示できます。

たとえば、パトリシア ツリーの実装は次のとおりです。

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およびdeleteIntMaps には O(min(n,W)) runtimeがあり、これは、設定された整数幅 ( ) を持つ特定のマシン上で実質的に一定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を再帰するため、O(degree) を組み合わせたものになります。clearPred

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

toAdjO(max(|V|,|E|)) である新しいエッジ リストを作成しますが、これは遅延構築されるため、使用されない限り、これについて心配する必要はありません。

于 2013-08-03T19:04:59.733 に答える