访问 boost::graph 中的特定顶点

Question

我主要使用自己的网络流算法。然而，我最近刚刚开始使用 boost，但正在努力定义图表。更具体地说，我自己的代码中的顶点编号为 0 到 n-1。边的编号为 0 到 m-1。我正在尝试构建一个非常简单的具有 4 个边的网络。

所有四个边的容量均为 4 个单位。我正在寻找 boost 来找到从 s = 0 到 t = 3 的最大流量。（答案是 8。）

为了让它运行，我有以下代码，但是尽管它编译和构建没有错误，但代码没有达到我的预期。请参阅代码中的注释来了解我的具体问题。有两个问题（Q1）和（Q2）。

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
#include <boost/graph/push_relabel_max_flow.hpp>
#include <boost/graph/edmonds_karp_max_flow.hpp>


using namespace boost;


typedef adjacency_list_traits < vecS, vecS, directedS > Traits;

typedef adjacency_list < vecS, vecS, directedS,

    property < vertex_name_t, std::string,
    property < vertex_index_t, int,
    property < vertex_color_t, boost::default_color_type,
    property < vertex_distance_t, double,
    property < vertex_predecessor_t, Traits::edge_descriptor > > > > >,

    property < edge_index_t, int, 
    property < edge_capacity_t, double,
    property < edge_weight_t, double, 
    property < edge_residual_capacity_t, double,
    property < edge_reverse_t, Traits::edge_descriptor > > > > > > Graph;

int main()
{
    Graph g;
    property_map<Graph, vertex_index_t>::type v = get(vertex_index, g);
    property_map<Graph, edge_index_t>::type e = get(edge_index, g);
    property_map<Graph, edge_capacity_t>::type cap = get(edge_capacity, g);
    property_map<Graph, edge_weight_t>::type cost = get(edge_weight, g);
    property_map<Graph, edge_residual_capacity_t>::type rescap = get(edge_residual_capacity, g);
    property_map < Graph, edge_reverse_t >::type rev = get(edge_reverse, g);

    int nonodes = 4;

    for (int i = 0; i < nonodes; i++) {
        Traits::vertex_descriptor vd;
        vd = add_vertex(g);
        assert(v[vd] == i);//(Q1)Here, v[vd] = i; produces an error. Is there any other way to assign integer indices to vertices?
    }

    Graph::vertex_iterator vertexIt, vertexEnd;
    tie(vertexIt, vertexEnd) = vertices(g);

    //Create edges
    Traits::edge_descriptor edf, edb;//Max flow algorithms seem to want both forward and backward edges. edf is for forward, edb is for backward

//Q2. All of the add_edge() functions below do not seem to add any edges to the graph, leading to a run time error when boykov_kolmogorov_max_flow() is finally called.
    edf = (add_edge(*(vertexIt+0), *(vertexIt + 1), g)).first;
    edb = (add_edge(*(vertexIt + 1), *(vertexIt + 0), g)).first;
    e[edf] = 0;
    e[edb] = 1;
    cap[edf] = 4;
    cap[edb] = 4;

    edf = (add_edge(*(vertexIt + 0), *(vertexIt + 2), g)).first;
    edb = (add_edge(*(vertexIt + 2), *(vertexIt + 0), g)).first;
    e[edf] = 2;
    e[edb] = 3;
    cap[edf] = 4;
    cap[edb] = 4;

    edf = (add_edge(*(vertexIt + 1), *(vertexIt + 3), g)).first;
    edb = (add_edge(*(vertexIt + 3), *(vertexIt + 1), g)).first;
    e[edf] = 4;
    e[edb] = 5;
    cap[edf] = 4;
    cap[edb] = 4;

    edf = (add_edge(*(vertexIt + 2), *(vertexIt + 3), g)).first;
    edb = (add_edge(*(vertexIt + 3), *(vertexIt + 2), g)).first;
    e[edf] = 6;
    e[edb] = 7;
    cap[edf] = 4;
    cap[edb] = 4;

    double flow = boykov_kolmogorov_max_flow(g, *(vertexIt + 0), *(vertexIt + 3));
    return 0;
}

关于 Q1）我查找了On C++ Boost Graph Creation 和 vertex_index 属性提供的解决方案。。但是，我不清楚为什么v[vd] = i;会导致编译时错误，但e[edf] = 0;后来不会导致编译时错误。

