Wie wird 'Übereinstimmung' in Haskells FGL als O (1) implementiert?

Question

In Haskell Functional Graph Library (FGL), hängen die meisten der Graphenalgorithmen auf die Funktion 'Spiel', die eine Node n gegeben, und eine Graph g, kehrt c & g', wo c die Context des n ist, und g' ist der Rest des Graphen (der keine Verweise auf n enthält).

Der einzige Weg, die ich sehen kann, dies zu tun ist in g jeder der Kontexte untersuchen und alle Kanten zu entfernen, die zu n beziehen und das Hinzufügen von ihnen auf den Kontext c. Dies würde meiner Meinung nach lineare Zeit erfordern.

Martin Erwig, der die Bibliothek schrieb, schlägt in this Papier vor, dass diese Transformation in konstanter oder zumindest sublinearer Zeit durchgeführt werden kann. Kann mir jemand erklären, wie das erreicht wird?

Answer 1

match ist in der Graph typeclass definiert, daher hängt die Implementierung dieser Funktion vom Datentyp ab, der die typeclass implementiert.

Das Paket wird mit zwei Implementierungen geliefert: one using Patricia trees, one using regular trees. Sie können die Quelle für sich selbst anzeigen.

Zum Beispiel kann die Umsetzung Patricia-Baum:

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, die auf einer gegebenen Maschine mit einem Satz ganzzahlige Breite effektiv konstant ist (W).

dass So bleibt nur clearPred, clearSucc und 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 ist auch O(min(n,W)), so brauchen wir nicht darüber Sorgen zu machen. Sowohl clearSucc als auch clearPred rekursiv durch jedes Element in der Adjazenzliste, so dass O (Grad) kombiniert ist.

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

toAdj erstellt eine neue Kantenliste, die O (max (| V |, | E |)), aber diese träge aufgebaut ist, so brauchen wir nicht zu kümmern, wenn es verwendet wird.