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

Subject: Re: [Boost-users] BGL: Problem with dijkstra_shortest_paths
From: Stephen Woodbridge (woodbri_at_[hidden])
Date: 2011-06-30 11:13:24

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_at_mappy:~/work/mapmatching$ vi boost_dijkstra_nodes.cpp
woodbri_at_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