c++ - 访问 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;
}

关于问题 1)我查找了提供的解决方案 On C++ Boost Graph Creation and the vertex_index Property. .但是，我不清楚为什么 v[vd] = i; 会导致编译时错误，但 e[edf] = 0; 之后不会导致编译时间错误。

关于问题 2)我真正想要的是一种访问顶点以传递给 add_edge() 函数的方法。更一般地说，有没有一种方法可以通过诸如 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 时，顶点索引是隐式 并且是顶点 vector 的整数索引。因此，如果不对周围的顶点进行物理洗牌，就无法分配它。

但是，您可以在没有内置隐式顶点索引的情况下自由操作，方法是选择一个非随机访问的顶点容器，例如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;

查看 Live On Coliru ，我希望你同意这会加重病情。

Note it also crashes. Don't worry, that's a minor issue (mainly because the reverse edge map is not built up correctly). Fixing that, quickly, gives you the elusive 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:分离临时顶点属性

那些特定于流算法的属性并不真正属于图中，那么为什么要包含它们呢？让我们做一些花哨的步法并使用外部 map 。这开始变得更先进了，但真正让我们明白了属性映射的要点:它们就像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 ，评论更少。