Search code examples
c++algorithmboost-graph

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

I am finding min-cut of a graph using 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, but I'd have to analyze the map to obtain the edges. Is there a way to get those directly?

In the example below, the min-cut weight is 1, but I'd like to get the edge(s) cut (0-2 in this case) as well.

(see live at 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;
}
Solution

  • There's no such way, however, "analysing" the parity map is not too hard:

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

    If you're worried about the "added cost" I don't think there is that, because the algorithm doesn't actually establish the edges to cut, so it's always a derivation task¹.

    Here's a more involved example:

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

    Which prints:

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

    The sample was taken from the docs:

    ¹ needs citation though :)