How would you present a graph (view related to the traveling salesman problem) in Haskell

Question

It is very easy to imagine a tree in haskell:

data Tree a = Node Tree a Tree | Leaf a 

but this is because he does not need the notion of a “pointer” of an imperative style, because each Node / Leaf has one and only one parent. I think I could imagine it as a list of Maybe Int lists ... to create a table with Nothing for these nodes without a path between them and Just n for those who do ... but it seems really ugly and cumbersome.

Answer 1

You can use type type

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

The list of nodes is the outgoing (or incoming, if you want) edges of this node. Since you can create circular data structures, this can be arbitrary (multi-) graphs. The disadvantage of this type of graph structure is that it cannot be changed after its creation. To perform crawls, each node may need a unique name (can be included in a ) so that you can keep track of which nodes you visited.

Answer 2

Disclaimer: Below is basically a meaningless exercise in the technique of "node binding." Fgl is the way to go if you want to actually use your graphics. However, if you are interested in how you can functionally represent circular data structures, read on.

It's pretty easy to imagine a graph in Haskell!

 -- a directed graph data Vertex ab = Vertex { vdata :: a, edges :: [Edge ab] } data Edge ab = Edge { edata :: b, src :: Vertex ab, dst :: Vertex ab } -- 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 = vs (zipWith e (repeat vk) mygraph5) in vk 

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

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

It is easy to construct a complete 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 = vs (zipWith e vks mygraph5) (zipWith e mygraph5 vks) in vk 

but try to build one that has one copy of each! (Imagine that there are some expensive calculations in e v1 v2 ).

Answer 3

The linking methods that others outlined may work, but it's a bit of a pain, especially when you're trying to plot on the fly. I think the approach you are describing is more practical. I would use an array / vector of node types, where each node type contains a list / array / vector of neighbors (in addition to any other data you need), represented as ints of the corresponding size, where int is an index into the node array. I probably would not use Maybe Int s. With Int you can use -1 or any suitable value as the uninitialized default value. After you fill out all the lists of your neighbors and know that they are good values, you still do not need the rejection mechanism provided by Maybe , which, as you noticed, imposes overhead and inconvenience. But your Maybe usage model would be the right thing if you needed to make full use of all the possible values ​​that the node pointer type might contain.

Answer 4

The easiest way is to provide the vertices in the graph with unique names (which can be as simple as Ints), and use either a regular adjacency matrix or an approximation of the list of neighbors, that is, if the names are Ints, or use an array (Int, Int ) Bool or array Int [Int].

Answer 5

Take a look at this knotting technique ; it is used to create circular structures. This may be required if your schedule contains cycles.

In addition, you can present your graph using the adjacency matrix.

Or you can save maps between each node and incoming and outgoing edges.

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