[Boost-users] Problem using a filtered graph in the Ressource constrained shortest path user defined extension and dominance functions

Subject: [Boost-users] Problem using a filtered graph in the Ressource constrained shortest path user defined extension and dominance functions
From: Berit Dangaard Brouer (blof_at_[hidden])
Date: 2013-12-11 08:04:40

Hi,

In our use of the boost ressource constrained shortest path from Boost 
BGL, we define problem specific ressource extension and dominance 
function on a user defined graph type mcf_graph (source code is posted 
below)

Our problem is the use of a filtered graph into the resource function. 
The forfeited edge filter stated in the code below, tries to remove some 
of the edges in order to speed up the algorithm. It seems that the 
resource and extension functions do not know how to deal with the 
filtered graph (I am guessing because they are not template functions), 
although the filtered graph contains the same Edge and Vertex 
definitions as the MCF graph, it is not typewise recognised as an 
mcf_graph, because it also contains the filter map.

Is there any way I can work around this? I tried making the resource and 
extension functions into templates, but this is a problem because my 
edge bundled properties are problem specific. I would truly appreciate 
any suggestions as a filter is preferable to copying the graph.

mcf_graph.h

#ifndef MCF_GRAPH_HPP
#define MCF_GRAPH_HPP

#include <boost/config.hpp>
#include <boost/graph/adjacency_list.hpp>

#include <iostream>

using namespace boost;
using namespace std;

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, 2  transhipment
     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, 
double tt=0.0 , int rot=-1) : 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), m_transittime(tt), m_rot(rot)  {}
     unsigned int m_idx;
     int m_type;//0 is load edge, 1 is voyage edge, 2 forfeited edge 
(commodity link), 3 transhipment edge, 4 transhipment ring edge
     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
     double m_transittime; // transit time on edge with current speed
     double m_rot; // current rotation
   };

//Graph
typedef adjacency_list<
vecS ,
vecS ,
bidirectionalS,
Port,
Edge>
mcf_graph;

//descriptor typedefs
typedef boost::graph_traits<mcf_graph>::vertex_descriptor vertex_descriptor;
typedef boost::graph_traits<mcf_graph>::edge_descriptor edge_descriptor;

//iterator typedefs
typedef boost::graph_traits<mcf_graph>::vertex_iterator Viterator;
typedef boost::graph_traits<mcf_graph>::edge_iterator Eiterator;

typedef boost::graph_traits<mcf_graph>::in_edge_iterator IEiterator;
typedef boost::graph_traits<mcf_graph>::out_edge_iterator OEiterator;

template <typename edge_type_map>
struct forfeited_edge_type {
     forfeited_edge_type() { }
     forfeited_edge_type( edge_type_map type) : forfeited(type) { }
     bool operator()(const edge_descriptor& e) const {
         return forfeited[e]==2;
     }
     edge_type_map forfeited;
};

#endif

And resource_extension and dominance functions here in res_path.h

#ifndef RESPATH_H_
#define RESPATH_H_

#include <boost/config.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/r_c_shortest_paths.hpp>
#include <iostream>
#include "mcf_graph.h"
#include "data.h"
#include <boost/graph/graphviz.hpp>

namespace std {

class respath {
public:

     respath(mcf_graph & m, Eiterator & comm);

     virtual ~respath();

private:
     mcf_graph & m_res_graph;
     Eiterator & commodities;
};

// data structures for shortest path problem with transit time 
constraints (spptt)
// ResourceContainer model
struct spp_spptt_res_cont
{
     spp_spptt_res_cont( double c = 0, double t = 0 ) : cost( c ), time( 
t ) {}
     spp_spptt_res_cont& operator=( const spp_spptt_res_cont& other )
     {
         if( this == &other )
             return *this;
         this->~spp_spptt_res_cont();
         new( this ) spp_spptt_res_cont( other );
         return *this;
     }
     double cost;
     double time;
};

bool operator==( const spp_spptt_res_cont& res_cont_1,const 
spp_spptt_res_cont& res_cont_2 ){
     return ( res_cont_1.cost == res_cont_2.cost
             && res_cont_1.time == res_cont_2.time );
}

bool operator<( const spp_spptt_res_cont& res_cont_1,const 
spp_spptt_res_cont& res_cont_2 )
{
     if( res_cont_1.cost > res_cont_2.cost )
         return false;
     if( res_cont_1.cost == res_cont_2.cost )
         return res_cont_1.time < res_cont_2.time;
     return true;
}

// ResourceExtensionFunction model
class ref_spptt
{
     static double maxtt;
     public:
     static void setmaxtt(double tt){
         maxtt=tt;
     }

     inline bool operator()( const mcf_graph& g,
             spp_spptt_res_cont& new_cont,
             const spp_spptt_res_cont& old_cont,
             boost::graph_traits
             <mcf_graph>::edge_descriptor ed) const
     {
         const Edge& arc_prop = get( edge_bundle, g )[ed];
         new_cont.cost = old_cont.cost + arc_prop.m_cost;
         new_cont.time=old_cont.time + arc_prop.m_transittime;
         double& i_time = new_cont.time;

         return i_time <= (maxtt) ? true : false;

     }
};

double ref_spptt::maxtt=0;

// Dominance Function
class dom_spptt
{
public:
     inline bool operator()( const spp_spptt_res_cont& res_cont_1,
             const spp_spptt_res_cont& res_cont_2 ) const
     {
         return res_cont_1.cost <= res_cont_2.cost
                 && res_cont_1.time <= res_cont_2.time;
     }
};

} /* namespace std */
#endif /* RESPATH_H_ */

-- 
Best Regards,
Ph.D. Berit Dangaard Brouer
Post Doc.
DTU Management Engineering, Management Science
Technical University of Denmark
	
Department of Management Engineering
Produktionstorvet, Bygning 426
2800 Kgs. Lyngby
blof_at_[hidden] <mailto:blof_at_[hidden]>
www.ms.man.dtu.dk <http://www.ms.man.dtu.dk>
http://www.maersk.com/innovation/leadingthroughinnovation/enerplan/
Please read about the ENERPLAN project here 
<http://www.maersk.com/innovation/leadingthroughinnovation/enerplan/>