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

Subject: Re: [Boost-users] BGL: Problem with dijkstra_shortest_paths
From: David Doria (daviddoria_at_[hidden])
Date: 2011-06-30 09:36:28

On Thu, Jun 30, 2011 at 9:18 AM, Stephen Woodbridge
<woodbri_at_[hidden]> wrote:
> 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

1) I would use a "BundledProperty" to store your edge ids:
http://programmingexamples.net/index.php?title=CPP/Boost/BGL/BundledProperties

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