[Lemon-user] Getting the result of Dijkstra on undirected graphs

[Dániel Csővári]

Hi!

I just started using the LEMON library, and I couldn't figure out how to get
the results from the Dijkstra algorithm.
I do have a representation of an undirected graph in another form, where
edges and nodes have their unique ID, and I should write back the results
into that form.
Consider the following code:

        typedef ListGraph::EdgeMap<double> CostMap;

	ListGraph g;

	ListGraph::Node u = g.addNode();
	ListGraph::Node v = g.addNode();
	ListGraph::Edge  a = g.addEdge(u, v);
	CostMap cost(g);
	cost[a] = 5;

	auto d = Dijkstra<ListGraph, CostMap>(g, cost);
	d.run(u);

	Path<ListGraph> p = d.path(v);
	Path<ListGraph>::ArcIt it(p);
	for (; it != INVALID; ++it)
	{
		//that's where I should identify the nodes and edges of the shortest
path with my ID's
	}


I suppose that I can create a new NodeMap and a new EdgeMap to map the
id's used by lemon to the id's of the other representation.

The problem is that the Path returned by the Dijkstra algorithm
contains arcs, even if the graph used was undirected, and I couldn't
find any conversions between the available ArcIt type and the original
Edge type. I tried getting the id of the arc and finding the edge
based on that (with edgeFromId(...)) but as the number of arcs is
twice the number of edges it does not give the expected result (or
crashes).

I'd really appretiate if someone could show me how the Paths can be
converted back.

Thanks in advance,

Daniel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20110307/b2e1fea5/attachment.html>