在Haskell中保存图形

我可以轻松地为有向图的节点定义数据类型.

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

我可以使用show函数将图形保存到文件中,然后使用read恢复它.但是,节目不会应付一个周期.是否有一种保存和恢复图形的简单方法？

不是我所知道的.你必须编写一个图遍历函数.

首先,决定在哪里打破循环.在这种情况下,它是微不足道的:使用节点名称(假设它们在图形中是唯一的).对于更复杂的结构,例如将节点和边作为单独类型的图,您必须决定是否存储具有节点的边,具有边的节点,还是保持节点和边完全分离.

然后枚举图中的所有节点.在这种情况下,显而易见的方法是遍历有限映射中的图形采集节点(参见Data.Map).然后将每个节点存储为名称,后跟其他节点名称列表.

恢复图表意味着使用"打结"模式.将存储的图形读入[[String,[String])]的结构中.然后可以使用以下代码重建原始图形:

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

注意相互递归:table调用makeNode,它调用findNode,调用table. 感谢懒惰的评价,这就是正确的事情.

编辑:代码现已测试并略有扩展.