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. How to I define an edge id and set it when I build my graph?

You are already doing that with: graph[e].id = id; You have to make sure that your template parameter E is the edge_descriptor of G. So maybe use the following instead: template <class G> static void graph_add_edge(G &graph, int id, int source, int target, float8 cost) { typedef typename graph_traits<G>::edge_descriptor e; bool inserted; tie(e, inserted) = add_edge(source, target, graph); graph[e].cost = cost; graph[e].id = id; }

2. Given a vertex id and a predecessor id, How do I get the edge id?

template <class G> static int get_edge_id(G &graph, int source, int target) { typedef typename graph_traits<G>::edge_descriptor e; bool found; tie(e, found) = edge(source, target, graph); return graph[e].id; }

On 6/30/2011 9:56 AM, Alex Hagen-Zanker wrote:

Sorry, correction:

...

1. How to I define an edge id and set it when I build my graph? You are already doing that with: graph[e].id = id; You have to make sure that your template parameter E is the edge_descriptor of G. So maybe use the following instead:

template <class G> static void graph_add_edge(G &graph, int id, int source, int target, float8 cost) { typedef typename graph_traits<G>::edge_descriptor E; E e; bool inserted; tie(e, inserted) = add_edge(source, target, graph); graph[e].cost = cost; graph[e].id = id; }

...

2. Given a vertex id and a predecessor id, How do I get the edge id?

template <class G> static int get_edge_id(G &graph, int source, int target) { typedef typename graph_traits<G>::edge_descriptor E;; E e; bool found; tie(e, found) = edge(source, target, graph); return graph[e].id; }

Alex, I think this has gotten me closer to a solution, but I'm running into a compile issue: The modified code is here: http://pastebin.com/buzd7F4J The error I'm getting is: make g++ -g -fPIC -Wno-deprecated -c boost_dijkstra_nodes.cpp boost_dijkstra_nodes.cpp: In function âint boost_dijkstra_nodes(edge_t*, unsigned int, int, double, bool, bool, path_element_t**, int*, char**)â: boost_dijkstra_nodes.cpp:136: error: expected primary-expression before â,â token make: *** [boost_dijkstra_nodes.o] Error 1 where line 136 is: pe.edge_id = get_edge_id(graph_t, pe.parent_id, pe.vertex_id); Also in dijkstra.h, I define two structs: typedef struct edge { int id; int source; int target; float8 cost; float8 rcost; } edge_t; typedef struct path_element { int vertex_id; int parent_id; int edge_id; float8 cost; } path_element_t; And if I change line 136 to: pe.edge_id = get_edge_id(graph_t, pe.parent_id, pe.vertex_id); I get this compile error: g++ -g -fPIC -Wno-deprecated -c boost_dijkstra_nodes.cpp boost_dijkstra_nodes.cpp: In function âint boost_dijkstra_nodes(edge_t*, unsigned int, int, double, bool, bool, path_element_t**, int*, char**)â: boost_dijkstra_nodes.cpp:136: error: expected primary-expression before â,â token make: *** [boost_dijkstra_nodes.o] Error 1 woodbri@mappy:~/work/mapmatching$ vi boost_dijkstra_nodes.cpp woodbri@mappy:~/work/mapmatching$ make g++ -g -fPIC -Wno-deprecated -c boost_dijkstra_nodes.cpp boost_dijkstra_nodes.cpp: In function âint boost_dijkstra_nodes(edge_t*, unsigned int, int, double, bool, bool, path_element_t**, int*, char**)â: boost_dijkstra_nodes.cpp:136: error: no matching function for call to âget_edge_id(boost_dijkstra_nodes(edge_t*, unsigned int, int, double, bool, bool, path_element_t**, int*, char**)::graph_t&, int&, int&)â make: *** [boost_dijkstra_nodes.o] Error 1 not sure what I'm doing wrong here, any ideas? Also it occurs to me that getting the edge based on the vertexes rather than the vertex ids might be faster. Thanks, -Steve

Alex, You have been very helpful. I got it to work, here is the final code: http://pastebin.com/qa1caiXs Many thanks, -Steve On 6/30/2011 11:47 AM, Alex Hagen-Zanker wrote:

...

I think this has gotten me closer to a solution, but I'm running into a compile issue:

...

where line 136 is:

pe.edge_id = get_edge_id(graph_t, pe.parent_id, pe.vertex_id);

graph_t is a type not an object.

also, get_edge_id will require template parameters, how about:

pe.edge_id = get_edge_id(graph, pe.parent_id, pe.vertex_id);

However, the E template parameter is really not necessary if you just use the typedef that you commented out. Once you get rid of E, the G template parameter will be recognized automatically:

pe.edge_id = get_edge_id(graph, pe.parent_id, pe.vertex_id);

Also I noticed that you set the number of nodes to 1. Note that add_edge assumes your nodes to be present, and does not add nodes if the required nodes are not there.

...

Also it occurs to me that getting the edge based on the vertexes rather than the vertex ids might be faster.

It will be just the same. Since the vertices are stored in a vector, vertex_descriptors are just indices to a vector.

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

On 30/06/2011 21:47, Stephen Woodbridge wrote:

That said, I assume add_edge does add the nodes if they do not exist in the graph when the edge is added and that when an edge is added and one or both nodes exist it uses them, since the code works and I appear to be getting the correct answers.

You're right, sorry to misinform you. From the documentation: "if either vertex descriptor u or v (which are integers) has a value greater than the current number of vertices in the graph, the graph is enlarged so that the number of vertices is std::max(u,v) + 1. " -- Alex Hagen-Zanker University of Cambridge, Department of Architecture, 1-5 Scroope Terrace, Cambridge, CB2 1PX, United Kingdom Tel: +44(0) 1223 330573