9

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

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

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

4

2 回答 2

8

据我所知不是。您必须编写一个图形遍历函数。

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

然后枚举图中的所有节点。在这种情况下，显而易见的方法是遍历有限映射中的图形收集节点（请参阅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。 多亏了惰性评估，这才做对了。

编辑：代码现在经过测试并略微扩展。

于 2008-12-28T07:02:47.030 回答
2

是和不是。它可以通过你的节点类型结构的领域知识和定义一些你可以测试的平等概念，结合迄今为止看到的节点列表或映射来恢复共享来完成。在病理情况下，GHC 中有一个 StableName 的概念来构建这样的概念。

在另一个方面，Matt Morrow 一直在做一些工作，使用他方便的真空库以汇编语言 .S 文件的形式提取任意循环数据。因此，无论是那个还是真空可能都适合您的需求。

一般来说，避免目前在地图中看到的巫毒和跟踪节点可能是最合理和可维护的解决方案。

于 2009-09-11T17:25:39.633 回答