c++ - 基于 BGL 的新类中自定义函数 addEdge 的返回值应该是什么？

Question

我尝试基于 https://stackoverflow.com/a/950173/7558038 实现一个图形类.添加边时，我返回添加边的边描述符，但如果边已经存在，则不应添加。那我还什么？不幸的是，null_edge()不存在(不像 null_vertex() )。它可能是 std::pair<e_it_t,bool>使用适当的边缘迭代器类型 e_it_t ，但是我怎样才能得到一个迭代器到新的边缘呢？

Answer 1

不要使用将近 10 年的类(class)。它已过时。

Bundled properties据我所知，我已经加入 BGL，这可能是……至少从 2010 年开始。从根本上说，没有什么比直接 boost 更容易了。

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

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

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

使用过时的包装器类

链接包装器提供这样的用法:

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?!?)

请注意，我并没有费心去解决获取边权重的问题(我们根本无法轻易地从接口(interface)中获取边描述符)。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));

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

Live On Coliru

替换2行C++11中的包装

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

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 行:

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

我说

• 那是优越的。
• 尽管不依赖 using namespace boost，但它同样优雅(ADL 是这里的关键)
• 我们实际上打印了边缘重量!

它还可以更干净

如果您切换到具有隐式顶点索引的顶点容器选择器(如 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)));
}

输出:

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

等等 - 不要忘记问题!

我不会!我认为上面显示的问题是 an X/Y problem .

如果您没有自定义类包装的障碍，则检测重复边是给定的(请参阅 if add_vertex in BGL checks for the existence of the vertex 了解背景信息):

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

更多内容

此外，您很可能还需要对顶点进行唯一性检查，因此您最终会得到图形创建代码，就像您在这个答案中看到的那样: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;
}

其他示例展示了如何同时插入 a -> b和 b -> a同时维护前后边缘之间的映射:Accessing specific edges in boost::graph with integer index

总结

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