基于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，但是我怎样才能得到一个迭代器到新的边?

解决方案

不要使用差不多 10 年的课程.它已经过时了.

捆绑属性据我所知，BGL 是...至少从 2010 年开始.从根本上说，没有什么比直接提升更容易的了.

另一个奇怪的特性是，该图中只能以某种方式插入互补边.这可能是您想要的，但并不保证拥有完整的课程，IMO.

事实上，拥有自定义类型会删除 ADL，这会使事情变得更加乏味，除非您去添加彼此的操作(例如，out_edges 或 in_edges，这大概是您首先想要的双向图；也许您实际上希望拥有可迭代范围而不是 pair 这需要您编写老式的 for 循环).

现在我已经热身了，让我们演示一下:

使用过时的包装类

链接的包装器提供如下用法:

struct VertexProperties { int i;};struct EdgeProperties { 双重；};int main() {使用 MyGraph = Graph；MyGraph g;VertexProperties 副总裁；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) {自动&vp = g.properties(*vr.first);std::cout <<顶点"<<vp.i<<"\n";for (auto er = g.getAdjacentVertices(*vr.first); er.first!=er.second; ++er.first) {汽车 s ​​= *vr.first;自动 t = *er.first;//erm 现在如何获取边缘属性?std::cout <<边缘"<<g.properties(s).i<<" -> " <<g.properties(t).i<<"(重量?！?)\n";}}}

打印:

顶点 23边缘 23 ->67(重量?！?)顶点 67边缘 67 ->23(重量?！?)

注意我并没有完全费心去解决获取边权重的问题(我们根本不容易从界面中获取边描述符).for 循环让我们回到过去至少 6 年.这还不是最严重的问题.据推测，你需要你的图表来做某事.假设您想要最小切割或最短路径.这意味着您要调用需要边缘权重的算法.这看起来像这样:

//让我们找到一条最短路径://构建顶点索引图boost::property_map<MyGraph::GraphContainer, vertex_properties_t>::const_type vpmap =boost::get(vertex_properties, g.getGraph());//哎呀，我们需要它的 id.没问题，只需要火箭科学:结构获取 ID {int operator()(VertexProperties const& vp) const {返回 vp.i;}};GetId get_id;boost::transform_value_property_mapid_map= boost::make_transform_value_property_map(get_id, vpmap);//构建权重图boost::property_map<MyGraph::GraphContainer, edge_properties_t>::const_type epmap =boost::get(edge_properties, g.getGraph());//哎呀，我们需要它的权重.没问题，只需要火箭科学:结构体获取重量{double operator()(EdgeProperties const& ep) const {返回 ep.weight;}};GetWeight get_weight;boost::transform_value_property_map<GetWeight,boost::property_map::const_type,双>权重映射= boost::make_transform_value_property_map(get_weight, epmap);//现在我们简单地"使用 Dijkstra:MyGraph::vertex_range_t vertices = g.getVertices();//size_t n_vertices = g.getVertexCount();MyGraph::Vertex source = *vertices.first;std::map前辈；std::map距离;boost::dijkstra_shortest_paths(g.getGraph(), source,boost::predecessor_map(boost::make_assoc_property_map(predecessors)).distance_map(boost::make_assoc_property_map(距离)).weight_map(weight_map).vertex_index_map(id_map));

这不是我对可用性的看法.只是为了显示所有编译和运行:

生活在 Coliru

用两行 C++11 替换 Wrapper

让我们用现代 BGL 风格替换整个 Graph 类模板:

template 使用 Graph = adjacency_list;

真的.这是一个可靠的替代品，我会立即演示.

<块引用>

事实上，让我们不要使用命名空间提升；，因为它会用我们可能觉得非常有用的各种名称污染我们的命名空间(比如，你知道source 或 num_vertices) 并邀请不明确的符号:

template 使用 Graph = boost::adjacency_list;

相同的用例 - 创建和 dijkstra

它们仍然如此简单，或者实际上更简单.完整代码从 249 行代码减少到仅 57 行:

生活在 Coliru

#include 命名空间 MyLib {template 使用 Graph = boost::adjacency_list;}#include #include struct VertexProperties { int i;};struct EdgeProperties { 双重；};int main() {使用 boost::make_iterator_range;使用 MyGraph = MyLib::Graph;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 <<顶点"<<g[v].i＜＜"\n";}for (auto e : make_iterator_range(boost::edges(g))) {汽车 s ​​= 源(e，g)；自动 t = 目标(e，g)；std::cout <<边缘"<<g[s].i＜＜" -> " <<g[t].i＜＜" (weight = " << g[e].weight << ")\n";}//让我们找到一条最短路径:auto id_map = get(&VertexProperties::i, g);auto weight_map = get(&EdgeProperties::weight, g);auto source = *vertices(g).first;使用 Vertex = MyGraph::vertex_descriptor;std::map<顶点，顶点>前辈；std::map距离;std::map颜色;boost::dijkstra_shortest_paths(g, 来源,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(距离)).weight_map(weight_map).vertex_index_map(id_map));}

