#include <iostream>                  // for std::cout
#include <utility>                   // for std::pair
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/one_bit_color_map.hpp>
#include <boost/graph/stoer_wagner_min_cut.hpp>
#include <boost/property_map/property_map.hpp>

using namespace boost;

int main(int,char*[])
{
    typedef adjacency_list < listS, vecS, undirectedS,
    no_property, property < edge_weight_t, int > > Graph;
    typedef std::pair<int, int> Edge;

    const int num_nodes = 8;
    Edge edge_array[] =
    {Edge(0,1), Edge(0,2), Edge(0,3),
    Edge(1,2), Edge(1,3), Edge(2,3),
    Edge(4,5), Edge(4,6), Edge(4,7),
    Edge(5,6), Edge(5,7), Edge(6,7),
    Edge(0,4)
    };
    int weights[] = {3,3,3,2,2,2,3,3,3,2,2,2,6};
    const int num_edges = sizeof(edge_array)/sizeof(edge_array[0]);

    // declare a graph object
    Graph g(edge_array, edge_array + num_edges, weights, num_nodes);
    property_map<Graph, edge_weight_t>::type weightmap = get(edge_weight, g);

    // define a property map, `parities`, that will store a boolean value for each vertex.
    // Vertices that have the same parity after `stoer_wagner_min_cut` runs are on the same side of the min-cut.
    BOOST_AUTO(parities, make_one_bit_color_map(num_vertices(g), get(vertex_index, g)));
    int w = boost::stoer_wagner_min_cut(g, get(edge_weight, g), parity_map(parities));

    std::cout << "The min-cut weight of G is " << w << ".\n" << std::endl;

    std::cout << "One set of vertices consists of:" << std::endl;
    size_t i;
    for (i = 0; i < num_vertices(g); ++i) {
        if (get(parities, i))
            std::cout << i << std::endl;
        }
    std::cout << std::endl;

    std::cout << "The other set of vertices consists of:" << std::endl;
    for (i = 0; i < num_vertices(g); ++i) {
        if (!get(parities, i))
            std::cout << i << std::endl;
    }
    std::cout << std::endl;
    return 0;
}