在基于BGL的新类中，自定义函数addEdge的返回值应该是多少？ [英] What should be the return value of a custom function addEdge in a new class based on BGL?
问题描述
我尝试根据 https://stackoverflow.com/a/950173/7558038 实施图表类。添加边时，我返回添加边的边描述符，但如果边已经存在，则不应添加边。那我该怎么回事？不幸的是， null_edge（）不存在（与 null_vertex（）不同）。它可能是 std :: pair< e_it_t，bool> ，带有适当的边缘迭代器类型 e_it_t ，但怎么能我得到一个新边缘的迭代器？
I try to implement a graph class based on https://stackoverflow.com/a/950173/7558038. When adding an edge I return the edge descriptor of the added edge, but if the edge already exists, it shouldn't be added. What shall I return then? Unfortunately, null_edge() does not exist (unlike null_vertex()). It could be an std::pair<e_it_t,bool> with an appropriate edge iterator type e_it_t, but how can I get an iterator to the new edge?
推荐答案
不要使用差不多10年的那个类。它已经过时了。
Don't use that class that is almost 10 years old. It is obsolete.
捆绑属性已经到了BGL，只要我知道，这可能是至少从2010年开始。没有什么比直接提升更容易了。
Bundled properties have come to BGL as long as I know, which is... probably since at least 2010. Nothing there is fundamentally easier than straight boost.
另一个奇怪的特性是，不知何故只能在该图中插入互补边。这可能是你想要的，但它不保证拥有完整的类，IMO。
事实上，拥有自定义类型会删除ADL，除非你去添加彼此的操作（比如，你知道， out_edges 或 in_edges ，这可能会让事情变得更加乏味是你想要的双向图形;也许你真的希望有可迭代的范围而不是对< iterator，iterator> 这需要你写老式的for循环）。
In fact, having the custom type removes ADL, which makes things more tedious unless you go and add each other operation (like, you know, out_edges or in_edges, which presumably is what you wanted a bidirectional graph for in the first place; maybe you actually wish to have iterable ranges instead of pair<iterator, iterator> which requires you to write old-fashioned for loops).
现在我已经热身了，让我们演示：
Now that I've warmed up a bit, lets demonstrate:
链接的包装器提供如下用法：
The linked wrapper affords usage like this:
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年。这不是最糟糕的问题。据推测，你需要你的图表。假设您想要最小切割或最短路径。这意味着您要调用需要边权重的算法。这看起来像这样：
Note I didn't exactly bother to solve the problem of getting the edge-weight (we don't readily get edge descriptors from the interface at all). The for loops throw us back in time at least 6 years. And that's not nearly the worst problem. Presumably, you need your graph for something. Let's assume you want minimum cut, or a shortest path. This means you want to invoke an algorithm that requires the edge weight. This would look like so:
// 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));
这不是我对可用性的看法。只是为了显示所有编译和运行：
This is not my idea of usability. Just to show it all compiles and runs:
让我们用现代BGL样式替换整个Graph类模板：
Let's replace the whole Graph class template in modern BGL style:
template <typename VertexProperties, typename EdgeProperties>
using Graph = adjacency_list<setS, listS, bidirectionalS, VertexProperties, EdgeProperties>;
真的。这是一个可靠的替代品，我会马上展示它。
Really. That is a solid replacement, I'll demonstrate it right away.
事实上，让我们不做
使用命名空间提升;因为它使用我们可能觉得非常有用的所有名称来污染我们的命名空间（比如，你知道source或num_vertices）并邀请含糊不清的符号：
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：
The Same Use-Cases - creation and dijkstra
They are still as simple, or in fact simpler. The full code goes down from 249 lines of code to just 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));
}
我会说
- 这是优越的。
- 尽管没有依赖
使用命名空间提升（ADL是此处的关键），但它仍然优雅 - 我们实际打印了边缘重量！
- that is superior.
- it's just as elegant despite not relying on
using namespace boost(ADL is the key here) - and we actually printed the edge weight!
如果切换到具有隐式顶点索引的顶点容器选择器（如 vecS ）：
If you switch to a vertex container selector that has implicit vertex index (like 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)
等待 - 不要忘记问题！
我不会！我认为上面显示的问题是 X / Y问题。
如果您没有自定义类包装的障碍，则检测到重复边缘是给定的（参见如果BGL中的add_vertex检查顶点是否存在为背景：
If you hadn't had the handicap of custom class wrapping, detecting duplicate edges was a given (see if add_vertex in BGL checks for the existence of the vertex for background):
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
如果您愿意，您当然可以更明确地写东西：
If you prefer you can of course write things more expressively:
Graph::edge_descriptor e;
bool inserted;
boost::tie(e, inserted) = add_edge(request.from, request.to, { request.weight }, g);
或者，有一些c ++ 17天赋：
Or, with some c++17 flair:
auto [e, inserted] = add_edge(request.from, request.to, { request.weight }, g);
更多来自这里
此外，在您也可能需要对顶点进行唯一性检查，因此最终会得到图形创建代码，就像您在此答案中看到的那样：提升BGL BFS查找从源到目标的所有独特路径
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中的特定边缘
Other examples show how you can insert both a -> b and b -> a while maintaining a mapping between the forward and back edges: Accessing specific edges in boost::graph with integer index
即将推出完整的循环，我建议您熟悉更新，更优雅的Boost Graph功能。最后，将图表封装起来是完全正常的，最终你可能会得到一个更加精美的界面。
Coming full circle, I recommend getting acquainted with the newer, more elegant Boost Graph features. In the end, it's perfectly normal to encapsulate your graph, and you might end up with an even more polished interface.
这篇关于在基于BGL的新类中，自定义函数addEdge的返回值应该是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
