BGL dijkstra_shortest_path algorithm method does not accept my color map exterior property

Question

I have been trying to get boost graph lib's dijkstra_shortest_paths to compile for about a week now without avail. I am trying to use exterior property maps for the different named parameters required by the templated method. My graph uses bundled properties for the vertex and the edges and I have been able to build the graph successfully. I will show you what I have for the code:

// vertex bundled properties
struct BusStop
{
    unsigned int id; //used for creating vertex index property map
    string name;
    Location* pLocation;
};

// edge bundled properties:
struct Route
{
    string routeName;
    BusType type;
    float distance; 
};

Here is my graph declaration:

typedef boost::adjacency_list<boost::vecS, boost::setS, boost::undirectedS, BusStop, Route> BusRouteGraph;

Here is my method that tries to do dijkstra's shortest path on the given graph:

template<typename Graph>
bool shortestPathSearch(Graph& g, typename   
  boost::graph_traits<Graph>::vertex_descriptor src,
  typename boost::graph_traits<Graph>::vertex_descriptor dest)
{
    bool bPathFound = false;
    VertexIndexMap index_map = get(&BusStop::id, g);

    // Initialize index_map
    typedef typename graph_traits<Graph>::vertex_iterator V_Iter;
    V_Iter v_iter, v_iter_end;
    int c = 0;
    for( boost::tie(v_iter, v_iter_end) = vertices(g); v_iter != v_iter_end; 
         ++v_iter, ++c)
    {
    index_map[*v_iter] = c;
    }

    // Create exterior properties for these
    vector<int> predecessor(num_vertices(g));
    vector<float> distances(num_vertices(g), 0.0f);
    vector<default_color_type> colors(num_vertices(g));

    dijkstra_shortest_paths(g, src, weight_map(get(&Route::distance, g))
    .color_map (make_iterator_property_map(colors.begin(), index_map))
        .distance_map(make_iterator_property_map(distances.begin(), 
                           index_map)));


    return bPathFound;
}

I get these compile time errors:(only the first error below)

\src\BusRouteFinder.cpp:461:2:   instantiated from 'bool shortestPathSearch  (Graph&, typename boost::graph_traits<Graph>::vertex_descriptor, typename boost::graph_traits<Graph>::vertex_descriptor) [with Graph = boost::adjacency_list<boost::vecS, boost::setS, boost::undirectedS, BusStop, Route>, typename boost::graph_traits<Graph>::vertex_descriptor = void*]'
..\src\BusRouteFinder.cpp:91:39:   instantiated from here
C:\boost\boost_1_48_0/boost/graph/two_bit_color_map.hpp:86:3: error: invalid cast from type 'boost::default_property_traits<boost::adj_list_vertex_property_map<boost::adjacency_list<boost::vecS, boost::setS, boost::undirectedS, BusStop, Route>, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t> >::value_type {aka boost::detail::error_property_not_found}' to type 'std::size_t {aka unsigned int}'
C:\boost\boost_1_48_0/boost/graph/two_bit_color_map.hpp:88:30: error: no match for 'operator/' in 'i / elements_per_char'
C:\boost\boost_1_48_0/boost/graph/two_bit_color_map.hpp:88:30: note: candidates are:
C:\boost\boost_1_48_0/boost/concept_archetype.hpp:316:3: note: template<class Base> boost::dividable_archetype<Base> boost::operator/(const boost::dividable_archetype<Base>&, const boost::dividable_archetype<Base>&)
C:\boost\boost_1_48_0/boost/concept_archetype.hpp:344:3: note: template<class Return, class BaseFirst, class BaseSecond> Return boost::operator/(const boost::divide_op_first_archetype<Return, BaseFirst>&, const boost::divide_op_second_archetype<Return, BaseSecond>&)
C:\boost\boost_1_48_0/boost/graph/two_bit_color_map.hpp:89:58: error: no match for 'operator%' in 'i % elements_per_char'
C:\boost\boost_1_48_0/boost/graph/two_bit_color_map.hpp:89:58: note: candidates are:
C:\boost\boost_1_48_0/boost/concept_archetype.hpp:317:3: note: template<class Base> boost::modable_archetype<Base> boost::operator%(const boost::modable_archetype<Base>&, const boost::modable_archetype<Base>&)
C:\boost\boost_1_48_0/boost/concept_archetype.hpp:346:3: note: template<class Return, class BaseFirst, class BaseSecond> Return boost::operator%(const boost::mod_op_first_archetype<Return, BaseFirst>&, const boost::mod_op_second_archetype<Return, BaseSecond>&)

