求最小S/T割集上弧的Boost图最大流算法

Question

我有一个应用程序，对于给定的固定数目的顶点，需要求解大量不同的最大流算法，从给定的固定源(S)到给定的固定接收器(T)。每个最大流量问题的不同之处在于，定向弧本身随容量的变化而变化.举个例子，见下文。

​

​

顶点的数目是固定的，但是实际的弧和它们的容量因问题的不同而不同。

下面的代码迭代地解决了图1和图2的最大流问题，在上面的图中使用了boost (对文本墙表示歉意)，我试图使它尽可能地最小化。下面的代码在我的linux盒上完全在g++上编译，但我无法在在线编译器(如wandbox等)上正确编译)：

#include <boost/config.hpp>
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/boykov_kolmogorov_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;

Graph g;
property_map<Graph, edge_index_t>::type e;
property_map<Graph, edge_capacity_t>::type cap;
property_map<Graph, edge_weight_t>::type cost;
property_map<Graph, edge_residual_capacity_t>::type rescap;
property_map<Graph, edge_reverse_t>::type rev;
property_map<Graph, vertex_color_t>::type colors;

void initialize(int nnodes) {
    e = get(edge_index, g);
    cap = get(edge_capacity, g);
    cost = get(edge_weight, g);
    rescap = get(edge_residual_capacity, g);
    rev = get(edge_reverse, g);
    colors = get(vertex_color, g);
    for(int i = 0; i < nnodes; i++)
        add_vertex(g);
}

void clearedges() {
    Graph::vertex_iterator v, vend;
    for (boost::tie(v, vend) = vertices(g); v != vend; ++v) 
        boost::clear_out_edges(*v, g);
}

void createedges(std::vector<std::pair<int, int>>& arcs, std::vector<double>& capacity) {
    Traits::edge_descriptor edf, edr;//forward and reverse
    for (int eindex = 0, sz = static_cast<int>(arcs.size()); eindex < sz; eindex++) {
        int fr, to;
        fr = arcs[eindex].first;
        to = arcs[eindex].second;
        edf = add_edge(fr, to, g).first;
        edr = add_edge(to, fr, g).first;
        e[edf] = 2 * eindex;
        e[edr] = e[edf] + 1;
        cap[edf] = capacity[eindex];
        cap[edr] = capacity[eindex];
        rev[edf] = edr;
        rev[edr] = edf;
    }
}

double solve_max_flow(int s, int t) {
    double retval = boykov_kolmogorov_max_flow(g, s, t);
    return retval;
}

bool is_part_of_source(int i) {
    if (colors[i] == boost::black_color)
        return true;
    return false;
}

int main() {
    initialize(6);
    std::vector<std::pair<int, int>> arcs1 = { std::make_pair<int,int>(0,1),
    std::make_pair<int,int>(0,2),
    std::make_pair<int,int>(1,2),
    std::make_pair<int,int>(1,3),
    std::make_pair<int,int>(1,4),
    std::make_pair<int,int>(2,4),
    std::make_pair<int,int>(3,4),
    std::make_pair<int,int>(3,5),
    std::make_pair<int,int>(4,5)
    };
    std::vector<double> capacities1 = { 10, 10, 10, 10, 1, 4, 3, 2, 10 };
    clearedges();
    createedges(arcs1, capacities1);
    double maxflow = solve_max_flow(0, 5);
    printf("max flow is %f\n", maxflow);
    for (int i = 0; i < 6; i++)
        if (is_part_of_source(i))
            printf("Node %d belongs to subset source is in\n", i);
    Graph::edge_iterator e_, eend_;
    int Eindex = 0;
    for (boost::tie(e_, eend_) = edges(g); e_ != eend_; ++e_) {
        int fr = source(*e_, g);
        int to = target(*e_, g);
        printf("(%d) Edge %d: (%d -> %d), capacity %f\n", Eindex, e[*e_], fr, to, cap[*e_]);
        Eindex++;
        if (is_part_of_source(fr) && is_part_of_source(to) == false)
            printf("----is part of ST Cut-----\n");
        else
            printf("x\n");
    }
    std::vector<std::pair<int, int>> arcs2 = { std::make_pair<int,int>(0,1),
    std::make_pair<int,int>(0,2),
    std::make_pair<int,int>(1,3),
    std::make_pair<int,int>(2,4),
    std::make_pair<int,int>(3,5),
    std::make_pair<int,int>(4,5)
    };
    std::vector<double> capacities2 = { 10, 10, 10, 4, 2, 0 };
    clearedges();
    createedges(arcs2, capacities2);
    maxflow = solve_max_flow(0, 5);
    printf("max flow is %f\n", maxflow);
    for (int i = 0; i < 6; i++)
        if (is_part_of_source(i))
            printf("Node %d belongs to subset source is in\n", i);
    Eindex = 0;
    for (boost::tie(e_, eend_) = edges(g); e_ != eend_; ++e_) {
        int fr = source(*e_, g);
        int to = target(*e_, g);
        printf("(%d) Edge %d: (%d -> %d), capacity %f\n", Eindex, e[*e_], fr, to, cap[*e_]);
        Eindex++;
        if (is_part_of_source(fr) && is_part_of_source(to) == false)
            printf("----is part of ST Cut-----\n");
        else
            printf("x\n");
    }
    getchar();
}

