我一直在尝试让 boost graph lib 的 dijkstra_shortest_paths 编译大约一个星期，现在无济于事。我正在尝试为模板化方法所需的不同命名参数使用外部属性映射。我的图使用顶点和边的捆绑属性，我已经能够成功构建图。我将向您展示我的代码:

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

这是我尝试在给定图上执行 dijkstra 最短路径的方法:

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 之前先问问这里的人 :(

谢谢

最佳答案

错误消息表明编译器没有找到合适的 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);

然后一切都应该正常工作。

祝你好运!

关于c++ - BGL dijkstra_shortest_path 算法方法不接受我的颜色图外部属性，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11336723/