关于 Q2）我真正寻找的是一种访问顶点以传递给函数的方法add_edge()。更一般地说，有没有办法通过某种机制访问第二个边缘（从 0 开始计数），或者vertex[2]通过某种机制访问第三个边缘（从 0 开始计数）edge[3]，等等？

Answer 1

i); //(Q1)Here, v[vd] = i; produces an error. Is there any other way to assign integer indices to vertices?

当您使用时，vecS顶点索引是隐式的，并且是顶点向量的积分索引。因此，如果不物理地打乱顶点，就无法分配它。

但是，您可以通过选择非随机访问顶点容器（例如 ）来自由地不使用内置隐式顶点索引listS。

但是：如果你这样做，你（显然）可以不再使用ID作为顶点描述符，使得所有代码都像

edf = (add_edge(*(vertexIt + 0), *(vertexIt + 1), g)).first;
edb = (add_edge(*(vertexIt + 1), *(vertexIt + 0), g)).first;

非常笨拙，更像

auto find_vertex_by_id = [&g](size_t id) {
    for(auto vd : boost::make_iterator_range(boost::vertices(g)))
        if (id == g[vd])
            return vd;
    throw std::range_error("vertex id " + std::to_string(id));
};

edf = (add_edge(find_vertex_by_id(g[*vertexIt].id + 0), find_vertex_by_id(g[*vertexIt].id + 1), g)).first;
edb = (add_edge(find_vertex_by_id(g[*vertexIt].id + 1), find_vertex_by_id(g[*vertexIt].id + 0), u)).first;

请在 Coliru 上观看直播，我希望您同意这很令人恼火。

请注意，它也会崩溃。别担心，这是一个小问题（主要是因为反向边缘图没有正确构建）。快速解决这个问题，会让你难以捉摸Flow: 8！Sneak Preview

我建议走另一条路！拥抱隐式顶点索引，它与描述符类型一致。然后，不要为迭代器的迂回方式而烦恼，只需绝对地址：

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
#include <boost/graph/edmonds_karp_max_flow.hpp>
#include <boost/graph/push_relabel_max_flow.hpp>
#include <iostream>

using namespace boost;

typedef adjacency_list_traits<vecS, vecS, directedS> Traits;

typedef adjacency_list<
    vecS, vecS, directedS,

    property<
        vertex_name_t, std::string,
        property<vertex_index_t, int,
        property<vertex_color_t, boost::default_color_type,
        property<vertex_distance_t, double,
        property<vertex_predecessor_t, Traits::edge_descriptor> 
    > > > >,

    property<
        edge_index_t, int,
        property<edge_capacity_t, double,
        property<edge_weight_t, double,
        property<edge_residual_capacity_t, double,
        property<edge_reverse_t, Traits::edge_descriptor>
    > > > > >
    Graph;

int main() {
    Graph g;
    property_map<Graph, edge_index_t>::type             e      = get(edge_index,             g);
    property_map<Graph, edge_capacity_t>::type          cap    = get(edge_capacity,          g);
    //property_map<Graph, edge_weight_t>::type            cost   = get(edge_weight,            g);
    //property_map<Graph, edge_residual_capacity_t>::type rescap = get(edge_residual_capacity, g);
    property_map<Graph, edge_reverse_t>::type           rev    = get(edge_reverse,           g);

    int nonodes = 4;

    for (int i = 0; i < nonodes; i++) {
        Traits::vertex_descriptor vd;
        vd = add_vertex(g);
        assert(vd == i);
    }

    // Create edges
    Traits::edge_descriptor edf, edb; // Max flow algorithms seem to want both forward and backward edges. edf is for
                                      // forward, edb is for backward

    // Q2. All of the add_edge() functions below do not seem to add any edges to the graph, leading to a run time error
    // when boykov_kolmogorov_max_flow() is finally called.
    edf = (add_edge(0, 1, g)).first;
    edb = (add_edge(1, 0, g)).first;

    e[edf] = 0;
    e[edb] = 1;
    cap[edf] = 4;
    cap[edb] = 4;
    rev[edf] = edb;
    rev[edb] = edf;

    edf = (add_edge(0, 2, g)).first;
    edb = (add_edge(2, 0, g)).first;
    e[edf] = 2;
    e[edb] = 3;
    cap[edf] = 4;
    cap[edb] = 4;
    rev[edf] = edb;
    rev[edb] = edf;

    edf = (add_edge(1, 3, g)).first;
    edb = (add_edge(3, 1, g)).first;
    e[edf] = 4;
    e[edb] = 5;
    cap[edf] = 4;
    cap[edb] = 4;
    rev[edf] = edb;
    rev[edb] = edf;

    edf = (add_edge(2, 3, g)).first;
    edb = (add_edge(3, 2, g)).first;
    e[edf] = 6;
    e[edb] = 7;
    cap[edf] = 4;
    cap[edb] = 4;
    rev[edf] = edb;
    rev[edb] = edf;

    double flow = boykov_kolmogorov_max_flow(g, 0, 3);
    std::cout << "Flow: " << flow << "\n";
}

