Unión-encontrar en una estructura gráfica

Question

Tengo un registro que describe un gráfico como conjuntos de nodos y bordes:

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

Ya que no volverá a eliminar los bordes, quiero realizar un seguimiento de los componentes conectados mediante una unión -find structure (que podría actualizar fácilmente cuando agregue un borde), porque quiero mapear sobre los componentes conectados, por lo que sería útil mantenerlos como un conjunto de conjuntos, también. Y, por supuesto, quiero obtener el componente para un nodo.

Encontré la biblioteca equivalence, que elegí porque no puedo ver cómo crearía conjuntos con union-find y persistent-equivalence necesita conocer el rango de valores.

Ahora puedo crear relaciones, y devolver el conjunto de conjuntos usando:

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

Pero: el uso de fromList es muy ingenua, debería ser posible conseguir todas las clases de equivalencia de la estructura interna de datos directamente.

Y, más importante aún, ¿cómo puedo almacenar la relación de equivalencia en mi estructura de datos?

Answer 1

Una opción sería utilizar 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) 
} 

Me parece que el uso de Ix un poco molesto aquí, pero si funciona para sus propósitos y luego ir con él. Hacer que la búsqueda de unión sea persistente es una idea increíble explorada por Conchon que también incluye una implementación probada correcta en Coq. Básicamente, si utiliza arrays de diferencias inversas, obtendrá matrices persistentes que tienen el rendimiento de matrices lineales a la Clean, pero pueden usarlas de forma persistente a costa de la reducción logarítmica. Por lo tanto, son adecuados para implementar cosas de unión-unión que implican muchos efectos secundarios imperativos de una manera puramente funcional.