
Boost Users : 
Subject: Re: [Boostusers] BGL: Problem with dijkstra_shortest_paths
From: Stephen Woodbridge (woodbri_at_[hidden])
Date: 20110630 09:18:58
On 6/30/2011 8:05 AM, David Doria wrote:
> On Wed, Jun 29, 2011 at 6:07 PM, Stephen Woodbridge
> <woodbri_at_[hidden]> 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_.28BGL.29
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
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net