[Boost-users] Calling dijkstra on a filtered graph with bundled properties?

Subject: [Boost-users] Calling dijkstra on a filtered graph with bundled properties?
From: Berit Dangaard Brouer (blof_at_[hidden])
Date: 2012-04-18 16:34:37

Hi there,

First of all thank you for the boost graph library - I really enjoy 
working with it. However I have become challenged in calling Dijkstra on 
a filtered graph with bundled properties:

My graph structure "mcf_graph" looks like this:

#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=0, 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=0, int type=0, double weight=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_dual_cost(dual_cost), 
m_utilization(util), m_capacity(cap), m_res_cap(r_cap)  {}

     unsigned int m_idx;
     int m_type;
     double m_weight;
     double m_dual_cost;
     double m_utilization;
     double m_capacity;
     double m_res_cap; //residual capacity
   };

template <typename res_cap_map>
struct positive_res_cap {
     positive_res_cap() { }
     positive_res_cap( res_cap_map cap) : res_cap(cap) { }
     bool operator()(const Edge& e) const {
         return 0 < e.m_res_cap;
     }
     res_cap_map res_cap;
};

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

private:
    mcf_graph& g;
};

#endif

I am filtering an mcf_graph like this:

     //filter positive residual capacity graph
     positive_res_cap<res_cap_map> filter(get(&Edge::m_res_cap, 
m_mcf->graph()));
     filtered_graph<mcf_graph, positive_res_cap<res_cap_map> > 
fg(m_mcf->graph(), filter);

and then calling Dijkstra like this:

     vertex_descriptor o_vd;
     std::vector<vertex_descriptor> p ( num_vertices ( fg ) );
     std::vector<double> d ( num_vertices ( fg ) );

     dijkstra_shortest_paths ( fg, o_vd, predecessor_map ( &p[0] 
).distance_map ( &d[0] ).weight_map ( get ( &Edge::m_weight,fg ) 
).vertex_index_map ( get (     vertex_index,fg ) ) );

and I get the following compilation error:

/usr/include/boost/graph/filtered_graph.hpp:75:63: error: no match for 
call to '(const 
positive_res_cap<boost::bundle_property_map<boost::adjacency_list<boost::vecS, 
boost::vecS, boost::bidirectionalS, Port, Edge>, 
boost::detail::edge_desc_impl<boost::bidirectional_tag, unsigned int>, 
Edge, double> >) (const 
boost::detail::edge_desc_impl<boost::bidirectional_tag, unsigned int>&)'
/home/berit/svn/MCF/src/IPH/include/mcf_graph.h:54:8: note: candidate is:
/home/berit/svn/MCF/src/IPH/include/mcf_graph.h:57:7: note: bool 
positive_res_cap<res_cap_map>::operator()(const Edge&) const [with 
res_cap_map = 
boost::bundle_property_map<boost::adjacency_list<boost::vecS, 
boost::vecS, boost::bidirectionalS, Port, Edge>, 
boost::detail::edge_desc_impl<boost::bidirectional_tag, unsigned int>, 
Edge, double>]
/home/berit/svn/MCF/src/IPH/include/mcf_graph.h:57:7: note:   no known 
conversion for argument 1 from 'const 
boost::detail::edge_desc_impl<boost::bidirectional_tag, unsigned int>' 
to 'const Edge&'

The above call to Dijkstra works on a non-filtered graph. Can anyone 
help me out in both understanding why it does not work for the predicate 
(Is it because the iterators are different???) and how to solve my problem?

Thanks in advance !

Berit
-- 
Best Regards,
Berit Dangaard Brouer (formerly Løfstedt)
PhD. Student
DTU Management Engineering, Operations Research
Technical University of Denmark
	
Department of Management Engineering
Produktionstorvet, Bygning 426
2800  Kgs. Lyngby
blof_at_[hidden] <mailto:blof_at_[hidden]>
www.or.man.dtu.dk <http://www.or.man.dtu.dk>