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

Question

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.

Answer 1

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.

Answer 2

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).