使用捆绑属性提升图形库
Boost graph Library using Bundled properties
我是 BGL 的新手，正在尝试使用 BGL 设置一个简单的最短路径查找程序，其中无向图被定义为具有自定义 EdgeProperty 和 VertexProperty 的邻接列表。我收到编译时错误，我将其归因于我在模板和 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;
}
错误是从 double 到 EdgeProperty 的未知转换。看来我在调用 dijkstra_shortest_paths 函数的语法中有错误。
我也想用函数替换 EdgeProperty 的数据成员。
我的其他查询是关于通过顶点描述符维护节点的索引。目前，我正在使用 VertexProperty::id 维护 VertexProperty 类型对象的字典。 Do Boost 在内部维护我可以使用的任何字典。
我在 Ubuntu 16.04 上使用 gcc5.4 版本的编译器
谢谢
尼汀
@llonesmiz 说的很对。这是代码的一般清理和现场演示。
我也用make_transform_value_property_map来使用getWeight()，把所有数据成员设为私有
NOTE I suspect that the std::map instances aren't really useful anymore now that you use bundled properties (?). In any case, you could drop some code if you don't need them any more: Shorter Demo
NOTE You might not know about print_graph. Even Shorter, slightly abbreviated output
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
#include <iostream>
#include <map>
enum class Node_type { STAIR, LEVEL, LIFT, OTHER, UNKNOWN };
static std::ostream& operator<<(std::ostream& os, Node_type type) {
switch(type) {
case Node_type::STAIR: return os << "STAIR";
case Node_type::LEVEL: return os << "LEVEL";
case Node_type::LIFT: return os << "LIFT";
case Node_type::OTHER: return os << "OTHER";
default:
case Node_type::UNKNOWN: return os << "UNKNOWN";
}
}
class VertexProperty {
public:
VertexProperty(int id = -1, Node_type type = Node_type::UNKNOWN, int level_id=254, int stair_id=254)
: id(id), type(type), level_id(level_id), stair_id(stair_id) { }
std::string toString() const {
std::ostringstream oss;
oss << *this;
return oss.str();
}
int getVertexID() { return id; }
private:
friend std::ostream& operator<<(std::ostream& os, VertexProperty const& v) {
return os << "id " << v.id << " type " << v.type << " level " << v.level_id << " stair_id " << v.stair_id;
}
int id;
Node_type type;
int level_id;
int stair_id;
};
class EdgeProperty {
public:
EdgeProperty(int i = -1, double wt = 0) : id(i), weight(wt) {
id = i;
weight = wt;
}
double getWeight() { return weight; }
int getID() { return id; }
std::string toString() const {
std::ostringstream oss;
oss << *this;
return oss.str();
}
private:
friend std::ostream& operator<<(std::ostream& os, EdgeProperty const& e) {
return os << "id " << e.id << " weight=" << std::fixed << e.weight;
}
int id;
double weight;
};
class A {
public:
void undirected_graph_creation();
void showEdges();
void showVertices();
void runDijstra();
private:
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProperty, EdgeProperty> UndirectedGraph;
UndirectedGraph g;
using edge_iterator = UndirectedGraph::edge_iterator;
using vertex_iterator = UndirectedGraph::vertex_iterator;
using vertex_descriptor = UndirectedGraph::vertex_descriptor;
using edge_descriptor = UndirectedGraph::edge_descriptor;
std::map<int, vertex_descriptor> map_id_vertex_desc;
std::map<int, edge_descriptor> map_id_edge_desc;
std::map<int, Node_type> map_node_id_type;
};
void A::undirected_graph_creation() {
auto add_vertex = [this](int id, Node_type type) {
// TODO: these maps are probably not required anymore
map_node_id_type[id] = type;
vertex_descriptor vd = boost::add_vertex(VertexProperty{id, type}, g);
return map_id_vertex_desc[id] = vd;
};
auto v0 = add_vertex(0, Node_type::LEVEL);
auto v1 = add_vertex(1, Node_type::STAIR);
auto v2 = add_vertex(2, Node_type::STAIR);
auto v3 = add_vertex(3, Node_type::STAIR);
auto add_edge = [this](vertex_descriptor u, vertex_descriptor v, EdgeProperty prop) {
auto ins = boost::add_edge(u, v, prop, g);
if (ins.second)
map_id_edge_desc[prop.getID()] = ins.first;
return ins.first;
};
add_edge(v0, v1, {1, 8});
add_edge(v0, v3, {2, 18});
add_edge(v1, v2, {3, 20});
add_edge(v2, v3, {4, 2});
add_edge(v1, v3, {5, 7});
}
void A::showEdges() {
for (auto e : boost::make_iterator_range(boost::edges(g)))
std::cout << "Edge " << e << " " << g[e] << "\n";
}
void A::showVertices() {
for (auto v : boost::make_iterator_range(boost::vertices(g)))
std::cout << "Vertex " << v << " " << g[v] << "\n";
}
void A::runDijstra() {
std::vector<vertex_descriptor> predecessors(num_vertices(g));
std::vector<double> distances(num_vertices(g));
vertex_descriptor start = *(vertices(g).first);
auto v_index = get(boost::vertex_index, g);
auto weight = boost::make_transform_value_property_map(std::mem_fn(&EdgeProperty::getWeight), get(boost::edge_bundle, g));
dijkstra_shortest_paths(
g, start,
predecessor_map(make_iterator_property_map(predecessors.begin(), v_index))
.distance_map(make_iterator_property_map(distances.begin(), v_index))
.weight_map(weight));
std::cout << "distances and parents:\n";
for (auto v : boost::make_iterator_range(boost::vertices(g))) {
auto id = g[v].getVertexID();
std::cout << "distance(" << id << ") = " << distances[v] << ", ";
std::cout << "parent(" << id << ") = " << g[predecessors[v]] << "\n";
}
}
int main() {
A a;
a.undirected_graph_creation();
a.showEdges();
a.showVertices();
a.runDijstra();
}
打印：
Edge (0,1) id 1 weight=8.000000
Edge (0,3) id 2 weight=18.000000
Edge (1,2) id 3 weight=20.000000
Edge (2,3) id 4 weight=2.000000
Edge (1,3) id 5 weight=7.000000
Vertex 0 id 0 type LEVEL level 254 stair_id 254
Vertex 1 id 1 type STAIR level 254 stair_id 254
Vertex 2 id 2 type STAIR level 254 stair_id 254
Vertex 3 id 3 type STAIR level 254 stair_id 254
distances and parents:
distance(0) = 0.000000, parent(0) = id 0 type LEVEL level 254 stair_id 254
distance(1) = 8.000000, parent(1) = id 0 type LEVEL level 254 stair_id 254
distance(2) = 17.000000, parent(2) = id 3 type STAIR level 254 stair_id 254
distance(3) = 15.000000, parent(3) = id 1 type STAIR level 254 stair_id 254
我是 BGL 的新手，正在尝试使用 BGL 设置一个简单的最短路径查找程序，其中无向图被定义为具有自定义 EdgeProperty 和 VertexProperty 的邻接列表。我收到编译时错误，我将其归因于我在模板和 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;
}
错误是从 double 到 EdgeProperty 的未知转换。看来我在调用 dijkstra_shortest_paths 函数的语法中有错误。
我也想用函数替换 EdgeProperty 的数据成员。
我的其他查询是关于通过顶点描述符维护节点的索引。目前，我正在使用 VertexProperty::id 维护 VertexProperty 类型对象的字典。 Do Boost 在内部维护我可以使用的任何字典。
我在 Ubuntu 16.04 上使用 gcc5.4 版本的编译器 谢谢
尼汀
@llonesmiz 说的很对。这是代码的一般清理和现场演示。
我也用make_transform_value_property_map来使用getWeight()，把所有数据成员设为私有
NOTE I suspect that the
std::mapinstances aren't really useful anymore now that you use bundled properties (?). In any case, you could drop some code if you don't need them any more: Shorter DemoNOTE You might not know about
print_graph. Even Shorter, slightly abbreviated output
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
#include <iostream>
#include <map>
enum class Node_type { STAIR, LEVEL, LIFT, OTHER, UNKNOWN };
static std::ostream& operator<<(std::ostream& os, Node_type type) {
switch(type) {
case Node_type::STAIR: return os << "STAIR";
case Node_type::LEVEL: return os << "LEVEL";
case Node_type::LIFT: return os << "LIFT";
case Node_type::OTHER: return os << "OTHER";
default:
case Node_type::UNKNOWN: return os << "UNKNOWN";
}
}
class VertexProperty {
public:
VertexProperty(int id = -1, Node_type type = Node_type::UNKNOWN, int level_id=254, int stair_id=254)
: id(id), type(type), level_id(level_id), stair_id(stair_id) { }
std::string toString() const {
std::ostringstream oss;
oss << *this;
return oss.str();
}
int getVertexID() { return id; }
private:
friend std::ostream& operator<<(std::ostream& os, VertexProperty const& v) {
return os << "id " << v.id << " type " << v.type << " level " << v.level_id << " stair_id " << v.stair_id;
}
int id;
Node_type type;
int level_id;
int stair_id;
};
class EdgeProperty {
public:
EdgeProperty(int i = -1, double wt = 0) : id(i), weight(wt) {
id = i;
weight = wt;
}
double getWeight() { return weight; }
int getID() { return id; }
std::string toString() const {
std::ostringstream oss;
oss << *this;
return oss.str();
}
private:
friend std::ostream& operator<<(std::ostream& os, EdgeProperty const& e) {
return os << "id " << e.id << " weight=" << std::fixed << e.weight;
}
int id;
double weight;
};
class A {
public:
void undirected_graph_creation();
void showEdges();
void showVertices();
void runDijstra();
private:
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProperty, EdgeProperty> UndirectedGraph;
UndirectedGraph g;
using edge_iterator = UndirectedGraph::edge_iterator;
using vertex_iterator = UndirectedGraph::vertex_iterator;
using vertex_descriptor = UndirectedGraph::vertex_descriptor;
using edge_descriptor = UndirectedGraph::edge_descriptor;
std::map<int, vertex_descriptor> map_id_vertex_desc;
std::map<int, edge_descriptor> map_id_edge_desc;
std::map<int, Node_type> map_node_id_type;
};
void A::undirected_graph_creation() {
auto add_vertex = [this](int id, Node_type type) {
// TODO: these maps are probably not required anymore
map_node_id_type[id] = type;
vertex_descriptor vd = boost::add_vertex(VertexProperty{id, type}, g);
return map_id_vertex_desc[id] = vd;
};
auto v0 = add_vertex(0, Node_type::LEVEL);
auto v1 = add_vertex(1, Node_type::STAIR);
auto v2 = add_vertex(2, Node_type::STAIR);
auto v3 = add_vertex(3, Node_type::STAIR);
auto add_edge = [this](vertex_descriptor u, vertex_descriptor v, EdgeProperty prop) {
auto ins = boost::add_edge(u, v, prop, g);
if (ins.second)
map_id_edge_desc[prop.getID()] = ins.first;
return ins.first;
};
add_edge(v0, v1, {1, 8});
add_edge(v0, v3, {2, 18});
add_edge(v1, v2, {3, 20});
add_edge(v2, v3, {4, 2});
add_edge(v1, v3, {5, 7});
}
void A::showEdges() {
for (auto e : boost::make_iterator_range(boost::edges(g)))
std::cout << "Edge " << e << " " << g[e] << "\n";
}
void A::showVertices() {
for (auto v : boost::make_iterator_range(boost::vertices(g)))
std::cout << "Vertex " << v << " " << g[v] << "\n";
}
void A::runDijstra() {
std::vector<vertex_descriptor> predecessors(num_vertices(g));
std::vector<double> distances(num_vertices(g));
vertex_descriptor start = *(vertices(g).first);
auto v_index = get(boost::vertex_index, g);
auto weight = boost::make_transform_value_property_map(std::mem_fn(&EdgeProperty::getWeight), get(boost::edge_bundle, g));
dijkstra_shortest_paths(
g, start,
predecessor_map(make_iterator_property_map(predecessors.begin(), v_index))
.distance_map(make_iterator_property_map(distances.begin(), v_index))
.weight_map(weight));
std::cout << "distances and parents:\n";
for (auto v : boost::make_iterator_range(boost::vertices(g))) {
auto id = g[v].getVertexID();
std::cout << "distance(" << id << ") = " << distances[v] << ", ";
std::cout << "parent(" << id << ") = " << g[predecessors[v]] << "\n";
}
}
int main() {
A a;
a.undirected_graph_creation();
a.showEdges();
a.showVertices();
a.runDijstra();
}
打印：
Edge (0,1) id 1 weight=8.000000
Edge (0,3) id 2 weight=18.000000
Edge (1,2) id 3 weight=20.000000
Edge (2,3) id 4 weight=2.000000
Edge (1,3) id 5 weight=7.000000
Vertex 0 id 0 type LEVEL level 254 stair_id 254
Vertex 1 id 1 type STAIR level 254 stair_id 254
Vertex 2 id 2 type STAIR level 254 stair_id 254
Vertex 3 id 3 type STAIR level 254 stair_id 254
distances and parents:
distance(0) = 0.000000, parent(0) = id 0 type LEVEL level 254 stair_id 254
distance(1) = 8.000000, parent(1) = id 0 type LEVEL level 254 stair_id 254
distance(2) = 17.000000, parent(2) = id 3 type STAIR level 254 stair_id 254
distance(3) = 15.000000, parent(3) = id 1 type STAIR level 254 stair_id 254