印刷

Flow: 8

这样不是好很多吗？现在，让我们继续消除那些仍然丑陋/烦人的东西

奖励 1：只需创建 4 个节点即可

现在循环add_vertex看起来相当无能：

for (int i = 0; i < nonodes; i++) {
    Traits::vertex_descriptor vd;
    vd = add_vertex(g);
    assert(vd == i);
}

事实上，我们就这样写：

Graph g(nonodes);

奖励 2：捆绑这些属性

以必须将属性映射传递给算法为代价，您可以通过使用Bundled Properties使构建图变得更容易：

Live On Coliru

等等——什么？这不是一个进步，不是吗？好吧，等到你看到这个：

struct { int from,to; } edges[] = { { 0, 1 }, { 0, 2 }, { 1, 3 }, { 2, 3 }, };
int edge_id = 0;
for (auto& edge : edges) {
    auto edf = add_edge(edge.from, edge.to, EdgeProperty{edge_id++, 4}, g).first,
         edb = add_edge(edge.to, edge.from, EdgeProperty{edge_id++, 4}, g).first;

    rev[edf] = edb;
    rev[edb] = edf;
}

Live On Coliru

耶！

奖励 3：将临时顶点属性分离出来

这些流算法特定的属性并不真正属于图中，那么为什么要包含它们呢？让我们做一些花哨的步法并使用外部地图。这已经开始变得先进，但确实让我们明白了属性映射的要点：它们就像C++ 的镜头。

不加评论地提出：

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
#include <functional>
#include <iostream>

using namespace boost;

struct VertexProperty { std::string name; };

struct EdgeProperty {
    int id;
    double capacity, residual_capacity;

    EdgeProperty(int id, double cap, double res = 0)
        : id(id), capacity(cap), residual_capacity(res)
    { }
};

typedef adjacency_list<vecS, vecS, directedS, VertexProperty, EdgeProperty> Graph;

int main() {
    int nonodes = 4;
    Graph g(nonodes);

    // reverse edge map
    auto e      = get(&EdgeProperty::id, g);
    auto rev    = make_vector_property_map<Graph::edge_descriptor>(e);

    // Create edges
    struct { int from,to; } edges[] = { { 0, 1 }, { 0, 2 }, { 1, 3 }, { 2, 3 }, };
    int edge_id = 0;

    for (auto& pair : edges) {
        auto a = add_edge(pair.from, pair.to, EdgeProperty { edge_id++, 4 }, g).first;
        auto b = add_edge(pair.to, pair.from, EdgeProperty { edge_id++, 4 }, g).first;
        rev[a] = b;
        rev[b] = a;
    }

    // property maps
    struct VertexEx {
        default_color_type color;
        double distance;
        Graph::edge_descriptor pred;
    };

    auto idx    = get(vertex_index, g);
    auto vex    = make_vector_property_map<VertexEx>(idx);
    auto pred   = make_transform_value_property_map(std::mem_fn(&VertexEx::pred),     vex);
    auto color  = make_transform_value_property_map(std::mem_fn(&VertexEx::color),    vex);
    auto dist   = make_transform_value_property_map(std::mem_fn(&VertexEx::distance), vex);

    auto cap    = get(&EdgeProperty::capacity, g);
    auto rescap = get(&EdgeProperty::residual_capacity, g);

    // algorithm
    double flow = boykov_kolmogorov_max_flow(g, cap, rescap, rev, pred, color, dist, idx, 0, 3);
    std::cout << "Flow: " << flow << "\n";
}

奖励 4：也适用于边缘属性图

Live On Coliru，提出的评论就更少了。