How do you represent a graph in Haskell?

Question

It's easy enough to represent a tree or list in haskell using algebraic data types. But how would you go about typographically representing a graph? It seems that you need to have pointers. I'm guessing you could have something like

type Nodetag = String
type Neighbours = [Nodetag]
data Node a = Node a Nodetag Neighbours

And that would be workable. However it feels a bit decoupled; The links between different nodes in the structure don't really "feel" as solid as the links between the current previous and next elements in a list, or the parents and children of a node in a tree. I have a hunch that doing algebraic manipulations on the graph as I defined it would be somewhat hindered by the level of indirection introduced through the tag system.

It is primarily this feeling of doubt and perception of inelegance that causes me to ask this question. Is there a better/more mathematically elegant way of defining graphs in Haskell? Or have I stumbled upon something inherently hard/fundamental? Recursive data structures are sweet, but this seems to be something else. A self referential data structure in a different sense to how trees and lists are self referential. It's like lists and trees are self referential at the type level, but graphs are self referential at the value level.

So what's really going on?

Solution 1

I also find it awkward to try to represent data structures with cycles in a pure language. It's the cycles that are really the problem; because values can be shared any ADT that can contain a member of the type (including lists and trees) is really a DAG (Directed Acyclic Graph). The fundamental issue is that if you have values A and B, with A containing B and B containing A, then neither can be created before the other exists. Because Haskell is lazy you can use a trick known as Tying the Knot to get around this, but that makes my brain hurt (because I haven't done much of it yet). I've done more of my substantial programming in Mercury than Haskell so far, and Mercury is strict so knot-tying doesn't help.

Usually when I've run into this before I've just resorted to additional indirection, as you're suggesting; often by using a map from ids to the actual elements, and having elements contain references to the ids instead of to other elements. The main thing I didn't like about doing that (aside from the obvious inefficiency) is that it felt more fragile, introducing the possible errors of looking up an id that doesn't exist or trying to assign the same id to more than one element. You can write code so that these errors won't occur, of course, and even hide it behind abstractions so that the only places where such errors could occur are bounded. But it's still one more thing to get wrong.

However, a quick google for "Haskell graph" led me to http://www.haskell.org/haskellwiki/The_Monad.Reader/Issue5/Practical_Graph_Handling, which looks like a worthwhile read.

Solution 2

In shang's answer you can see how to represent a graph using laziness. The problem with these representations is that they are very difficult to change. The knot-tying trick is useful only if you're going to build a graph once, and afterward it never changes.

In practice, should I actually want to do something with my graph, I use the more pedestrian representations:

• Edge list
• Adjacency list
• Give a unique label to each node, use the label instead of a pointer, and keep a finite map from labels to nodes

If you're going to be changing or editing the graph frequently, I recommend using a representation based on Huet's zipper. This is the representation used internally in GHC for control-flow graphs. You can read about it here:

• An Applicative Control-Flow Graph based on Huet's Zipper

• Hoopl: A Modular, Reusable Library for Dataflow Analysis and Transformation

Solution 3

It's true, graphs are not algebraic. To deal with this problem, you have a couple of options:

1. Instead of graphs, consider infinite trees. Represent cycles in the graph as their infinite unfoldings. In some cases, you may use the trick known as "tying the knot" (explained well in some of the other answers here) to even represent these infinite trees in finite space by creating a cycle in the heap; however, you will not be able to observe or detect these cycles from within Haskell, which makes a variety of graph operations difficult or impossible.
2. There are a variety of graph algebras available in the literature. The one that comes to mind first is the collection of graph constructors described in section two of Bidirectionalizing Graph Transformations. The usual property guaranteed by these algebras is that any graph can be represented algebraically; however, critically, many graphs will not have a canonical representation. So checking equality structurally isn't enough; doing it correctly boils down to finding graph isomorphism -- known to be something of a hard problem.
3. Give up on algebraic datatypes; explicitly represent node identity by giving them each unique values (say, Ints) and referring to them indirectly rather than algebraically. This can be made significantly more convenient by making the type abstract and providing an interface that juggles the indirection for you. This is the approach taken by, e.g., fgl and other practical graph libraries on Hackage.
4. Come up with a brand new approach that fits your use case exactly. This is a very difficult thing to do. =)

So there are pros and cons to each of the above choices. Pick the one that seems best for you.

Solution 4

As Ben mentioned, cyclic data in Haskell is constructed by a mechanism called "tying the knot". In practice, it means that we write mutually recursive declarations using let or where clauses, which works because the mutually recursive parts are lazily evaluated.

