Sauvegarde des graphiques dans Haskell

Question

Je peux facilement définir un type de données pour un noeud d'un graphe orienté.

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

Je peux enregistrer le graphique dans un fichier en utilisant la fonction show, puis restaurer à l'aide de lire. Cependant, spectacle ne sera pas faire face à un cycle. Yat-il un moyen trivial de sauvegarder et de restaurer un graphique?

Answer 1

Pas pour autant que je sais. Vous devez écrire une fonction graphique traversant.

Tout d'abord, décider où briser la circularité. Dans ce cas, il est trivial: utiliser les noms de noeud (en supposant qu'ils sont uniques dans un graphique). Pour une structure plus complexe, comme un graphique avec des noeuds et des arêtes comme des types séparés, vous devez décider de stocker des bords avec des noeuds, des noeuds avec des arêtes, ou garder des noeuds et des arêtes complètement séparés.

énumérer ensuite tous les noeuds du graphique. Dans ce cas, la manière évidente consiste à parcourir le graphe de collecte des noeuds dans une carte finie (voir Data.Map ). Ensuite stocker chaque noeud comme un nom suivi d'une liste d'autres noms de nœuds.

Récupérer le moyen de graphique en utilisant le modèle « attacher le noeud ». Lire le graphique stocké dans une structure de [(String, [String])]. Ensuite, le graphique original peut être reconstruit avec le code suivant:

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

Notez la récursion mutuelle: table appelle makeNode, qui appelle FindNode, qui appelle table. Merci à l'évaluation paresseuse ce fait la bonne chose .

Edit: Code maintenant testé et légèrement élargi

.

Answer 2

Oui et non. Il peut se faire via la connaissance du domaine de la structure de votre type de nœud et de définir une notion d'égalité que vous pouvez tester, combinée à une liste ou une carte des noeuds vus jusqu'à présent pour récupérer le partage. Dans le cas pathologique il y a une notion de StableName dans GHC pour construire une telle notion.

Sur un autre front Matt Morrow a fait un travail pour extraire sous la forme d'un fichier .S de langage d'assemblage, les données cycliques arbitraires en utilisant sa bibliothèque sous vide à portée de main. Donc, ça ou vide pourrait répondre à vos besoins.

En général évitant les nœuds vaudous et de suivi vu jusqu'à présent dans une carte est probablement la solution la plus rationnelle et maintenable.