将图保存在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 

注意相互递归：表调用makeNode，它调用findNode，它调用表。 Thanks to lazy evaluation this does the Right Thing。

编辑：代码现在测试并稍微扩展。

Answer 2

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

另一方面，Matt Morrow一直在做一些工作，以汇编语言.S文件的形式提取任意循环数据，使用他的便捷真空库。所以无论是真空还是真空都可以满足你的需求

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