基于 BGL 的新 class 中自定义函数 addEdge 的 return 值应该是多少？
What should be the return value of a custom function addEdge in a new class based on BGL?
我尝试根据 实现图表 class。添加边时我return添加边的边描述符，但如果边已经存在，则不应添加。那我return怎么办？不幸的是，null_edge() 不存在（与 null_vertex() 不同）。它可能是具有适当边迭代器类型 e_it_t 的 std::pair<e_it_t,bool>，但我怎样才能获得指向新边的迭代器？
不要使用快 10 年的 class。它已过时。
据我所知，Bundled properties 已经加入 BGL，这可能是...... 至少从 2010 年开始。从根本上说，没有什么比直接提升更容易了。
另一个奇怪的 属性 是不知何故只能在该图中插入互补边。这可能是您想要的，但它并不能保证拥有完整的 class，IMO。
事实上，拥有自定义类型会删除 ADL，这会让事情变得更加乏味，除非你去添加彼此的操作（比如，你知道的，out_edges 或 in_edges，这大概就是你首先想要一个双向图；也许你真的希望有可迭代的范围而不是 pair<iterator, iterator>，这需要你编写老式的 for 循环）。
既然我已经热身了，让我们演示一下：
使用过时的包装器class
链接包装器提供如下用法：
struct VertexProperties { int i; };
struct EdgeProperties { double weight; };
int main() {
using MyGraph = Graph<VertexProperties, EdgeProperties>;
MyGraph g;
VertexProperties vp;
vp.i = 42;
MyGraph::Vertex v1 = g.AddVertex(vp);
g.properties(v1).i = 23;
MyGraph::Vertex v2 = g.AddVertex(vp);
g.properties(v2).i = 67;
g.AddEdge(v1, v2, EdgeProperties{1.0}, EdgeProperties{0.0});
for (auto vr = g.getVertices(); vr.first!=vr.second; ++vr.first) {
auto& vp = g.properties(*vr.first);
std::cout << "Vertex " << vp.i << "\n";
for (auto er = g.getAdjacentVertices(*vr.first); er.first!=er.second; ++er.first) {
auto s = *vr.first;
auto t = *er.first;
// erm how to get edge properties now?
std::cout << "Edge " << g.properties(s).i << " -> " << g.properties(t).i << " (weight?!?)\n";
}
}
}
打印：
Vertex 23
Edge 23 -> 67 (weight?!?)
Vertex 67
Edge 67 -> 23 (weight?!?)
请注意，我并没有费心去解决获取边权重的问题（我们根本不容易从界面中获取边描述符）。
for 循环让我们回到了至少 6 年前。这几乎不是最糟糕的问题。据推测，您需要图表来做某事。假设您想要最小切割或最短路径。这意味着您要调用需要边权重的算法。这看起来像这样：
// let's find a shortest path:
// build the vertex index map
boost::property_map<MyGraph::GraphContainer, vertex_properties_t>::const_type vpmap =
boost::get(vertex_properties, g.getGraph());
// oops we need the id from it. No problem, it takes only rocket science:
struct GetId {
int operator()(VertexProperties const& vp) const {
return vp.i;
}
};
GetId get_id;
boost::transform_value_property_map<GetId,
boost::property_map<MyGraph::GraphContainer, vertex_properties_t>::const_type,
int> id_map
= boost::make_transform_value_property_map<int>(get_id, vpmap);
// build the weight map
boost::property_map<MyGraph::GraphContainer, edge_properties_t>::const_type epmap =
boost::get(edge_properties, g.getGraph());
// oops we need the weight from it. No problem, it takes only rocket science:
struct GetWeight {
double operator()(EdgeProperties const& ep) const {
return ep.weight;
}
};
GetWeight get_weight;
boost::transform_value_property_map<GetWeight,
boost::property_map<MyGraph::GraphContainer, edge_properties_t>::const_type,
double> weight_map
= boost::make_transform_value_property_map<double>(get_weight, epmap);
// and now we "simply" use Dijkstra:
MyGraph::vertex_range_t vertices = g.getVertices();
//size_t n_vertices = g.getVertexCount();
MyGraph::Vertex source = *vertices.first;
std::map<MyGraph::Vertex, MyGraph::Vertex> predecessors;
std::map<MyGraph::Vertex, double> distance;
boost::dijkstra_shortest_paths(g.getGraph(), source,
boost::predecessor_map(boost::make_assoc_property_map(predecessors))
.distance_map(boost::make_assoc_property_map(distance))
.weight_map(weight_map)
.vertex_index_map(id_map));
这不是我对可用性的看法。只是为了展示它所有的编译和运行：
替换 2 行 C++11 中的包装器
让我们用现代 BGL 风格替换整个图形 class 模板：
template <typename VertexProperties, typename EdgeProperties>
using Graph = adjacency_list<setS, listS, bidirectionalS, VertexProperties, EdgeProperties>;
真的。这是一个可靠的替代品，我会马上演示。
In fact, let's not do using namespace boost; because it pollutes our namespace with all manner of names we might find really useful (like, you know source or num_vertices) and invites ambiguous symbols:
template <typename VertexProperties, typename EdgeProperties>
using Graph = boost::adjacency_list<boost::setS, boost::listS, boost::bidirectionalS, VertexProperties, EdgeProperties>;
相同的用例 - 创建和 dijkstra
它们仍然很简单，或者实际上更简单。完整代码从 249 行代码减少到 57 行：
#include <boost/graph/adjacency_list.hpp>
namespace MyLib {
template <typename VertexProperties, typename EdgeProperties>
using Graph = boost::adjacency_list<boost::setS, boost::listS, boost::bidirectionalS, VertexProperties, EdgeProperties>;
}
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <iostream>
struct VertexProperties { int i; };
struct EdgeProperties { double weight; };
int main() {
using boost::make_iterator_range;
using MyGraph = MyLib::Graph<VertexProperties, EdgeProperties>;
MyGraph g;
auto v1 = add_vertex({42}, g);
auto v2 = add_vertex({42}, g);
g[v1].i = 23;
g[v2].i = 67;
add_edge(v1, v2, EdgeProperties{ 1.0 }, g);
add_edge(v2, v1, EdgeProperties{ 0.0 }, g);
for (auto v : make_iterator_range(vertices(g))) {
std::cout << "Vertex " << g[v].i << "\n";
}
for (auto e : make_iterator_range(boost::edges(g))) {
auto s = source(e, g);
auto t = target(e, g);
std::cout << "Edge " << g[s].i << " -> " << g[t].i << " (weight = " << g[e].weight << ")\n";
}
// let's find a shortest path:
auto id_map = get(&VertexProperties::i, g);
auto weight_map = get(&EdgeProperties::weight, g);
auto source = *vertices(g).first;
using Vertex = MyGraph::vertex_descriptor;
std::map<Vertex, Vertex> predecessors;
std::map<Vertex, double> distance;
std::map<Vertex, boost::default_color_type> colors;
boost::dijkstra_shortest_paths(
g, source,
boost::vertex_color_map(boost::make_assoc_property_map(colors))
.predecessor_map(boost::make_assoc_property_map(predecessors))
.distance_map(boost::make_assoc_property_map(distance))
.weight_map(weight_map)
.vertex_index_map(id_map));
}
我会说
- 那是优越的。
- 尽管不依赖
using namespace boost也一样优雅（ADL是这里的关键）
- 我们实际上打印了边缘权重！
它还可以更干净
如果切换到具有隐式顶点索引的顶点容器选择器（如 vecS）：
#include <boost/graph/adjacency_list.hpp>
namespace MyLib {
template <typename VertexProperties, typename EdgeProperties>
using Graph = boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS, VertexProperties, EdgeProperties>;
}
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <iostream>
struct VertexProperties { int i; };
struct EdgeProperties { double weight; };
int main() {
using boost::make_iterator_range;
using MyGraph = MyLib::Graph<VertexProperties, EdgeProperties>;
MyGraph g;
add_vertex({23}, g);
add_vertex({67}, g);
add_edge(0, 1, EdgeProperties{ 1.0 }, g);
add_edge(1, 0, EdgeProperties{ 0.0 }, g);
for (auto v : make_iterator_range(vertices(g))) {
std::cout << "Vertex " << g[v].i << "\n";
}
for (auto e : make_iterator_range(boost::edges(g))) {
auto s = source(e, g);
auto t = target(e, g);
std::cout << "Edge " << g[s].i << " -> " << g[t].i << " (weight = " << g[e].weight << ")\n";
}
// let's find a shortest path:
std::vector<size_t> predecessors(num_vertices(g));
std::vector<double> distance(num_vertices(g));
boost::dijkstra_shortest_paths(g, *vertices(g).first,
boost::predecessor_map(predecessors.data()).distance_map(distance.data())
.weight_map(get(&EdgeProperties::weight, g)));
}
输出：
Vertex 23
Vertex 67
Edge 23 -> 67 (weight = 1)
Edge 67 -> 23 (weight = 0)
等等 - 不要忘记问题！
我不会！我认为以上显示问题是 an X/Y problem.
如果您没有自定义 class 环绕的障碍，检测重复边缘是给定的（请参阅 了解背景）：
struct { size_t from, to; double weight; } edge_data[] = {
{0, 1, 1.0},
{1, 0, 0.0},
{0, 1, 99.999} // oops, a duplicate
};
for(auto request : edge_data) {
auto addition = add_edge(request.from, request.to, { request.weight }, g);
if (!addition.second) {
auto& weight = g[addition.first].weight;
std::cout << "Edge already existed, changing weight from " << weight << " to " << request.weight << "\n";
weight = request.weight;
}
}
这将打印 Live On Coliru:
Edge already existed, changing weight from 1 to 99.999
如果你愿意，你当然可以写得更有表现力：
Graph::edge_descriptor e;
bool inserted;
boost::tie(e, inserted) = add_edge(request.from, request.to, { request.weight }, g);
或者，具有一些 c++17 天赋：
auto [e, inserted] = add_edge(request.from, request.to, { request.weight }, g);
更多来自这里
此外，您很可能也需要对顶点进行唯一性检查，因此您最终会得到图形创建代码，就像您在这个答案中看到的那样：
Graph read_graph() {
std::istringstream iss(R"(
0 1 0.001
0 2 0.1
0 3 0.001
1 5 0.001
2 3 0.001
3 4 0.1
1 482 0.1
482 635 0.001
4 705 0.1
705 5 0.1
1 1491 0.01
1 1727 0.01
1 1765 0.01)");
Graph g;
std::map<int,Vertex> idx; // temporary lookup of existing vertices
auto vertex = [&](int id) mutable {
auto it = idx.find(id);
if (it != idx.end())
return it->second;
return idx.emplace(id, add_vertex(id, g)).first->second;
};
for (std::string line; getline(iss, line);) {
std::istringstream ls(line);
int s,t; double w;
if (ls >> s >> t >> w) {
add_edge(vertex(s), vertex(t), w, g);
} else {
std::cerr << "Skipped invalid line '" << line << "'\n";
}
}
return g;
}
其他示例显示了如何插入 a -> b 和 b -> a，同时保持前向和后向边缘之间的映射：
总结
绕一圈，我建议您熟悉更新、更优雅的 Boost Graph 功能。最后，封装你的图表是完全正常的，你最终可能会得到一个更完美的界面。
我尝试根据 实现图表 class。添加边时我return添加边的边描述符，但如果边已经存在，则不应添加。那我return怎么办？不幸的是，null_edge() 不存在（与 null_vertex() 不同）。它可能是具有适当边迭代器类型 e_it_t 的 std::pair<e_it_t,bool>，但我怎样才能获得指向新边的迭代器？
不要使用快 10 年的 class。它已过时。
据我所知，Bundled properties 已经加入 BGL，这可能是...... 至少从 2010 年开始。从根本上说，没有什么比直接提升更容易了。
另一个奇怪的 属性 是不知何故只能在该图中插入互补边。这可能是您想要的，但它并不能保证拥有完整的 class，IMO。
事实上，拥有自定义类型会删除 ADL，这会让事情变得更加乏味，除非你去添加彼此的操作（比如，你知道的，out_edges 或 in_edges，这大概就是你首先想要一个双向图；也许你真的希望有可迭代的范围而不是 pair<iterator, iterator>，这需要你编写老式的 for 循环）。
既然我已经热身了，让我们演示一下：
使用过时的包装器class
链接包装器提供如下用法：
struct VertexProperties { int i; };
struct EdgeProperties { double weight; };
int main() {
using MyGraph = Graph<VertexProperties, EdgeProperties>;
MyGraph g;
VertexProperties vp;
vp.i = 42;
MyGraph::Vertex v1 = g.AddVertex(vp);
g.properties(v1).i = 23;
MyGraph::Vertex v2 = g.AddVertex(vp);
g.properties(v2).i = 67;
g.AddEdge(v1, v2, EdgeProperties{1.0}, EdgeProperties{0.0});
for (auto vr = g.getVertices(); vr.first!=vr.second; ++vr.first) {
auto& vp = g.properties(*vr.first);
std::cout << "Vertex " << vp.i << "\n";
for (auto er = g.getAdjacentVertices(*vr.first); er.first!=er.second; ++er.first) {
auto s = *vr.first;
auto t = *er.first;
// erm how to get edge properties now?
std::cout << "Edge " << g.properties(s).i << " -> " << g.properties(t).i << " (weight?!?)\n";
}
}
}
打印：
Vertex 23
Edge 23 -> 67 (weight?!?)
Vertex 67
Edge 67 -> 23 (weight?!?)
请注意，我并没有费心去解决获取边权重的问题（我们根本不容易从界面中获取边描述符）。 for 循环让我们回到了至少 6 年前。这几乎不是最糟糕的问题。据推测，您需要图表来做某事。假设您想要最小切割或最短路径。这意味着您要调用需要边权重的算法。这看起来像这样：
// let's find a shortest path:
// build the vertex index map
boost::property_map<MyGraph::GraphContainer, vertex_properties_t>::const_type vpmap =
boost::get(vertex_properties, g.getGraph());
// oops we need the id from it. No problem, it takes only rocket science:
struct GetId {
int operator()(VertexProperties const& vp) const {
return vp.i;
}
};
GetId get_id;
boost::transform_value_property_map<GetId,
boost::property_map<MyGraph::GraphContainer, vertex_properties_t>::const_type,
int> id_map
= boost::make_transform_value_property_map<int>(get_id, vpmap);
// build the weight map
boost::property_map<MyGraph::GraphContainer, edge_properties_t>::const_type epmap =
boost::get(edge_properties, g.getGraph());
// oops we need the weight from it. No problem, it takes only rocket science:
struct GetWeight {
double operator()(EdgeProperties const& ep) const {
return ep.weight;
}
};
GetWeight get_weight;
boost::transform_value_property_map<GetWeight,
boost::property_map<MyGraph::GraphContainer, edge_properties_t>::const_type,
double> weight_map
= boost::make_transform_value_property_map<double>(get_weight, epmap);
// and now we "simply" use Dijkstra:
MyGraph::vertex_range_t vertices = g.getVertices();
//size_t n_vertices = g.getVertexCount();
MyGraph::Vertex source = *vertices.first;
std::map<MyGraph::Vertex, MyGraph::Vertex> predecessors;
std::map<MyGraph::Vertex, double> distance;
boost::dijkstra_shortest_paths(g.getGraph(), source,
boost::predecessor_map(boost::make_assoc_property_map(predecessors))
.distance_map(boost::make_assoc_property_map(distance))
.weight_map(weight_map)
.vertex_index_map(id_map));
这不是我对可用性的看法。只是为了展示它所有的编译和运行：
替换 2 行 C++11 中的包装器
让我们用现代 BGL 风格替换整个图形 class 模板：
template <typename VertexProperties, typename EdgeProperties>
using Graph = adjacency_list<setS, listS, bidirectionalS, VertexProperties, EdgeProperties>;
真的。这是一个可靠的替代品，我会马上演示。
In fact, let's not do
using namespace boost;because it pollutes our namespace with all manner of names we might find really useful (like, you knowsourceornum_vertices) and invites ambiguous symbols:template <typename VertexProperties, typename EdgeProperties> using Graph = boost::adjacency_list<boost::setS, boost::listS, boost::bidirectionalS, VertexProperties, EdgeProperties>;
相同的用例 - 创建和 dijkstra
它们仍然很简单，或者实际上更简单。完整代码从 249 行代码减少到 57 行：
#include <boost/graph/adjacency_list.hpp>
namespace MyLib {
template <typename VertexProperties, typename EdgeProperties>
using Graph = boost::adjacency_list<boost::setS, boost::listS, boost::bidirectionalS, VertexProperties, EdgeProperties>;
}
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <iostream>
struct VertexProperties { int i; };
struct EdgeProperties { double weight; };
int main() {
using boost::make_iterator_range;
using MyGraph = MyLib::Graph<VertexProperties, EdgeProperties>;
MyGraph g;
auto v1 = add_vertex({42}, g);
auto v2 = add_vertex({42}, g);
g[v1].i = 23;
g[v2].i = 67;
add_edge(v1, v2, EdgeProperties{ 1.0 }, g);
add_edge(v2, v1, EdgeProperties{ 0.0 }, g);
for (auto v : make_iterator_range(vertices(g))) {
std::cout << "Vertex " << g[v].i << "\n";
}
for (auto e : make_iterator_range(boost::edges(g))) {
auto s = source(e, g);
auto t = target(e, g);
std::cout << "Edge " << g[s].i << " -> " << g[t].i << " (weight = " << g[e].weight << ")\n";
}
// let's find a shortest path:
auto id_map = get(&VertexProperties::i, g);
auto weight_map = get(&EdgeProperties::weight, g);
auto source = *vertices(g).first;
using Vertex = MyGraph::vertex_descriptor;
std::map<Vertex, Vertex> predecessors;
std::map<Vertex, double> distance;
std::map<Vertex, boost::default_color_type> colors;
boost::dijkstra_shortest_paths(
g, source,
boost::vertex_color_map(boost::make_assoc_property_map(colors))
.predecessor_map(boost::make_assoc_property_map(predecessors))
.distance_map(boost::make_assoc_property_map(distance))
.weight_map(weight_map)
.vertex_index_map(id_map));
}
我会说
- 那是优越的。
- 尽管不依赖
using namespace boost也一样优雅（ADL是这里的关键） - 我们实际上打印了边缘权重！
它还可以更干净
如果切换到具有隐式顶点索引的顶点容器选择器（如 vecS）：
#include <boost/graph/adjacency_list.hpp>
namespace MyLib {
template <typename VertexProperties, typename EdgeProperties>
using Graph = boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS, VertexProperties, EdgeProperties>;
}
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <iostream>
struct VertexProperties { int i; };
struct EdgeProperties { double weight; };
int main() {
using boost::make_iterator_range;
using MyGraph = MyLib::Graph<VertexProperties, EdgeProperties>;
MyGraph g;
add_vertex({23}, g);
add_vertex({67}, g);
add_edge(0, 1, EdgeProperties{ 1.0 }, g);
add_edge(1, 0, EdgeProperties{ 0.0 }, g);
for (auto v : make_iterator_range(vertices(g))) {
std::cout << "Vertex " << g[v].i << "\n";
}
for (auto e : make_iterator_range(boost::edges(g))) {
auto s = source(e, g);
auto t = target(e, g);
std::cout << "Edge " << g[s].i << " -> " << g[t].i << " (weight = " << g[e].weight << ")\n";
}
// let's find a shortest path:
std::vector<size_t> predecessors(num_vertices(g));
std::vector<double> distance(num_vertices(g));
boost::dijkstra_shortest_paths(g, *vertices(g).first,
boost::predecessor_map(predecessors.data()).distance_map(distance.data())
.weight_map(get(&EdgeProperties::weight, g)));
}
输出：
Vertex 23
Vertex 67
Edge 23 -> 67 (weight = 1)
Edge 67 -> 23 (weight = 0)
等等 - 不要忘记问题！
我不会！我认为以上显示问题是 an X/Y problem.
如果您没有自定义 class 环绕的障碍，检测重复边缘是给定的（请参阅
struct { size_t from, to; double weight; } edge_data[] = {
{0, 1, 1.0},
{1, 0, 0.0},
{0, 1, 99.999} // oops, a duplicate
};
for(auto request : edge_data) {
auto addition = add_edge(request.from, request.to, { request.weight }, g);
if (!addition.second) {
auto& weight = g[addition.first].weight;
std::cout << "Edge already existed, changing weight from " << weight << " to " << request.weight << "\n";
weight = request.weight;
}
}
这将打印 Live On Coliru:
Edge already existed, changing weight from 1 to 99.999
如果你愿意，你当然可以写得更有表现力：
Graph::edge_descriptor e;
bool inserted;
boost::tie(e, inserted) = add_edge(request.from, request.to, { request.weight }, g);
或者，具有一些 c++17 天赋：
auto [e, inserted] = add_edge(request.from, request.to, { request.weight }, g);
更多来自这里
此外，您很可能也需要对顶点进行唯一性检查，因此您最终会得到图形创建代码，就像您在这个答案中看到的那样：
Graph read_graph() {
std::istringstream iss(R"(
0 1 0.001
0 2 0.1
0 3 0.001
1 5 0.001
2 3 0.001
3 4 0.1
1 482 0.1
482 635 0.001
4 705 0.1
705 5 0.1
1 1491 0.01
1 1727 0.01
1 1765 0.01)");
Graph g;
std::map<int,Vertex> idx; // temporary lookup of existing vertices
auto vertex = [&](int id) mutable {
auto it = idx.find(id);
if (it != idx.end())
return it->second;
return idx.emplace(id, add_vertex(id, g)).first->second;
};
for (std::string line; getline(iss, line);) {
std::istringstream ls(line);
int s,t; double w;
if (ls >> s >> t >> w) {
add_edge(vertex(s), vertex(t), w, g);
} else {
std::cerr << "Skipped invalid line '" << line << "'\n";
}
}
return g;
}
其他示例显示了如何插入 a -> b 和 b -> a，同时保持前向和后向边缘之间的映射：
总结
绕一圈，我建议您熟悉更新、更优雅的 Boost Graph 功能。最后，封装你的图表是完全正常的，你最终可能会得到一个更完美的界面。