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