Boost logo

Boost Users :

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


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

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.



#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

typedef adjacency_list<
vecS ,
vecS ,

//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;


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 {

     respath(mcf_graph & m, Eiterator & comm);

     virtual ~respath();

     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;
         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;
     static void setmaxtt(double tt){

     inline bool operator()( const mcf_graph& g,
             spp_spptt_res_cont& new_cont,
             const spp_spptt_res_cont& old_cont,
             <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
     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]> <>
Please read about the ENERPLAN project here 

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at