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@dtu.dk
www.ms.man.dtu.dk
http://www.maersk.com/innovation/leadingthroughinnovation/enerplan/

Please read about the ENERPLAN project here