將圖保存在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文件的形式提取任意循環數據，使用他的便捷真空庫。所以無論是真空還是真空都可以滿足你的需求

一般來說，避免在地圖上看到的巫術和跟蹤節點可能是最合理和可維護的解決方案。