BGL：來自Stoer-Wagner min-cut的邊緣指數？

Question

我使用Stoer-Wagner algorithm in boost::graph發現圖的最小切割。結果是正確的，但我需要得到算法切割的邊緣。我知道有可能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

有沒有這樣的方式，但是， 「分析」 奇偶地圖是不是太辛苦：

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 

的樣品從文檔採取：

---

¹需要引用雖然:)