我有以下问题。

(a)如果底层顶点保持固定，但只有弧和它们的容量随迭代而变化，那么是否比使用clear_out_edges清除弧，然后使用add_edge添加具有新容量的新弧更快？另外，clear_out_edges是否也正确地清除了属性映射项，这些项可能将边缘描述符作为键删除？

(b) Boost max-flow算法似乎需要显式增加反向弧.到目前为止，在函数createedges中，我通过前向边缘描述符(edf)和反向边缘描述符(edr)显式地实现了这一点。这是否有任何性能损失，特别是当需要解决的最大流量问题在1000秒内时？还有什么比这更有效的吗？

(c)通过代码的以下部分，我能够正确地枚举最小S/T的弧数：

    int Eindex = 0;
    for (boost::tie(e_, eend_) = edges(g); e_ != eend_; ++e_) {
        int fr = source(*e_, g);
        int to = target(*e_, g);
        printf("(%d) Edge %d: (%d -> %d), capacity %f\n", Eindex, e[*e_], fr, to, cap[*e_]);
        Eindex++;
        if (is_part_of_source(fr) && is_part_of_source(to) == false)
            printf("----is part of ST Cut-----\n");
        else
            printf("x\n");
    }

是否有任何比上述更有效的方法或枚举弧的科技/技术削减？

Answer 1

有很多问题。如果使用现代C++和编译器警告，您可以减少代码并发现打印顶点描述符中的错误(printf只是不安全；使用诊断！)

这是我复习后的看法。

显著变化：

