1
我是BGL的新手，尝试使用BGL设置简单的最短路径查找程序，其中无向图被定义为具有自定义EdgeProperty和VertexProperty的邻接列表。我得到编译时错误，我认为我的模板和Boost技能不足。 代码如下：Boost图库使用捆绑属性
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/directed_graph.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include<iostream>
#include <map>
using namespace std;
using namespace boost;
enum Node_type
{
STAIR,
LEVEL,
LIFT,
OTHER,
UNKNOWN
};
class VertexProperty
{
public:
VertexProperty(){ id=-1; type=Node_type::UNKNOWN, level_id=254, stair_id=254;}
std::string toString()
{
std::string str;
str = "id "+to_string(id)+" type "+to_string(type)+" level "+to_string(level_id)+" stair_id "+to_string(stair_id);
return str;
}
int getVertexID() {return id;}
int id;
Node_type type;
int level_id;
int stair_id;
};
class EdgeProperty
{
public:
EdgeProperty(){id=-1, weight=0;}
EdgeProperty(int i, double wt){ id=i; weight=wt; }
double getWeigth(){ return weight;}
int getID() {return id;}
std::string toString()
{
std::string str;
str = "id "+to_string(id)+" weight="+to_string(weight);
return str;
}
int id;
double weight;
};
typedef boost::property<boost::edge_weight_t, double> EdgeWeigthProperty;
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,VertexProperty, EdgeProperty> UndirectedGraph;
typedef boost::graph_traits<UndirectedGraph>::edge_iterator edge_iterator;
typedef boost::graph_traits<UndirectedGraph>::vertex_iterator vertex_iterator;
typedef boost::directed_graph <boost::no_property, EdgeWeigthProperty> DirectedGraph;
typedef boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_descriptor;
typedef boost::graph_traits<UndirectedGraph>::edge_descriptor edge_descriptor;
class A
{
public:
A();
void undirected_graph_creation();
void directed_graph_creation();
void showEdges();
void showVertices();
void run_dijkastra();
UndirectedGraph g;
DirectedGraph dg;
map<int, vertex_descriptor> map_id_vertex_desc;
map<int, edge_descriptor> map_id_edge_desc;
map<int, Node_type> map_node_id_type;
};
A::A()
{
}
void A::undirected_graph_creation()
{
UndirectedGraph::vertex_descriptor v0= boost::add_vertex(g);
map_id_vertex_desc.emplace(0,v0);
g[v0].id=0;
g[v0].type=Node_type::LEVEL;
UndirectedGraph::vertex_descriptor v1= boost::add_vertex(g);
g[v1].id=1;
g[v1].type=Node_type::STAIR;
map_id_vertex_desc.emplace(1,v1);
UndirectedGraph::vertex_descriptor v2= boost::add_vertex(g);
map_id_vertex_desc.emplace(2,v2);
g[v2].id=2;
g[v2].type=Node_type::STAIR;
UndirectedGraph::vertex_descriptor v3= boost::add_vertex(g);
map_id_vertex_desc.emplace(3,v3);
g[v3].id=3;
g[v3].type=Node_type::STAIR;
/*EdgeWeigthProperty w8(8);
EdgeWeigthProperty w18(18);
EdgeWeigthProperty w20(20);
EdgeWeigthProperty w2(2);
EdgeWeigthProperty w7(7);*/
EdgeProperty w8(1,8);
EdgeProperty w18(2,18);
EdgeProperty w20(3,20);
EdgeProperty w2(4,2);
EdgeProperty w7(5,7);
boost::add_edge(v0,v1,w8,g);
boost::add_edge(v0,v3,w18,g);
boost::add_edge(v1,v2,w20,g);
boost::add_edge(v2,v3,w2,g);
boost::add_edge(v1,v3,w7,g);
}
void A::showEdges()
{
std::pair<edge_iterator,edge_iterator> ei=edges(g);
std::cout<<" number of edges "<<num_edges(g)<<endl;
std::cout<<" Edge list ";
for(edge_iterator it= ei.first; it!=ei.second; ++it)
cout<<*it<<" "<<g[*it].toString()<<endl;
}
void A::showVertices()
{
std::pair<vertex_iterator, vertex_iterator> vi= boost::vertices(g);
std::cout<<" Number of vertices are "<<endl;
for(vertex_iterator i = vi.first; i!=vi.second; ++i)
{
cout<<*i<<" id="<<g[*i].toString()<<" type="<<g[*i].type<<endl;
}
}
void A::run_dijkastra()
{
std::vector<vertex_descriptor> predecessors(boost::num_vertices(g));
std::vector<EdgeProperty> distances(boost::num_vertices(g));
std::pair<vertex_iterator,vertex_iterator> vi=boost::vertices(g);
vertex_descriptor first_vertex_descriptor = *(vi.first);
vertex_descriptor start_vertex = boost::vertex(0,g);
// boost::dijkstra_shortest_paths(g, first_vertex_descriptor,
// boost::weight_map(get(&EdgeProperty::weight,g))
// .distance_map(boost::make_iterator_property_map(distances.begin(), get(boost::vertex_index, g))) );
dijkstra_shortest_paths(g, first_vertex_descriptor,
predecessor_map(make_iterator_property_map(predecessors.begin(), get(vertex_index,g))).distance_map(make_iterator_property_map(distances.begin(), get(boost::vertex_index,g))).weight_map(get(&EdgeProperty::weight,g));
/*
std::cout << "distances and parents:" << std::endl;
graph_traits <UndirectedGraph>::vertex_iterator vi1, vend1;
for (boost::tie(vi1, vend1) = vertices(g); vi1 != vend1; ++vi1) {
std::cout << "distance(" << g[*vi1].id << ") = " << distances[*vi1].toString() << ", ";
std::cout << "parent(" << g[*vi1].id << ") = " << g[predecessors[*vi1]].id << std::
endl;
}*/
}
void A::directed_graph_creation()
{
//todo
}
int main()
{
A a_graph;
a_graph.undirected_graph_creation();
a_graph.showEdges();
a_graph.showVertices();;
a_graph.run_dijkastra();
return 0;
}
错误是从双到EdgeProperty正是未知的转换。看起来我在调用dijkstra_shortest_paths函数的语法上有错误。
我还想用函数替换EdgeProperty的数据成员。
我的其他查询是关于通过顶点描述符维护节点的索引。目前，我正在使用VertexProperty :: id做一个字典来维护VertexProperty类型的对象。 Do Boost在内部维护我可以使用的任何字典。
我使用在Ubuntu 16.04 gcc5.4版本的编译器谢谢
尼廷
你需要'distances'是一个'的std ::矢量'。 –
llonesmiz
太多的问题，太多的代码（所有的评论与它有什么关系？） – sehe