Graphs (Nodes and Edges)

Question

I am using HASKELL for graph games. I am willing to get a suitable method for reach ability from a node to a particular node in the graph apart from using bfs or trees etc.

---

As I asked for code in haskell for reach ability from one node to a particular node, it is necessary to tell you that I am totally new to haskell. I have been reading the tutorials and simple examples, but when it come to implementation then I am lost. My graph is a directed graph, and say I want to check whether I can reach from node v to node w in graph.

Answer 1

There are several All pair shortest path algorithms in hand. For small graphs, wikipedia says:

Floyd-Warshall algorithm is an elegant, quickly implementable O(n3) algorithm (Assumes absence of negatively-weighed cycles).

EDIT: Are you looking for a ready-made Haskell code?

Answer 2

Try representing your graph as a matrix where a 1 represents an edge.

E.g.:

 Node/Node  A  B  C  D
          A  0  0  1  1
          B  0  0  1  1
          C  0  0  1  0
          D  1  0  1  0

For directed graphs the order of the matrix indices matters, for undirected graphs they don't. The above being a directed graph where there is an edge from D->C but not from C->D.

Answer 3

From Data.Graph:

reachable :: Graph -> Vertex -> [Vertex]

To search the Haskell API and libraries:

• http://www.haskell.org/hoogle/
• http://holumbus.fh-wedel.de/hayoo/hayoo.html

Answer 4

Not entirely sure what your question is, in the context of Haskell.

• Are you asking for readymade implementations of the required algorithms + data structures?
• Looking for libraries for graphs in Haskell?

Either way, check http://hackage.haskell.org for graph-related packages:

1. http://hackage.haskell.org/package/fgl
2. http://hackage.haskell.org/package/graphviz
3. http://hackage.haskell.org/package/Graphalyze
4. http://hackage.haskell.org/package/GraphSCC
5. http://hackage.haskell.org/package/hgal