BGL: obtenir des indices de bord de Stoer-Wagner min-coupe?

Question

Je trouve min-coupe d'un graphique en utilisant Stoer-Wagner algorithm in boost::graph. Le résultat est correct mais j'ai besoin d'obtenir les arêtes qui ont été coupées par l'algorithme. Je sais qu'il y a la possibilité de obtain parity map, mais je devrais analyser la carte pour obtenir les bords. Y a-t-il un moyen de les obtenir directement? Dans l'exemple ci-dessous, le poids de la coupe min est de 1, mais j'aimerais aussi obtenir la coupe du bord (0-2 dans ce cas).

(voir en direct à 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

Il n'y a pas de telle sorte, cependant, "analyser" la carte de parité est pas trop difficile:

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

Si vous êtes inquiet au sujet de la " coût supplémentaire "Je ne pense pas qu'il y en ait, car l'algorithme n'établit pas réellement les bords à couper, donc c'est toujours une tâche de dérivation¹.

Voici un exemple plus impliqué:

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

qui imprime:

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

L'échantillon a été prélevé des docs:

---

¹ a besoin de citation bien :)