Problem with dijkstra_shortest_paths
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
On 6/29/2011 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:
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.
OK, a little more information that might help: 1. I'm using Boost 1.34 on Linux Debian Lenny which is pretty old but I can't upgrade this system yet. I could try this on another system if you think this is the problem. 2. boost_dijkstra_nodes() is always called with directed=false and has_reverse_cost=false but the graph is always built as directed with both the u-v and v-u edges added with the same cost. 3. I thinking that may be the problem is that I'm associating the edge is with a vertex id, but any given vertex can have multiple edges associated with it and may be I should be using a PropertyTag on the edge instead of what I am doing now. Thanks again for any input, -Steve
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
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
On Thu, Jun 30, 2011 at 9:18 AM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:
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
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<Graph::edge_descriptor, bool> 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<Graph::edge_iterator, Graph::edge_iterator> 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
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; }
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 Hagen-Zanker University of Cambridge, Department of Architecture, 1-5 Scroope Terrace, Cambridge, CB2 1PX, United Kingdom Tel: +44(0) 1223 330573
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
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_t, E>(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.
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_t, E>(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 6/30/2011 11:47 AM, Alex Hagen-Zanker wrote: ...
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.
... OK, I just noticed this comment. I think to create a graph you need to allocate at least one node. I don't have a good way to get the number of unique nodes from the data that I'm building the graph from, short of scanning it all first and getting the min and max node ids. I actually do have to scan for the minimum node id because I renumber them, so also picking up the max node id at the same time could be done also. I assume if I create the graph with max-min+1 number of nodes, that that will speed it up because the container will not need to be extended when new edges with new nodes are added. 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. Thanks, -Steve
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
participants (3)
-
Alex Hagen-Zanker -
David Doria -
Stephen Woodbridge