Re: [Boost-users] BGL: Problem with dijkstra_shortest_paths

On Thu, Jun 30, 2011 at 9:18 AM, Stephen Woodbridge wrote:

On 6/30/2011 8:05 AM, David Doria wrote:

...

On Wed, Jun 29, 2011 at 6:07 PM, Stephen Woodbridge  wrote:

...

Hi all,

I am C programmer floundering in a C++ world! I have the function that I call from C that builds a graph, runs dijkstra_shortest_paths(), then extracts the results and passes them back to a C array of structs. Code is in pastebin:

http://pastebin.com/xi7vLpTx

This seems to work and everything looks ok, EXCEPT the edge ids are not correct. I suspect this is because I'm not doing something correctly and I have been messing with this for a couple weeks without success, so I think its time to ask for help.

So in the function:

graph_add_edge(G&graph, int id, int source, int target, float8 cost)

id is the edge id source is the node id at the start of the edge target is the node_id at the end of the edge cost is the cost to traverse the edge from source to target

I would really appreciate it if someone could look at this and point out what I might be doing wrong.

Thanks in advance,  -Steve

There are a few Dijkstra examples here, do they help?

http://programmingexamples.net/index.php?title=Boost#Boost_Graph_Library_.28...

David,

Thanks, I've been through the examples and some other code. I need to be able to call this code from a C application and basically the code seems to be working. Where I'm having problems is that I need to be able to tag the edges with an ID when I build the graph and to be able to identify those edges by ID in the results. So how do I do this?

My current code builds the graph with this helper function:

struct Edge {  int id;  float8 cost; };

struct Vertex {  int id;  int edge_id; };

template static void graph_add_edge(G &graph, int id, int source, int target, float8 cost) {  E e;  bool inserted;

 if (cost < 0) // edges are not inserted in the graph if cost is negative    return;

 tie(e, inserted) = add_edge(source, target, graph);

 graph[e].cost = cost;  graph[e].id = id;

 typedef typename graph_traits<G>::vertex_descriptor Vertex;  Vertex s = vertex(source, graph);  Vertex t = vertex(target, graph);  graph[s].id = source;  graph[t].id = target;  graph[s].edge_id = id;  graph[t].edge_id = id;

}

So the edge id is set on the Vertex when it is added, but since the same vertex can be on multiple edges, I assume only the edge id of the last vertex is kept and that is what I am seeing in my results.

So the question is:

1. How to I define an edge id and set it when I build my graph? 2. Given a vertex id and a predecessor id, How do I get the edge id?

Thanks,  -Steve

1) I would use a "BundledProperty" to store your edge ids: http://programmingexamples.net/index.php?title=CPP/Boost/BGL/BundledProperti... 2) Given two vertex_descriptors, you can get the edge_descriptor like this: std::pair edgePair = boost::edge(v0, v1, g); Graph::edge_descriptor edge = edgePair.first; 3) The only way I would know to get an edge_descriptor by an edge property is: std::pair edgeIteratorRange = boost::edges(g); for(Graph::edge_iterator edgeIterator = edgeIteratorRange.first; edgeIterator != edgeIteratorRange.second; ++edgeIterator) { if(g[*edgeIterator].edge_id == something) ThisIsTheEdgeYouWereLookingFor; } That is clearly very very inefficient, but if your graph is small enough it might be good enough. I hope that helps a bit. David