I have toiled with this for a long time and I don't seem to be arriving at a solution. I thought I'd ask some one here before I give up on BGL :(

Thanks

Thanks to everybody who gave their time. – Sujay Anand Nov 14 '13 at 15:11 — Sujay Anand, Nov 14 '13 at 15:11

score 8 · Answer 1 · answered Oct 31 '13 at 22:14

8

The error message says that compiler does not find proper vertex_index_t property - a critical element for all search algorithms from Boost.Graph. It is not enough to define a class VertexIndexMap, you also have to tell Boost that this is your "vertex_index".

You can try to add declarations similar to following:

class VertexIndexMap //maps vertex to index
{
public:
    typedef boost::readable_property_map_tag category; 
    typedef size_t  value_type;
    typedef value_type reference;
    typedef BusRouteGraph::vertex_descriptor key_type; 

    VertexIndexMap(const BusRouteGraph& g): _g(&g) {} 

    const BusRouteGraph * _g;
};

namespace boost {

template<>
struct property_map<BusRouteGraph, vertex_index_t > {
    typedef VertexIndexMap const_type;
    //typedef type const_type ; //-- we do not define type as "vertex_index_t" map is read-only 
};

VertexIndexMap get(boost::vertex_index_t, const BusRouteGraph & g )
{
    return VertexIndexMap(g);
}

VertexIndexMap::value_type get(VertexIndexMap map, VertexIndexMap::key_type vertex)
{
    return (*map._g)[vertex].id;
}

} //namespace boost

After that you can drop the loop which inits the index_map; instead we use standard "Boost-ish" way to get the index map

VertexIndexMap index_map = get(boost::vertex_index, g); ///replaces get(&BusStop::id, g);

Then everything should work OK.

Good luck!

answered Oct 31 '13 at 22:14

Michael Simbirsky

3,045
1
12
24

Thanks for helping me learn BGL a little bit more. I actually got past this problem in a different way. I changed the graph from have setS as the vertex container to have vecS as the vertex container and the code compiles without these nasty template compilation error and it works correctly too. But I will try your solution one of these days by reverting back to setS and see how it goes. But don't hold your breath for it :) – Sujay Anand Nov 14 '13 at 15:11
Will the `adjacency_list` implementation insert unique ids in such a an associated property map? I don't know how it could e.g. remove elements from the index on `remove_vertex`? I find this approach very interesting, but I don't know what level of "automagic" to expect (I actually expect none, which means I'm surprised we "you can drop the loop which inits the index_map; instead we use standard "Boost-ish" way to get the index map") – sehe Apr 14 '15 at 06:27
1

@sehe. I agree, this approach leaves on the user to maintain the validity of "vertex_index" map. For example, initial answer assumes that all elements BusStop::id are unique and provide a proper mapping. There is no "automagic" in this approach. In fact no approach seems to work well when vertex is removed unless vertex container is `vecS`. One has to update or re-create the vertex index map before the calls to shortest path search. As @sehe suggested elsewhere one can keep index_map separately from the graph in some container and then pass as .vertex_index_map named parameter. – Michael Simbirsky Apr 14 '15 at 07:53
@MichaelSimbirsky Thanks for clarifying. I was kinda hoping there was some "customization point" inside adjacency_list itself for this. I guess it's sad that there isn't, but at least now I know more about it, so I can take it into account. Cheers – sehe Apr 14 '15 at 07:59
@sehe, as we know, the "automatic" index works well for vecS -- but not for other generators. Probably, this is the reason no automatic index is provided for them. In practice people often maintain this index anyway for other purposes. The code above, injected into boost namespace, shows how to connect BGL with such custom index. In a similar manner, one can also add specialization to the global function `remove_vertex` to update both the graph and the [custom] index. – Michael Simbirsky Apr 14 '15 at 08:10

BGL dijkstra_shortest_path algorithm method does not accept my color map exterior property

1 Answers1

Linked