我想说

• 那太棒了.
• 尽管不依赖于使用命名空间提升，但它同样优雅(ADL 是这里的关键)
• 我们实际上打印了边缘重量！

它可以更干净

如果您切换到具有隐式顶点索引的顶点容器选择器(如 vecS):

生活在 Coliru

#include 命名空间 MyLib {template 使用 Graph = boost::adjacency_list;}#include #include struct VertexProperties { int i;};struct EdgeProperties { 双重；};int main() {使用 boost::make_iterator_range;使用 MyGraph = MyLib::Graph;我的图 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 <<顶点"<<g[v].i＜＜"\n";}for (auto e : make_iterator_range(boost::edges(g))) {汽车 s ​​= 源(e，g)；自动 t = 目标(e，g)；std::cout <<边缘"<<g[s].i＜＜" -> " <<g[t].i＜＜" (weight = " << g[e].weight << ")\n";}//让我们找到一条最短路径:std::vector前辈(num_vertices(g))；std::vector距离(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)));}

输出:

顶点 23顶点 67边缘 23 ->67(重量=1)边缘 67 ->23 (重量 = 0)

等待 - 不要忘记这个问题！

我不会！我认为以上表明问题是一个 X/Y 问题.>

如果你没有自定义类包装的障碍，检测重复边是给定的(参见 如果 BGL 中的 add_vertex 检查顶点的存在 作为背景):

struct { size_t from, to;双倍重量；} edge_data[] = {{0, 1, 1.0},{1, 0, 0.0},{0, 1, 99.999}//哎呀，重复};for(自动请求:edge_data){自动添加 = add_edge(request.from, request.to, { request.weight }, g);如果 (!addition.second) {自动&重量 = g[addition.first].weight;std::cout <<边缘已经存在，改变权重从"<<重量＜＜到" <<request.weight<<"\n";重量 = 请求.重量；}}

这将打印 Live On Coliru:

Edge 已经存在，将权重从 1 更改为 99.999

如果你愿意，你当然可以写得更有表现力:

Graph::edge_descriptor e;插入布尔值；boost::tie(e, insert) = add_edge(request.from, request.to, { request.weight }, g);

或者，有一些 C++17 天赋:

auto [e, insert] = add_edge(request.from, request.to, { request.weight }, g);

更多来自这里

此外，您很可能也需要对顶点进行唯一性检查，因此您最终会得到图形创建代码，就像您在此答案中看到的那样:Boost BGL BFS 查找从源到目标的所有唯一路径

Graph read_graph() {std::istringstream iss(R"(0 1 0.0010 2 0.10 3 0.0011 5 0.0012 3 0.0013 4 0.11 482 0.1482 635 0.0014 705 0.1705 5 0.11 1491 0.011 1727 0.011 1765 0.01)");图g；std::mapidx;//临时查找现有顶点自动顶点 = [&](int id) 可变 {自动它 = idx.find(id);如果(它！= idx.end())返回它->第二个；返回 idx.emplace(id, add_vertex(id, g)).first->second;};for (std::string line; getline(iss, line);) {std::istringstream ls(line);整数 s,t;双 w;如果 (ls >> s >> t >> w) {add_edge(vertex(s), vertex(t), w, g);} 别的 {std::cerr <<跳过无效行'"<<线<<"'\n";}}返回 g;}

其他示例展示了如何插入 a ->b 和 b ->a 同时保持前后边缘之间的映射:使用整数索引访问 boost::graph 中的特定边

总结

归根结底，我建议您熟悉更新、更优雅的 Boost Graph 功能.最后，封装您的图形是完全正常的，您可能最终会得到一个更加精美的界面.

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?

解决方案

Don't use that class that is almost 10 years old. It is obsolete.

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.

Another weird property is that somehow only complementary edges can be inserted in that graph. This might be what you want, but it doesn't warrant having the complete class, IMO.

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:

Using The Obsolete Wrapper class

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";
        }
    }
}

Which prints:

Vertex 23
Edge 23 -> 67 (weight?!?)
Vertex 67
Edge 67 -> 23 (weight?!?)

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:

Live On Coliru

Replace The Wrapper In 2 Lines Of C++11

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.

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>;

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:

Live On Coliru

#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));
}

I'd say

• 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!

And It Can Be Cleaner Still

If you switch to a vertex container selector that has implicit vertex index (like vecS):

Live On Coliru

#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)));
}

Output:

Vertex 23
Vertex 67
Edge 23 -> 67 (weight = 1)
Edge 67 -> 23 (weight = 0)

WAIT - Don't Forget About The Question!

I won't! I think the above shows the problem was an X/Y problem.

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;
    }
}

This will print 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);

Or, with some c++17 flair:

auto [e, inserted] = add_edge(request.from, request.to, { request.weight }, g);

More From Here

Also, in all likelihood you need to do uniqueness checks on the vertices too, so you end up with graph creation code like you can see in this answer: Boost BGL BFS Find all unique paths from Source to Target

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;
}

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

Summary

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屋！