haskell - 在 Haskell 中保存图表

Question

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

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

我可以使用 show 函数将图形保存到文件中，然后使用 read 恢复它。但是，显示无法应对循环。有没有简单的方法来保存和恢复图表？

Answer 1

据我所知还没有。您必须编写一个图形遍历函数。

首先，决定在哪里打破循环。在这种情况下，这很简单:使用节点名称(假设它们在图中是唯一的)。对于更复杂的结构，例如节点和边作为单独类型的图，您必须决定是存储边与节点、节点与边，还是将节点和边完全分开。

然后枚举图中的所有节点。在这种情况下，显而易见的方法是遍历图，收集有限映射中的节点(请参阅 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，makeNode 调用 findNode，后者调用 table。 Thanks to lazy evaluation this does the Right Thing .

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