• 捆绑属性而不是单独的内部属性
• 这意味着传递命名的参数(但请参阅https://stackoverflow.com/a/64744086/85371)
• 如果简单的构造函数足够，则不再存在全局变量，也不会出现更多的模糊初始化。
• 不再有重复的代码(没有什么会引起错误，就像让capacities1和capacities2躺在一起一样)
• 使用clear_vertex而不仅仅是clear_out_edges --这可能没有什么区别(?)但似乎更好地表达了意图
• 不再使用printf (我将使用libfmt，它也在c++23中)。 fmt：：print(“最大流{} \n节点{}在源子集\n”，最大流，顶点(_g)+筛选(Is_source))； 版画 最大流10个节点{0，1，2，3}在源子集中 一蹴而就
• 打印你认为你正在打印的东西。特别是，如果可以的话，请使用库支持打印边。

在编译器资源管理器上直播

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
#include <boost/range/adaptors.hpp>
#include <fmt/ostream.h>
#include <fmt/ranges.h>
using boost::adaptors::filtered;

using Traits = boost::adjacency_list_traits<boost::vecS, boost::vecS, boost::directedS>;
using V      = Traits::vertex_descriptor;
using E      = Traits::edge_descriptor;

using Capacity = double;
using Color    = boost::default_color_type;

struct VertexProps {
    // std::string name;
    Color    color;
    Capacity distance;
    E        predecessor;
};

struct EdgeProps {
    int      id;
    Capacity weight, residual;
    E        reverse;
};

using Graph = boost::adjacency_list<
    boost::vecS, boost::vecS, boost::directedS,
    VertexProps,
    // see https://stackoverflow.com/a/64744086/85371 :(
    boost::property<boost::edge_capacity_t, Capacity, EdgeProps>>;

struct MyGraph {
    MyGraph(size_t nnodes) : _g(nnodes) {}

    void runSimulation(auto const& arcs, auto const& capacities)
    {
        reconfigure(arcs, capacities);

        Capacity maxflow = solve_max_flow(0, 5);

        auto cap       = get(boost::edge_capacity, _g);
        auto is_source = [this](V v) { return _g[v].color == Color::black_color; };

        fmt::print("Max flow {}\nNodes {} are in source subset\n", maxflow,
                vertices(_g) | filtered(is_source));

        for (E e : boost::make_iterator_range(edges(_g))) {
            bool st_cut =
                is_source(source(e, _g)) and
                not is_source(target(e, _g));

            fmt::print("Edge {} (id #{:2}), capacity {:3} {}\n", e, _g[e].id,
                    cap[e], st_cut ? "(ST Cut)" : "");
        }
    }

private:
    Graph _g;

    void reconfigure(auto const& arcs, auto const& capacities)
    {
        assert(arcs.size() == capacities.size());

        for (auto v : boost::make_iterator_range(vertices(_g))) {
            // boost::clear_out_edges(v, g);
            boost::clear_vertex(v, _g);
        }

        auto cap  = get(boost::edge_capacity, _g);
        auto eidx = get(&EdgeProps::id, _g);
        auto rev  = get(&EdgeProps::reverse, _g);

        auto  eindex = 0;

        for (auto [fr, to] : arcs) {
            auto edf  = add_edge(fr, to, _g).first;
            auto edr  = add_edge(to, fr, _g).first;
            eidx[edf] = 2 * eindex;
            eidx[edr] = eidx[edf] + 1;
            cap[edf]  = cap[edr] = capacities[eindex];

            rev[edf] = edr;
            rev[edr] = edf;

            ++eindex;
        }
    }

    Capacity solve_max_flow(V src, V sink)
    {
        return boykov_kolmogorov_max_flow(
            _g, src, sink,
            // named arguments
            boost::reverse_edge_map(get(&EdgeProps::reverse, _g))
                .residual_capacity_map(get(&EdgeProps::residual, _g))
                .vertex_color_map(get(&VertexProps::color,       _g))
                .predecessor_map(get(&VertexProps::predecessor,  _g))
                .distance_map(get(&VertexProps::distance,        _g))
            // end named arguments
        );
    }
};

int main() {
    MyGraph g{6};

    using namespace std;
    for (auto&& [arcs, capacities] : { tuple
            // 1
            {vector{pair{0, 1}, {0, 2}, {1, 2}, {1, 3}, {1, 4},
                                    {2, 4}, {3, 4}, {3, 5}, {4, 5}},
            vector{10, 10, 10, 10, 1, 4, 3, 2, 10}},
            // 2
            {vector{pair{0, 1}, {0, 2}, {1, 3}, {2, 4}, {3, 5}, {4, 5}},
            vector{10, 10, 10, 4, 2, 0}},
        })
    {
        g.runSimulation(arcs, capacities);
    }
}

打印

Max flow 10
Nodes {0, 1, 2, 3} are in source subset
Edge (0,1) (id # 0), capacity  10 
Edge (0,2) (id # 2), capacity  10 
Edge (1,0) (id # 1), capacity  10 
Edge (1,2) (id # 4), capacity  10 
Edge (1,3) (id # 6), capacity  10 
Edge (1,4) (id # 8), capacity   1 (ST Cut)
Edge (2,0) (id # 3), capacity  10 
Edge (2,1) (id # 5), capacity  10 
Edge (2,4) (id #10), capacity   4 (ST Cut)
Edge (3,1) (id # 7), capacity  10 
Edge (3,4) (id #12), capacity   3 (ST Cut)
Edge (3,5) (id #14), capacity   2 (ST Cut)
Edge (4,1) (id # 9), capacity   1 
Edge (4,2) (id #11), capacity   4 
Edge (4,3) (id #13), capacity   3 
Edge (4,5) (id #16), capacity  10 
Edge (5,3) (id #15), capacity   2 
Edge (5,4) (id #17), capacity  10 
Max flow 2
Nodes {0, 1, 2, 3, 4} are in source subset
Edge (0,1) (id # 0), capacity  10 
Edge (0,2) (id # 2), capacity  10 
Edge (1,0) (id # 1), capacity  10 
Edge (1,3) (id # 4), capacity  10 
Edge (2,0) (id # 3), capacity  10 
Edge (2,4) (id # 6), capacity   4 
Edge (3,1) (id # 5), capacity  10 
Edge (3,5) (id # 8), capacity   2 (ST Cut)
Edge (4,2) (id # 7), capacity   4 
Edge (4,5) (id #10), capacity   0 (ST Cut)
Edge (5,3) (id # 9), capacity   2 
Edge (5,4) (id #11), capacity   0 

边注

如果您认为main太复杂了，这里有另一种方法可以只为两个调用编写它：

在编译器资源管理器上直播

g.runSimulation({{0, 1}, {0, 2}, {1, 2}, {1, 3}, {1, 4}, {2, 4}, {3, 4}, {3, 5}, {4, 5}},
                {10, 10, 10, 10, 1, 4, 3, 2, 10});

g.runSimulation({{0, 1}, {0, 2}, {1, 3}, {2, 4}, {3, 5}, {4, 5}},
                {10, 10, 10, 4, 2, 0});