Salvataggio dei grafici in Haskell

Question

posso facilmente definire un tipo di dati per un nodo di un grafo orientato.

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

posso salvare il grafico in un file utilizzando la funzione spettacolo, poi ripristinarlo utilizzando leggere. Tuttavia, spettacolo non farà fronte con un ciclo. C'è un modo banale per salvare e ripristinare un grafico?

Answer 1

Non per quanto ne so. Devi scrivere una funzione grafica-attraversamento.

In primo luogo, decidere dove spezzare la circolarità. In questo caso è banale: utilizzare i nomi dei nodi (ammesso che sono unici nel grafico). Per una struttura più complessa, come ad esempio un grafico con i nodi e spigoli come tipi separati, si dovrà decidere se archiviare bordi con nodi, nodi con bordi, o tenere i nodi e spigoli completamente separati.

Poi enumerare tutti i nodi del grafo. In questo caso il modo ovvio deve traslare il grafico raccolta nodi in una mappa finita (vedi Data.Map ). Poi memorizzare ogni nodo come nome seguito da un elenco di altri nomi nodo.

Il recupero dei mezzi grafico utilizzando il "sposarsi" modello. Leggere il grafico memorizzato in una struttura di [(String, [String])]. Poi il grafico originale può essere ricostruita con il seguente codice:

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

Si noti la ricorsione mutua: tavolo chiama makeNode, che chiama findNode, che chiama tavolo. Grazie a questa valutazione pigra fa la cosa giusta .

Modifica codice Testato e leggermente ampliato

.

Answer 2

Sì e no. Esso può essere fatto tramite la conoscenza del dominio della struttura del vostro tipo di nodo e la definizione di una qualche nozione di uguaglianza che è possibile testare, in combinazione con una lista o una mappa dei nodi visto finora a recuperare la condivisione. Nel caso patologico v'è una nozione di un GHC StableName a costruire questa nozione.

Su un altro fronte Matt Morrow ha fatto qualche lavoro per estrarre sotto forma di un file .S linguaggio assembly, dati ciclici arbitrari con la sua biblioteca di vuoto a portata di mano. Quindi, o che o il vuoto potrebbe soddisfare le vostre esigenze.

In generale, evitando voodoo e tracking nodi visto finora in una mappa è probabilmente la soluzione più razionale e gestibile.