在 Haskell 中保存图表

发布于 2024-07-10 02:59:15 字数 190 浏览 6 评论 0原文

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

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

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

原文

I can easily define a datatype for a node of a directed graph.

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

I can save the graph to a file using show function, then restore it using read. However, show will not cope with a cycle. Is there a trivial way to save and restore a graph?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

跨年 2024-07-17 02:59:15

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

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

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

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

Not as far as I know. You have to write a graph-traversing function.

First, decide where to break the circularity. In this case it is trivial: use the node names (assuming they are unique within a graph). For a more complex structure, such as a graph with nodes and edges as separate types, you would have to decide whether to store edges with nodes, nodes with edges, or keep nodes and edges completely separate.

Then enumerate all the nodes in the graph. In this case the obvious way is to traverse the graph collecting nodes in a finite map (see Data.Map). Then store each node as a name followed by a list of other node names.

Recovering the graph means using the "tying the knot" pattern. Read the stored graph into a structure of [(String, [String])]. Then the original graph can be reconstructed with the following code:

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

Note the mutual recursion: table calls makeNode, which calls findNode, which calls table. Thanks to lazy evaluation this does the Right Thing.

Edit: code now tested and slightly expanded.

回复收藏 0 原文