Union findet in einer Graphenstruktur

Question

Ich habe einen Rekord ein Diagramm als Sätze von Knoten und Kanten beschreiben:

data MyGraph a = MyGraph { 
    nodes :: Set a, 
    edges :: Set (a,a), 
    components :: UnionFindM a -- ? 
} 
emptyGraph = MyGraph{ 
    nodes = empty, edges = empty, 
    components = emptyUnionFind singleton union --? 
} 
addEdge g (a,b) = g{ 
    edges = (a,b) `insert` (edges g), 
    components = (components g) >>= (equate a b) -- ? 
} 

Da ich nicht immer Kanten entfernen werde, möchte ich die angeschlossenen Komponenten verfolgen eine Vereinigung mit -Findung der Struktur (die ich beim Hinzufügen einer Kante leicht aktualisieren könnte), weil ich die verbundenen Komponenten überlagern möchte, also wäre es nützlich, sie auch als eine Menge von Mengen zu behalten. Und natürlich möchte ich die Komponente für einen Knoten bekommen.

Ich fand die equivalence Bibliothek, die ich wählte, weil ich nicht sehen kann, wie ich Sets mit union-find und persistent-equivalence erstellen würde, muss den Wertebereich kennen.

Jetzt kann ich Beziehungen erstellen, und gibt den Satz der Sätze mit:

import Control.Monad(liftM) 
import Data.Equivalence.Monad 
import Data.Set(singleton, union, fromList) 
f = runEquivM singleton union $ do 
    equate "foo" "bar" 
    equate "bar" "baz" 
    (liftM fromList) $ mapM classDesc ["foo","bar","baz","one","two"] 

>>> f 
fromList [fromList ["bar","baz","foo"],fromList ["one"],fromList ["two"]] 

Aber: mit fromList sehr naiv ist, sollte es möglich sein, alle Äquivalenzklassen von der internen Datenstruktur direkt zu erhalten.

Und noch wichtiger: Wie kann ich die Äquivalenzrelation in meiner Datenstruktur speichern?

Answer 1

Eine Option wäre Data.Equivalence.Persistent

data MyGraph a = MyGraph { 
    nodes :: Set a, 
    edges :: Set (a,a), 
    components :: Equivalence a 
} 
emptyGraph :: Ix a => (a, a) -> MyGraph a 
emptyGraph range = MyGraph{ 
    nodes = empty, edges = empty, 
    components = emptyEquivalence range 
} 
addEdge :: Ix a => MyGraph a -> (a, a) -> MyGraph a 
addEdge g (a,b) = g{ 
    edges = (a,b) `insert` (edges g), 
    components = equate a b (components g) 
} 

ich die Verwendung von Ix ein wenig ärgerlich finden Sie hier zu verwenden, aber wenn es für Ihre Zwecke dann gehen mit ihr arbeitet. Union-find persistent zu machen ist eine großartige Idee von Conchon untersucht, die auch eine Implementierung enthält, die in Coq korrekt ist. Wenn Sie Reverse-Differenz-Arrays verwenden, erhalten Sie im Grunde persistente Arrays, die die Leistung von linearen Arrays a la Clean haben, aber sie auf eine dauerhafte Art und Weise auf Kosten der logarithmischen Verlangsamung verwenden können. So sind sie geeignet, Dinge zu implementieren, die eine Menge funktionaler Nebenwirkungen beinhalten.