Here's an example graph type:

import Data.Maybe (fromJust)

data Node a = Node
    { label    :: a
    , adjacent :: [Node a]
    }

data Graph a = Graph [Node a]

As you can see, we use actual Node references instead of indirection. Here's how to implement a function that constructs the graph from a list of label associations.

mkGraph :: Eq a => [(a, [a])] -> Graph a
mkGraph links = Graph $ map snd nodeLookupList where

    mkNode (lbl, adj) = (lbl, Node lbl $ map lookupNode adj)

    nodeLookupList = map mkNode links

    lookupNode lbl = fromJust $ lookup lbl nodeLookupList

We take in a list of (nodeLabel, [adjacentLabel]) pairs and construct the actual Node values via an intermediate lookup-list (which does the actual knot-tying). The trick is that nodeLookupList (which has the type [(a, Node a)]) is constructed using mkNode, which in turn refers back to the nodeLookupList to find the adjacent nodes.

Solution 5

A few others have briefly mentioned fgl and Martin Erwig's Inductive Graphs and Functional Graph Algorithms, but it's probably worth writing up an answer that actually gives a sense of the data types behind the inductive representation approach.

In his paper, Erwig presents the following types:

type Node = Int
type Adj b = [(b, Node)]
type Context a b = (Adj b, Node, a, Adj b)
data Graph a b = Empty | Context a b & Graph a b

(The representation in fgl is slightly different, and makes good use of typeclasses - but the idea is essentially the same.)

Erwig is describing a multigraph in which nodes and edges have labels, and in which all edges are directed. A Node has a label of some type a; an edge has a label of some type b. A Context is simply (1) a list of labeled edges pointing to a particular node, (2) the node in question, (3) the node's label, and (4) the list of labeled edges pointing from the node. A Graph can then be conceived of inductively as either Empty, or as a Context merged (with &) into an existing Graph.

As Erwig notes, we can't freely generate a Graph with Empty and &, as we might generate a list with the Cons and Nil constructors, or a Tree with Leaf and Branch. Too, unlike lists (as others have mentioned), there's not going to be any canonical representation of a Graph. These are crucial differences.

Nonetheless, what makes this representation so powerful, and so similar to the typical Haskell representations of lists and trees, is that the Graph datatype here is inductively defined. The fact that a list is inductively defined is what allows us to so succinctly pattern match on it, process a single element, and recursively process the rest of the list; equally, Erwig's inductive representation allows us to recursively process a graph one Context at a time. This representation of a graph lends itself to a simple definition of a way to map over a graph (gmap), as well as a way to perform unordered folds over graphs (ufold).

The other comments on this page are great. The main reason I wrote this answer, however, is that when I read phrases such as "graphs are not algebraic," I fear that some readers will inevitably come away with the (erroneous) impression that no one's found a nice way to represent graphs in Haskell in a way that permits pattern matching on them, mapping over them, folding them, or generally doing the sort of cool, functional stuff that we're used to doing with lists and trees.

View more solutions

Comments

[Bayquiri]

You should also mention that this data structure is not able to describe graphs. It only describes their unfoldings. (infinite unfoldings in finite space, but still...)

[Rohan Desai]

Another problem with tying the knot is that it is very easy to accidentally untie it and waste a lot of space.

[TheIronKnuckle]

Wow. I haven't had the time to examine all the answers in detail, but I will say that exploiting lazy evaluation like this sounds like you'd be skating on thin ice. How easy would it be to slip into infinite recursion? Still awesome stuff, and feels much better than the datatype I proposed in the question.

[Justin L.]

@TheIronKnuckle not too much difference than the infinite lists that Haskellers use all the time :)

[Artelius]

"you will not be able to observe or detect these cycles from within Haskell" is not exactly true - there's a library that lets you do just that! See my answer.

[gntskn]

Something seems to be wrong with Tuft's website (at least at the moment), and neither of these links work currently. I have managed to find some alternative mirrors for these: An Applicative Control-Flow Graph based on Huet's Zipper, Hoopl: A Modular, Reusable Library for Dataflow Analysis and Transformation

[Josh.F]

graphs are algebraic now! hackage.haskell.org/package/algebraic-graphs

[Daniel Wagner]

The algebraic-graphs package appears to fall under (2) here. Just because you can use an algebraic language to describe a graph (as in that package) or algebra-like pattern matching (as in fgl) does not mean graphs are algebraic.