Enregistrement de graphiques dans Haskell

Question

Je peux facilement définir un type de données pour un noeud d'un graphe orienté. Je peux sauvegarder le graphique dans un fichier en utilisant la fonction show, puis le restaurer en utilisant read. Cependant, show ne fera pas face à un cycle. Existe-t-il un moyen trivial d'enregistrer et de restaurer un graphique?

Answer 1

Pas aussi loin que je sache. Vous devez écrire une fonction de déplacement de graphique.

D'abord, décidez où casser la circularité. Dans ce cas, c'est trivial: utilisez les noms des nœuds (en supposant qu'ils soient uniques dans un graphique). Pour une structure plus complexe, telle qu'un graphe avec des noeuds et des arêtes en tant que types distincts, vous devez décider si vous souhaitez stocker des arêtes avec des noeuds, des noeuds avec des arêtes ou bien séparer les noeuds et les arêtes.

Ensuite, énumérer tous les nœuds dans le graphique. Dans ce cas, la manière évidente consiste à parcourir les nœuds de collecte de graphe dans une carte finie (voir Data.Map). Ensuite, stockez chaque noeud sous un nom suivi d'une liste d'autres noms de noeud. Récupérer le graphique signifie utiliser le motif "attacher le noeud". Lit 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: appelle la table makeNode, qui appelle FindNode, qui appelle table. Thanks to lazy evaluation this does the Right Thing.

Modifier: code maintenant testé et légèrement élargi.

Answer 2

Oui et non. Cela peut se faire via la connaissance du domaine de la structure de votre type de nœud et en définissant une notion d'égalité que vous pouvez tester, combinée à une liste ou une carte des nœuds vus jusqu'à présent pour récupérer le partage. Dans le cas pathologique, il existe une notion de StableName dans GHC pour construire une telle notion. Sur un autre front Matt Morrow a fait un certain travail pour extraire sous la forme d'un fichier .S en langage assembleur, des données cycliques arbitraires en utilisant sa bibliothèque de vide pratique. Donc, soit cela ou l'aspirateur pourrait convenir à vos besoins.

En général, l'évitement du vaudou et des nœuds de suivi visibles jusqu'à présent dans une carte est probablement la solution la plus rationnelle et la plus facile à maintenir.