BGL dijkstra_shortest_path算法方法不接受我的颜色图外部属性 [英] BGL dijkstra_shortest_path algorithm method does not accept my color map exterior property
问题描述
我一直试图得到提升图表lib的dijkstra_shortest_paths编译大约一个星期,现在没有效果。我试图使用外部属性映射的模板方法所需的不同的命名参数。我的图使用捆绑属性的顶点和边缘,我已经能够成功地构建图。我会告诉你我的代码:
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;
};
这是我的图表声明:
typedef boost :: adjacency_list& boost :: vecS,boost :: setS,boost :: undirectedS,BusStop,Route> BusRouteGraph;
这是我的方法,试图做dijkstra的给定图上的最短路径:
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;
}
我得到了这些编译时错误:(仅下面的第一个错误) p>
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>&)
我已经很久了,我似乎没有得到一个解决方案。我想我会在我放弃BGL之前问一个这样的人:(
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 :(
谢谢
推荐答案
错误消息说编译器没有找到合适的vertex_index_t属性 - 从Boost.Graph的所有搜索算法的关键元素。仅仅定义一个类VertexIndexMap是不够的,你也必须告诉Boost这是您的vertex_index。
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
可以丢弃在index_map中的循环;我们使用标准的Boost-ish方法来获取索引映射
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.
祝你好运!
这篇关于BGL dijkstra_shortest_path算法方法不接受我的颜色图外部属性的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!