On 6/30/2011 8:05 AM, David Doria wrote:
On Wed, Jun 29, 2011 at 6:07 PM, Stephen Woodbridge <woodbri@swoodbridge.com> 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:
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 <class G, class E> 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