4

我一直试图让 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 之前，我想我会在这里问一些人 :(

谢谢

4

1 回答 1

8

错误消息说编译器没有找到正确的 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);

然后一切都应该正常。

祝你好运！

于 2013-10-31T22:14:38.293 回答