Метод алгоритма BGL dijkstra_shortest_path не принимает свойство внешнего вида карты цветов

Я пытался компилировать dijkstra_shortest_paths библиотеки boost graph lib уже около недели, но безрезультатно. Я пытаюсь использовать внешние карты свойств для различных именованных параметров, требуемых шаблонным методом. Мой граф использует связанные свойства для вершины и ребер, и мне удалось успешно построить граф. Я покажу вам, что у меня есть для кода:

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

Вот мое объявление графа:

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

Вот мой метод, который пытается найти кратчайший путь Дейкстры на заданном графе:

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

Я получаю эти ошибки времени компиляции: (только первая ошибка ниже)

\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>&)

Я долго мучился с этим и, похоже, не нашел решения. Я подумал, что спрошу кого-нибудь здесь, прежде чем разочаруюсь в BGL :(

Спасибо


c++ boost-graph
person Sujay Anand    schedule 05.07.2012    source источник
comment
Спасибо всем, кто уделил свое время.   -  person Sujay Anand    schedule 14.11.2013

Ответы (1)


arrow_upward
8
arrow_downward

Сообщение об ошибке говорит о том, что компилятор не находит нужного свойства vertex_index_t — критического элемента для всех алгоритмов поиска от Boost.Graph. Недостаточно определить класс VertexIndexMap, вы также должны сообщить Boost, что это ваш «vertex_index».

Вы можете попробовать добавить объявления, подобные следующим:

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

После этого вы можете отказаться от цикла, который инициализирует index_map; вместо этого мы используем стандартный способ "Boost-ish" для получения индексной карты.

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

Тогда все должно работать нормально.

Удачи!

person Michael Simbirsky    schedule 31.10.2013
comment
Спасибо за помощь в изучении BGL. На самом деле я решил эту проблему по-другому. Я изменил график с setS в качестве контейнера вершин на vecS в качестве контейнера вершин, и код компилируется без этих неприятных ошибок компиляции шаблона, и он тоже работает правильно. Но на днях я попробую ваше решение, вернусь к setS и посмотрю, как оно пойдет. Но не задерживайте дыхание для этого :) - person Sujay Anand; 14.11.2013
comment
Будет ли реализация adjacency_list вставлять уникальные идентификаторы в такую ​​связанную карту свойств? Я не знаю, как это может быть, например. удалить элементы из индекса на remove_vertex? Я нахожу этот подход очень интересным, но я не знаю, какой уровень автоматической магии ожидать (на самом деле я не ожидаю его, что означает, что я удивлен, что вы можете отказаться от цикла, который инициализирует index_map; вместо этого мы используем стандартный способ Boost-ish чтобы получить индексную карту) - person sehe; 14.04.2015
comment
@сехе. Я согласен, этот подход оставляет за пользователем право поддерживать действительность карты vertex_index. Например, исходный ответ предполагает, что все элементы BusStop::id уникальны и обеспечивают правильное сопоставление. В этом подходе нет никакой автоматической магии. На самом деле ни один подход не работает хорошо, когда вершина удаляется, если только контейнер вершины не vecS. Необходимо обновить или пересоздать карту индекса вершин перед вызовами поиска кратчайшего пути. Как предложил @sehe в другом месте, index_map можно хранить отдельно от графика в каком-либо контейнере, а затем передавать как именованный параметр .vertex_index_map. - person Michael Simbirsky; 14.04.2015
comment
@MichaelSimbirsky Спасибо за разъяснение. Я надеялся, что внутри самого adjacency_list есть какая-то точка настройки для этого. Я думаю, это печально, что его нет, но, по крайней мере, теперь я знаю об этом больше, так что я могу принять это во внимание. Ваше здоровье - person sehe; 14.04.2015
comment
@sehe, как мы знаем, автоматический индекс хорошо работает для vecS, но не для других генераторов. Вероятно, по этой причине для них не предусмотрен автоматический индекс. На практике люди часто все равно используют этот индекс для других целей. Приведенный выше код, введенный в пространство имен boost, показывает, как подключить BGL к такому пользовательскому индексу. Аналогичным образом можно также добавить специализацию к глобальной функции remove_vertex для обновления как графа, так и [настраиваемого] индекса. - person Michael Simbirsky; 14.04.2015