How would you represent a graph (the kind associated with the travelling salesman problem) in Haskell

4
votes

It's pretty easy to represent a tree in haskell:

data Tree a = Node Tree a Tree | Leaf a

but that's because it has no need for the concept of an imperative style "pointer" because each Node/Leaf has one, and only one parent. I guess I could represent it as a list of lists of Maybe Ints ...to create a table with Nothing for those nodes without a path between and Just n for those that do... but that seems really ugly and unwieldy.

5
haskellgraph-traversal
Check out the functional graph library, although if I recall correctly, it's undergoing a major rewrite. – Antal Spector-Zabusky
Note that you can construct a graph with cycles easily enough by relying on lazy evaluation. For instance, I believe let xs = () : xs in xs will construct a single-element circular list, not an list of infinitely repeating elements. – C. A. McCann

5 Answers

8
votes

You can use a type like

type Graph a = [Node a]
data Node a = Node a [Node a]

The list of nodes is the outgoing (or incoming if you prefer) edges of that node. Since you can build cyclic data structures this can represent arbitrary (multi-)graphs. The drawback of this kind of graph structure is that it cannot be modified once you have built it it. To do traversals each node probably needs a unique name (can be included in the a) so you can keep track of which nodes you have visited.

6
votes

Disclaimer: below is a mostly pointless exercise in "tying the knot" technique. Fgl is the way to go if you want to actually use your graphs. However if you are wondering how it's possible to represent cyclic data structures functionally, read on.

It is pretty easy to represent a graph in Haskell!

-- a directed graph

data Vertex a b = Vertex { vdata :: a, edges :: [Edge a b] }
data Edge   a b = Edge   { edata :: b, src :: Vertex a b, dst :: Vertex a b }

-- My graph, with vertices labeled with strings, and edges unlabeled

type Myvertex = Vertex String ()
type Myedge   = Edge   String ()

-- A couple of helpers for brevity

e :: Myvertex -> Myvertex -> Myedge
e = Edge ()

v :: String -> [Myedge] -> Myvertex
v = Vertex

-- This is a full 5-graph

mygraph5 = map vv [ "one", "two", "three", "four", "five" ] where
    vv s = let vk = v s (zipWith e (repeat vk) mygraph5) in vk

This is a cyclic, finite, recursive, purely functional data structure. Not a very efficient or beautiful one, but look, ma, no pointers! Here's an exercise: include incoming edges in the vertex

data Vertex a b = Vertex {vdata::a, outedges::[Edge a b], inedges::[Edge a b]}

It's easy to build a full graph that has two (indistinguishable) copies of each edge:

mygraph5 = map vv [ "one", "two", "three", "four", "five" ] where
    vv s = 
       let vks = repeat vk
           vk = v s (zipWith e vks mygraph5) 
                    (zipWith e mygraph5 vks)
       in vk

but try to build one that has one copy of each! (Imagine that there's some expensive computation involved in e v1 v2).

2
votes

The knot-tying techniques that others have outlined can work, but are a bit of a pain, especially when you're trying to construct the graph on the fly. I think the approach you describe is a bit more practical. I would use an array/vector of node types where each node type holds a list/array/vector of neighbors (in addition to any other data you need) represented as ints of the appropriate size, where the int is an index into the node array. I probably wouldn't use Maybe Ints. With Int you can still use -1 or any suitable value as your uninitialized default. Once you have populated all your neighbor lists and know they are good values you won't need the failure machinery provided by Maybe anyway, which as you observed imposes overhead and inconvenience. But your pattern of using Maybe would be the correct thing to do if you needed to make complete use of all possible values the node pointer type could contain.

2
votes

The simplest way is to give the vertices in the graph unique names (which could be as simple as Ints) and use either the usual adjacency matrix or neighbor list approaches, i.e., if the names are Ints, either use array (Int,Int) Bool, or array Int [Int].

1
votes

Have a look at this knot-tying technique, it is used to create circular structures. You may need it if your graph contains cycles.

Also, you can represent your graph using the adjacency matrix.

Or you can keep maps between each node and the inbound and outbound edges.

In fact, each of them is useful in one context and a pain in others. Depending on your problem, you'll have to choose.