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

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

最佳答案

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

据我所知，Bundled properties至少在2010年就加入了BGL。从根本上讲，没有什么比直接提升更为容易的了。

另一个怪异的特性是，在某种程度上只能在该图中插入互补边。这可能是您想要的，但不保证拥有完整的类(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>;

真。这是一个可靠的替代品，我将立即进行演示。



相同的用例-创建和创建

它们仍然一样简单，或者实际上更简单。完整的代码从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功能。最后，封装图形是完全正常的，最终可能会得到更优美的界面。