[Newbie] Data structure for Dijkstra's algorithm
Hi! I am new to functional Programming and need some advice. I want to implement Dijkstra's algorithm for the shortest path problem. The algorithm calculates the shortest path from a single vertex in a directed graph to any other connected vertex ( http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm ). For input and output I need an appropriate graph representation. It should be as simple to implement as possible - speed and memory consumption does not matter. The graph consists of vertices (including the source vertex) and weighted edges. I first thought of an adjacency matrix implemented with nested lists. Something like [[0,1,6,2] , [1,0,2,infinity] , [6,2,0,3] , [2,infinity,3,0]] where every sublist represents a vertex, and every entry represents the edge weight to another vertex (infinity means there is no direct connection, and 0 means it points to itself). My main problem is that this adjacency list is not so easy to process. For my output I need a tree like structure and I always need to keep track of the previous vertex and its distance etc. Other approaches e.g. structure-like tuples didn't really work - my C experience is worthless. Bottom line - I don't what to do. Any help is appreciated. TIA, Robert Potthast
This algorithm relies pretty fundamentally on mutability, which makes it a less than wonderful fit for a functional language. If you want to use this algorithm in particular, I would recommend a mutable array indexed on the vertex pair (u,v). See: http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data.Array.MArray... These will require your program to be in the IO or ST monads. Alternately, you could do it fully functionally using Data.FiniteMap, but I don't think you will be happy with the performance. If you just want to solve the shortest path problem, it may be possible to come up with something using the Data.Graph module, although you might have to dig around in the module source to get at what you need. There's a lot of goodies not exported from that module. RCP-Software wrote:
Hi!
I am new to functional Programming and need some advice. I want to implement Dijkstra's algorithm for the shortest path problem. The algorithm calculates the shortest path from a single vertex in a directed graph to any other connected vertex ( http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm ).
For input and output I need an appropriate graph representation. It should be as simple to implement as possible - speed and memory consumption does not matter. The graph consists of vertices (including the source vertex) and weighted edges. I first thought of an adjacency matrix implemented with nested lists. Something like [[0,1,6,2] , [1,0,2,infinity] , [6,2,0,3] , [2,infinity,3,0]] where every sublist represents a vertex, and every entry represents the edge weight to another vertex (infinity means there is no direct connection, and 0 means it points to itself). My main problem is that this adjacency list is not so easy to process. For my output I need a tree like structure and I always need to keep track of the previous vertex and its distance etc. Other approaches e.g. structure-like tuples didn't really work - my C experience is worthless.
Bottom line - I don't what to do. Any help is appreciated.
TIA, Robert Potthast
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
On Mon, 14 Feb 2005 12:27:51 -0500, robert dockins <robdockins@fastmail.fm> wrote:
[Dijkstra's] algorithm relies pretty fundamentally on mutability, which makes it a less than wonderful fit for a functional language. If you want to use this algorithm in particular, I would recommend a mutable array indexed on the vertex pair (u,v).
It is quite possible to implement the shortest path algorithm functionally even though it is not straight forward. See the following paper by Ralf Hinze: http://www.informatik.uni-bonn.de/~ralf/publications/ICFP01.pdf /Josef
On 2005-02-14, robert dockins <robdockins@fastmail.fm> wrote:
This algorithm relies pretty fundamentally on mutability, which makes it a less than wonderful fit for a functional language.
True
If you want to use this algorithm in particular, I would recommend a mutable array indexed on the vertex pair (u,v). See:
But this is overkill. An intertwined priority queue and a mutable mapping from vertices to distances and current shortest path works fine.
These will require your program to be in the IO or ST monads. Alternately, you could do it fully functionally using Data.FiniteMap, but I don't think you will be happy with the performance.
If you just want to solve the shortest path problem, it may be possible to come up with something using the Data.Graph module, although you might have to dig around in the module source to get at what you need. There's a lot of goodies not exported from that module.
Reasonable advice. I still think there should be some clever way to do this using lazy evaluation, but it's not at all clear how. -- Aaron Denney -><-
G'day all. Quoting robert dockins <robdockins@fastmail.fm>:
This algorithm relies pretty fundamentally on mutability, which makes it a less than wonderful fit for a functional language.
Right, which makes me wonder if this is the algorithm that you really want. Does it have to be Dijkstra's algorithm? Dynamic programming algorithms (e.g. the Floyd-Warshall algorithm) are very easy to write in a lazy language like Haskell, because you don't need mutability; you write "thunks" into a dictionary data structure (which may depend on other values in the data structure), and let the evaluation rule do the rest. Cheers, Andrew Bromage
On Mon, 14 Feb 2005 15:00:17 +0100 RCP-Software <rcp-software@web.de> wrote:
For input and output I need an appropriate graph representation. It should be as simple to implement as possible - speed and memory consumption does not matter. The graph consists of vertices (including the source vertex) and weighted edges. I first thought of an adjacency matrix implemented with nested lists. Something like [[0,1,6,2] , [1,0,2,infinity] , [6,2,0,3] , [2,infinity,3,0]] where every sublist represents a vertex, and every entry represents the edge weight to another vertex (infinity means there is no direct connection, and 0 means it points to itself).
Robert, if you're not requiring an efficient implementation you can represent the graph as a list of (weighted) arcs, i.e. type Node = Int -- or whatever you want to label the nodes with type Weight = Int -- weights are just ints type Arc = (Node, Weight, Node) type Graph = [Arc] The type name declarations are just for readability, but also to enforce that you keep nodes and weights separately (even thought they might both be integers). Alternatively, you could also use an adjecency list, but again you should distinguish nodes and weights: type Adj = [(Node,Weight)] -- weighted arcs connecting to nodes type AdjGraph = [ (Node, Adj) ] -- list of adjecencies In either case, remember that Haskell lists must be homogenous, i.e. you can't have a weight being either an int or "infinity". You can either use a special large value to represent infinity or you'd have to define a lifted type. I'd recomend you try the first option first. BTW, these represetations are less efficient than you could write in e.g. C because you have to traverse a list to find neighbours of a vertex. It is possible to write more efficient representation using references or arrays, but I'd stay away from that until you're more familiar with the language. Best regards, Pedro Vasconcelos
participants (6)
-
Aaron Denney -
ajb＠spamcop.net -
Josef Svenningsson -
Pedro Vasconcelos -
RCP-Software -
robert dockins