BGL：从 Stoer-Wagner min-cut 获取边缘索引？

Question

我正在使用 Stoer-Wagner algorithm in boost::graph. The result is correct but I need to get the edges which were cut by the algorithm. I know there is the possibility to obtain parity 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;
}

Answer 1

没有这样的方法，但是，"analysing"奇偶映射并不难：

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";
}

如果您担心 "added cost" 我不认为是这样，因为该算法实际上并没有建立要切割的边，所以它始终是一个推导任务¹。

这是一个更复杂的例子：

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

示例取自文档：

¹ 虽然需要引用:)

BGL：从 Stoer-Wagner min-cut 获取边缘索引？

BGL: geting edge indices from Stoer-Wagner min-cut?

c++

algorithm

boost-graph