CODEWITHSUNDEEP
haskellgraph-theory
sajjad
sajjad

Reputation:

Graphs (Nodes and Edges)

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.

Upvotes: 2

Views: 3062

Answers (4)

Don Stewart
Don Stewart

Reputation: 137937

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

Upvotes: 2

Jared Updike
Jared Updike

Reputation: 7277

From Data.Graph:

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

To search the Haskell API and libraries:

Upvotes: 8

Adam Matan
Adam Matan

Reputation: 136141

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?

Upvotes: 2

oz10
oz10

Reputation: 158254

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.

Upvotes: 2

Related Questions