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

[Balázs Dezső]

Hi,

theoretically the ArcIt is convertible to Arc and Arc is convertible to Edge.

for (Path<ListGraph>::ArcIt it(p); it != INVALID; ++it) {
	ListGrapgh::Edge e = it;
}

I think, it's better that the path contains arcs for undirected
graphs, because it describes the orientation of the edge.

Regards, Balazs


On Mon, Mar 7, 2011 at 6:39 PM, Dániel Csővári <daniel.csovari at gmail.com> wrote:
> 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
>
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
>
>