Guardar gráficos en Haskell

Question

I puede definir fácilmente un tipo de datos para un nodo de un grafo dirigido.

data Node = Node String [Node] derving (Show, Read)

Puedo guardar el gráfico en un archivo utilizando la función de demostración, a continuación, restaurarla utilizando la lectura. Sin embargo, la demostración no hacer frente a un ciclo. ¿Hay una manera trivial para guardar y restaurar un gráfico?

Answer 1

No es por lo que yo sé. Usted tiene que escribir una función de gráfico de travesía.

En primer lugar, decidir dónde romper la circularidad. En este caso es trivial: utilizar los nombres de nodo (suponiendo que son únicos dentro de un gráfico). Para una estructura más compleja, como un gráfico con nodos y bordes como tipos separados, que tendría que decidir si desea almacenar los bordes con los nodos, los nodos con los bordes, o mantener los nodos y los bordes completamente separados.

A continuación, enumerar todos los nodos en el gráfico. En este caso la forma obvia es que atravesar el gráfico de la recogida de los nodos en un mapa finito (ver Data.Map ). Entonces almacenar cada nodo como un nombre seguido por una lista de otros nombres de nodo.

Recuperación de los medios de gráfico usando el patrón "atar el nudo". Leer el gráfico almacenado en una estructura de [(String, [String])]. A continuación, el gráfico original puede ser reconstruido con el código siguiente:

import qualified Data.Map as M

data Node = Node String [Node]

instance Show Node where
   show (Node name others) = "Node " ++ show name ++ 
         " " ++ show (map nodeName others)
      where nodeName (Node n _) = n

restoreGraph :: [(String, [String])] -> M.Map String Node
restoreGraph pairs = table
   where
      table = M.fromList $ map makeNode pairs
      makeNode (name, others) = (name, Node name $ map findNode others)
      findNode str = fromJust $ M.lookup str table

Tenga en cuenta la recursión mutua: mesa de llama makeNode, que llama findNode, que llama a la mesa. Gracias a esta evaluación perezosa hace la cosa correcta .

Editar: código Probado y ligeramente ampliado

.

Answer 2

Sí y no. Se puede hacer a través de conocimiento del dominio de la estructura de su tipo de nodo y definir una noción de igualdad que se puede probar, junto con una lista o mapa de nodos visto hasta ahora para recuperar el compartir. En el caso patológico hay una noción de un StableName en GHC para construir tal noción.

En otro frente Matt Morrow ha estado haciendo un trabajo para extraer en forma de un archivo .S lenguaje ensamblador, los datos cíclicos arbitrarias usando su biblioteca de vacío práctico. Así que eso o de vacío podría satisfacer sus necesidades.

En general evitando los nodos de vudú y seguimiento visto hasta ahora en un mapa es probablemente la solución más racional y fácil de mantener.