Saving graphs in Haskell

Question

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?

Answer 1

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.

Answer 2

Yes and no. It can be done via domain knowledge of the structure of your Node type and defining some notion of equality that you can test, combined with a list or map of nodes seen so far to recover sharing. In the pathological case there is a notion of a StableName in GHC to construct such a notion.

On another front Matt Morrow has been doing some work to extract in the form of a assembly language .S file, arbitrary cyclic data using his handy vacuum library. So either that or vacuum might suit your needs.

In general avoiding voodoo and tracking nodes seen so far in a map is probably the most rational and maintainable solution.