Re: [Boost-users] Problems calling make_reversed_graph in a call to dijkstra from version 1.48

Subject: Re: [Boost-users] Problems calling make_reversed_graph in a call to dijkstra from version 1.48
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2013-04-16 14:13:44

On Tue, 16 Apr 2013, Berit Dangaard Brouer wrote:

> Hi,
>
> First of all thank you for providign the boost BGL library. I use it 
> extensively.
>
> I am having some problems with some code, that works just fine using boost 
> version 1.46, but cannot compile using version 1.48 and higher.
>
> I have a Bidirectional Graph using bundled properties defined as:
>
> struct Port
>  {
>    Port(int index=-1, int type=-1, int port_code=0, string UN="NN", string 
> name="NN", int service_id=-1 ): m_index(index), m_type(type), m_port_code( 
> port_code), UNLOCODE(UN), m_name(name), m_service_id(service_id)  {}
>
>    int m_index;
>    int m_type;//0 port, 1 port call
>    int m_port_code;
>    string UNLOCODE;
>    string m_name;
>    int m_service_id;
>  };
>
> struct Edge
>  {
>
>  Edge( int id=-1, int type=-1, double weight=0.0, double cost=0.0, double 
> dual_cost=0.0, double util=0.0, double cap=0.0, double r_cap=0.0 ) : 
> m_idx(id), m_type(type), m_weight(weight) , m_cost(cost), 
> m_dual_cost(dual_cost), m_utilization(util), m_capacity(cap), 
> m_res_cap(r_cap)  {}
>
>    unsigned int m_idx;
>    int m_type;//0 is load edge, 1 is voyage edge, 2 forfeited edge 
> (commodity link)
>    double m_weight; //distance
>    double m_cost; //cost - only on load/unload/transhipment edges
>    double m_dual_cost;
>    double m_utilization;
>    double m_capacity;
>    double m_res_cap; //residual capacity
>  };
>
>
>
> //Graph
> typedef adjacency_list<
> vecS ,
> vecS ,
> bidirectionalS,
> Port,
> Edge>
> mcf_graph;
>
> I am trying to make a call to dijkstra on a reversed graph as follows: (the 
> reversed graph is also a filtered graph, but I do not think this is an issue:
>
> dijkstra_shortest_paths (make_reverse_graph(fg), before_p, predecessor_map ( 
> &p[0] ).distance_map ( &d[0] ).weight_map ( get ( &Edge::m_weight, fg) 
> ).vertex_index_map ( get ( vertex_index,fg ) ) );

The problem here is that you pass in a weight map from the original
graph while the algorithm expects one on the reverse graph.  That used
to work, but some of the internals of reverse_graph have changed so that
it doesn't anymore.  Try putting the reverse_graph into a variable and
then calling get(&Edge::m_weight, rg) on that.  You probably want to do
the same for vertex_index_map, but that is less important (reverse_graph
does not change the graph vertex type).

-- Jeremiah Willcock