c++ - BGL:从Stoer-Wagner最小切割中获取边缘指数吗？

我正在使用Stoer-Wagner algorithm in boost::graph找到图形的最小割。结果是正确的，但我需要获取算法所切割的边缘。我知道obtain parity map是可能的，但是我必须分析 map 以获得边缘。有没有办法直接获得这些？

在下面的示例中，最小切割权重为1，但我也想获得切割的边缘(在这种情况下为0-2)。

(请参见http://coliru.stacked-crooked.com/a/fc4166dafb089103上的直播)

#include <iostream>

#include<boost/graph/adjacency_list.hpp>
#include<boost/graph/connected_components.hpp>
#include <boost/graph/stoer_wagner_min_cut.hpp>

int main(void){
    typedef boost::property<boost::edge_weight_t, int> EdgeWeightProp;
    typedef boost::adjacency_list<
        /*vertex storage*/boost::vecS,
        /*edge storage*/boost::vecS,
        /*graph type*/boost::undirectedS,
        /*vertex properties*/boost::no_property,
        /*edge properties*/ EdgeWeightProp
        > Graph;
    /*
      something simple as example:

      2   3
      | / |
      0 - 1

    */
    Graph conn(4);
    boost::add_edge(0,1,EdgeWeightProp(1),conn);
    boost::add_edge(0,2,EdgeWeightProp(1),conn);
    boost::add_edge(0,3,EdgeWeightProp(1),conn);
    boost::add_edge(1,3,EdgeWeightProp(1),conn);
    int w=boost::stoer_wagner_min_cut(conn,get(boost::edge_weight,conn));
    std::cout<<"Mincut weight is "<<w<<std::endl;
}

最佳答案

但是，没有这种方法，“分析”奇偶校验图并不难:

for (auto ed : boost::make_iterator_range(edges(conn))) {
    auto s = source(ed, conn), t = target(ed, conn);
    if (get(parity, s)!=get(parity, t))
        std::cout << "{" << s << "," << t << "; weight " << get(weights, ed) << "}\n";
}

如果您担心“增加的成本”，我认为没有必要，因为该算法实际上并未确定要切割的边缘，因此它始终是推导任务¹。

这是一个涉及更多的示例:

Live On Coliru

/*                                    2
 *  +-----------------+           +---------------------+
 *  |                 |           |                     |
 *  |   +----+  2   +----+  3   +---+  4   +---+  2   +---+  3   +---+
 *  |   | 0  | ---- | 1  | ---- | 2 | ---- | 3 | ---- | 6 | ---- | 7 |
 *  |   +----+      +----+      +---+      +---+      +---+      +---+
 *  | 2   |           |                      |          |   2      |
 *  |     | 3         | 2                    +----------+----------+
 *  |     |           |                                 |
 *  |   +----+  3   +----+       1                      |
 *  +-- | 4  | ---- | 5  | -----------------------------+
 *      +----+      +----+
 */
Graph conn(8);
add_edge(0, 1, 2, conn);
add_edge(0, 4, 3, conn);
add_edge(1, 2, 3, conn);
add_edge(1, 5, 2, conn);
add_edge(1, 4, 2, conn);
add_edge(2, 6, 2, conn);
add_edge(2, 3, 4, conn);
add_edge(3, 7, 2, conn);
add_edge(3, 6, 2, conn);
add_edge(4, 5, 3, conn);
add_edge(5, 6, 1, conn);
add_edge(6, 7, 3, conn);

auto parity = boost::make_one_bit_color_map(num_vertices(conn), get(boost::vertex_index, conn));
auto weights = get(boost::edge_weight, conn);
int w = boost::stoer_wagner_min_cut(conn, weights, boost::parity_map(parity));

for (auto ed : boost::make_iterator_range(edges(conn))) {
    auto s = source(ed, conn), t = target(ed, conn);
    if (get(parity, s)!=get(parity, t))
        std::cout << "{" << s << "," << t << "; weight " << get(weights, ed) << "}\n";
}

哪些打印:

{1,2; weight 3}
{5,6; weight 1}
Mincut weight is 4

该样本取自文档:

¹尽管需要引用:)

关于c++ - BGL:从Stoer-Wagner最小切割中获取边缘指数吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/46753785/