Как "матч" реализован в Haskell FGL как O (1)?

В функциональной библиотеке Haskell (FGL) большинство алгоритмов графа зависят от функции "match", которая при заданных Node n и a Graph g возвращает c & g', где c является Context n, а g' - остальная часть графика (в котором нет ссылок на n).

Единственный способ, которым я могу это сделать, - изучить каждый из контекстов в g и удалить любые ребра, относящиеся к n, и добавить их в контекст c. Полагаю, это займет линейное время.

Мартин Эрвиг, который написал библиотеку, предлагает в эту бумагу, что это преобразование может быть выполнено в постоянном или, по крайней мере, подлинейном времени, Может ли кто-нибудь объяснить мне, как это делается?

Ответы

Ответ 1

match определяется в Graph typeclass, поэтому реализация этой функции зависит от типа данных, который реализует класс типов.

Пакет поставляется с двумя реализациями: один с использованием деревьев Patricia, one используя регулярные деревья. Вы можете просмотреть источник для себя.

Например, реализация дерева Патрисии:

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 |)), но это построено лениво, поэтому нам не нужно беспокоиться об этом, если оно не используется.