Union-trovare in una struttura di grafo

Question

Ho un record che descrive un grafico come insiemi di nodi e spigoli:

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) -- ? 
} 

Dal momento che non potrà mai rimuovere i bordi, voglio tracciare i componenti collegati tramite un sindacato -trovare la struttura (che potrei facilmente aggiornare aggiungendo un bordo), perché voglio mappare sui componenti connessi, quindi sarebbe utile mantenerli come set di set. E ovviamente voglio ottenere il componente per un nodo.

Ho trovato la libreria equivalence, che ho scelto perché non riesco a vedere come creare set con union-find e persistent-equivalence per conoscere il range di valori.

Ora posso creare delle relazioni, e restituire il set di insiemi utilizzando:

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"]] 

Ma: usando fromList è molto ingenuo, dovrebbe essere possibile ottenere tutte le classi di equivalenza dalla struttura interna di dati direttamente.

E, ancora più importante: come posso memorizzare la relazione di equivalenza nella mia struttura dati?

Answer 1

Una possibilità sarebbe quella di utilizzare 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) 
} 

Trovo l'uso di Ix un po 'fastidioso qui, ma se funziona per i vostri scopi poi andare con esso. Rendere persistente la ricerca di unione è un'idea fantastica esplorata da Conchon che include anche un'implementazione dimostrata corretta in Coq. Fondamentalmente, se si usano array di differenza inversa, si ottengono array persistenti che hanno prestazioni di array lineari a la Clean ma possono usarli in modo persistente al costo del rallentamento logaritmico. Pertanto, sono adatti per implementare le cose unione-trovare che coinvolgono un sacco di effetti collaterali imperativi in ​​modo puramente funzionale.