//            Copyright Daniel Trebbien 2010.
// Distributed under the Boost Software License, Version 1.0.
//   (See accompanying file LICENSE_1_0.txt or the copy at
//         http://www.boost.org/LICENSE_1_0.txt)

#include <fstream>
#include <iostream>
#include <map>
#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/connected_components.hpp>
#include <boost/graph/graph_traits.hpp>
//#include <boost/graph/graphviz.hpp>
#include <boost/graph/stoer_wagner_mincut.hpp>
#include <boost/property_map/property_map.hpp>
#define BOOST_TEST_DYN_LINK 1
#define BOOST_TEST_MAIN 1
#include <boost/test/unit_test.hpp>
#include <boost/tuple/tuple.hpp>

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::no_property, boost::property<boost::edge_weight_t, int> > undirected_graph;
typedef boost::property_map<undirected_graph, boost::edge_weight_t>::type weight_map_type;
typedef boost::property_traits<weight_map_type>::value_type weight_type;

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> undirected_unweighted_graph;

struct edge_t
{
    unsigned long first;
    unsigned long second;
};

// the example from Stoer & Wagner (1997)
BOOST_AUTO_TEST_CASE(test0)
{
    typedef boost::graph_traits<undirected_graph>::vertex_descriptor vertex_descriptor;
    typedef boost::graph_traits<undirected_graph>::edge_descriptor edge_descriptor;
    
    edge_t edges[] = {{0, 1}, {1, 2}, {2, 3},
        {0, 4}, {1, 4}, {1, 5}, {2, 6}, {3, 6}, {3, 7}, {4, 5}, {5, 6}, {6, 7}};
    weight_type ws[] = {2, 3, 4, 3, 2, 2, 2, 2, 2, 3, 1, 3};
    undirected_graph g(edges, edges + 12, ws, 8, 12);
    //boost::write_graphviz(std::clog, g);
    
    weight_map_type weights = get(boost::edge_weight, g);
    std::map<vertex_descriptor, bool> parity;
    boost::associative_property_map<std::map<vertex_descriptor, bool> > parities(parity);
    std::map<vertex_descriptor, vertex_descriptor> assignment;
    boost::associative_property_map<std::map<vertex_descriptor, vertex_descriptor> > assignments(assignment);
    int w = boost::stoer_wagner_mincut(g, weights, parities, get(boost::vertex_index, g), assignments);
    BOOST_CHECK_EQUAL(w, 4);
    const bool parity0 = get(parities, 0);
    BOOST_CHECK_EQUAL(parity0, get(parities, 1));
    BOOST_CHECK_EQUAL(parity0, get(parities, 4));
    BOOST_CHECK_EQUAL(parity0, get(parities, 5));
    const bool parity2 = get(parities, 2);
    BOOST_CHECK_NE(parity0, parity2);
    BOOST_CHECK_EQUAL(parity2, get(parities, 3));
    BOOST_CHECK_EQUAL(parity2, get(parities, 6));
    BOOST_CHECK_EQUAL(parity2, get(parities, 7));
}

BOOST_AUTO_TEST_CASE(test1)
{
    { // if only one vertex, can't run `boost::stoer_wagner_mincut`
        typedef boost::graph_traits<undirected_graph>::vertex_descriptor vertex_descriptor;
        typedef boost::graph_traits<undirected_graph>::edge_descriptor edge_descriptor;
    
        undirected_graph g;
        add_vertex(g);
        
        weight_map_type weights = get(boost::edge_weight, g);
        std::map<vertex_descriptor, bool> parity;
        boost::associative_property_map<std::map<vertex_descriptor, bool> > parities(parity);
        std::map<vertex_descriptor, vertex_descriptor> assignment;
        boost::associative_property_map<std::map<vertex_descriptor, vertex_descriptor> > assignments(assignment);
        BOOST_CHECK_THROW(boost::stoer_wagner_mincut(g, weights, parities, get(boost::vertex_index, g), assignments), std::invalid_argument);
    }{ // three vertices with one multi-edge
        typedef boost::graph_traits<undirected_graph>::vertex_descriptor vertex_descriptor;
        typedef boost::graph_traits<undirected_graph>::edge_descriptor edge_descriptor;
        
        edge_t edges[] = {{0, 1}, {1, 2}, {1, 2}, {2, 0}};
        weight_type ws[] = {3, 1, 1, 1};
        undirected_graph g(edges, edges + 4, ws, 3, 4);
        
        weight_map_type weights = get(boost::edge_weight, g);
        std::map<vertex_descriptor, bool> parity;
        boost::associative_property_map<std::map<vertex_descriptor, bool> > parities(parity);
        std::map<vertex_descriptor, vertex_descriptor> assignment;
        boost::associative_property_map<std::map<vertex_descriptor, vertex_descriptor> > assignments(assignment);
        int w = boost::stoer_wagner_mincut(g, weights, parities, get(boost::vertex_index, g), assignments);
        BOOST_CHECK_EQUAL(w, 3);
        const bool parity2 = get(parities, 2),
            parity0 = get(parities, 0);
        BOOST_CHECK_NE(parity2, parity0);
        BOOST_CHECK_EQUAL(parity0, get(parities, 1));
    }
}

// example by Daniel Trebbien
BOOST_AUTO_TEST_CASE(test2)
{
    typedef boost::graph_traits<undirected_graph>::vertex_descriptor vertex_descriptor;
    typedef boost::graph_traits<undirected_graph>::edge_descriptor edge_descriptor;
    
    edge_t edges[] = {{5, 2}, {0, 6}, {5, 6},
        {3, 1}, {0, 1}, {6, 3}, {4, 6}, {2, 4}, {5, 3}};
    weight_type ws[] = {1, 3, 4, 6, 4, 1, 2, 5, 2};
    undirected_graph g(edges, edges + 9, ws, 7, 9);
    //boost::write_graphviz(std::clog, g);
    
    weight_map_type weights = get(boost::edge_weight, g);
    std::map<vertex_descriptor, bool> parity;
    boost::associative_property_map<std::map<vertex_descriptor, bool> > parities(parity);
    std::map<vertex_descriptor, vertex_descriptor> assignment;
    boost::associative_property_map<std::map<vertex_descriptor, vertex_descriptor> > assignments(assignment);
    int w = boost::stoer_wagner_mincut(g, weights, parities, get(boost::vertex_index, g), assignments);
    BOOST_CHECK_EQUAL(w, 3);
    const bool parity2 = get(parities, 2);
    BOOST_CHECK_EQUAL(parity2, get(parities, 4));
    const bool parity5 = get(parities, 5);
    BOOST_CHECK_NE(parity2, parity5);
    BOOST_CHECK_EQUAL(parity5, get(parities, 3));
    BOOST_CHECK_EQUAL(parity5, get(parities, 6));
    BOOST_CHECK_EQUAL(parity5, get(parities, 1));
    BOOST_CHECK_EQUAL(parity5, get(parities, 0));
}

// example by Daniel Trebbien
BOOST_AUTO_TEST_CASE(test3)
{
    typedef boost::graph_traits<undirected_graph>::vertex_descriptor vertex_descriptor;
    typedef boost::graph_traits<undirected_graph>::edge_descriptor edge_descriptor;
    
    edge_t edges[] = {{3, 4}, {3, 6}, {3, 5}, {0, 4}, {0, 1}, {0, 6}, {0, 7},
        {0, 5}, {0, 2}, {4, 1}, {1, 6}, {1, 5}, {6, 7}, {7, 5}, {5, 2}, {3, 4}};
    weight_type ws[] = {0, 3, 1, 3, 1, 2, 6, 1, 8, 1, 1, 80, 2, 1, 1, 4};
    undirected_graph g(edges, edges + 16, ws, 8, 16);
    //boost::write_graphviz(std::clog, g);
    
    weight_map_type weights = get(boost::edge_weight, g);
    std::map<vertex_descriptor, bool> parity;
    boost::associative_property_map<std::map<vertex_descriptor, bool> > parities(parity);
    std::map<vertex_descriptor, vertex_descriptor> assignment;
    boost::associative_property_map<std::map<vertex_descriptor, vertex_descriptor> > assignments(assignment);
    int w = boost::stoer_wagner_mincut(g, weights, parities, get(boost::vertex_index, g), assignments);
    BOOST_CHECK_EQUAL(w, 7);
    const bool parity1 = get(parities, 1);
    BOOST_CHECK_EQUAL(parity1, get(parities, 5));
    const bool parity0 = get(parities, 0);
    BOOST_CHECK_NE(parity1, parity0);
    BOOST_CHECK_EQUAL(parity0, get(parities, 2));
    BOOST_CHECK_EQUAL(parity0, get(parities, 3));
    BOOST_CHECK_EQUAL(parity0, get(parities, 4));
    BOOST_CHECK_EQUAL(parity0, get(parities, 6));
    BOOST_CHECK_EQUAL(parity0, get(parities, 7));
}

BOOST_AUTO_TEST_CASE(test4)
{
    typedef boost::graph_traits<undirected_unweighted_graph>::vertex_descriptor vertex_descriptor;
    typedef boost::graph_traits<undirected_unweighted_graph>::edge_descriptor edge_descriptor;
    
    edge_t edges[] = {{0, 1}, {1, 2}, {2, 3},
        {0, 4}, {1, 4}, {1, 5}, {2, 6}, {3, 6}, {3, 7}, {4, 5}, {5, 6}, {6, 7},
        {0, 4}, {6, 7}};
    undirected_unweighted_graph g(edges, edges + 14, 8);
    //boost::write_graphviz(std::clog, g);
    
    std::map<vertex_descriptor, bool> parity;
    boost::associative_property_map<std::map<vertex_descriptor, bool> > parities(parity);
    std::map<vertex_descriptor, vertex_descriptor> assignment;
    boost::associative_property_map<std::map<vertex_descriptor, vertex_descriptor> > assignments(assignment);
    int w = boost::stoer_wagner_mincut(g, boost::make_constant_weight_property_map(g), parities, get(boost::vertex_index, g), assignments);
    BOOST_CHECK_EQUAL(w, 2);
    const bool parity0 = get(parities, 0);
    BOOST_CHECK_EQUAL(parity0, get(parities, 1));
    BOOST_CHECK_EQUAL(parity0, get(parities, 4));
    BOOST_CHECK_EQUAL(parity0, get(parities, 5));
    const bool parity2 = get(parities, 2);
    BOOST_CHECK_NE(parity0, parity2);
    BOOST_CHECK_EQUAL(parity2, get(parities, 3));
    BOOST_CHECK_EQUAL(parity2, get(parities, 6));
    BOOST_CHECK_EQUAL(parity2, get(parities, 7));
}

// The input for the `test_prgen` family of tests comes from a program, named
// `prgen`, that comes with a package of min-cut solvers by Chandra Chekuri,
// Andrew Goldberg, David Karger, Matthew Levine, and Cliff Stein. `prgen` was
// used to generate input graphs and the solvers were used to verify the return
// value of `boost::stoer_wagner_mincut` on the input graphs.
//
// http://www.columbia.edu/~cs2035/code.html
//
// Note that it is somewhat more difficult to verify the parities because
// "`prgen` graphs" often have several min-cuts. This is why only the cut
// weight of the min-cut is verified.

undirected_graph parse_noigen(std::istream& is)
{
    int n = -1, m = -1;
    std::vector<edge_t> edges;
    std::vector<weight_type> ws;
    while(is) {
        char l;
        if (is >> std::skipws >> l) {
            if (l == 'c') { // comment line
                char trash[4];
                while (is.getline(trash, 4).rdstate() & std::ios::failbit)
                    is.clear(is.rdstate() & ~std::ios::failbit);
            }
            else if (l == 'p') {
                assert(n < 0 && m < 0);
            
                std::string word;
                if (is >> std::skipws >> word) {
                    assert (word == "cut");
                    is >> n >> m;
                }
            }
            else if (l == 'a') {
                edge_t e = {0, 0};
                weight_type w;
                if (is >> e.first >> e.second >> w) {
                    --e.first; --e.second; // vertex indices in NOIGEN format start at 1
                    assert(n > e.first && e.first >= 0);
                    assert(n > e.second && e.second >= 0);
                    edges.push_back(e);
                    ws.push_back(w);
                }
            }
        }
    }
    
    assert(edges.size() == ws.size());
    assert(edges.size() == m);
    
    return undirected_graph(edges.begin(), edges.end(), ws.begin(), n, m);
}

// 3 min-cuts
BOOST_AUTO_TEST_CASE(test_prgen_20_70_2)
{
    typedef boost::graph_traits<undirected_graph>::vertex_descriptor vertex_descriptor;
    typedef boost::graph_traits<undirected_graph>::edge_descriptor edge_descriptor;

    std::ifstream ifs("prgen_20_70_2.txt");
    undirected_graph g = parse_noigen(ifs);
    
    std::map<vertex_descriptor, std::size_t> component;
    boost::associative_property_map<std::map<vertex_descriptor, std::size_t> > components(component);
    BOOST_CHECK_EQUAL(boost::connected_components(g, components), 1); // verify the connectedness assumption
    
    weight_map_type weights = get(boost::edge_weight, g);
    std::map<vertex_descriptor, bool> parity;
    boost::associative_property_map<std::map<vertex_descriptor, bool> > parities(parity);
    std::map<vertex_descriptor, vertex_descriptor> assignment;
    boost::associative_property_map<std::map<vertex_descriptor, vertex_descriptor> > assignments(assignment);
    int w = boost::stoer_wagner_mincut(g, weights, parities, get(boost::vertex_index, g), assignments);
    BOOST_CHECK_EQUAL(w, 3407);
}

// 7 min-cuts
BOOST_AUTO_TEST_CASE(test_prgen_50_40_2)
{
    typedef boost::graph_traits<undirected_graph>::vertex_descriptor vertex_descriptor;
    typedef boost::graph_traits<undirected_graph>::edge_descriptor edge_descriptor;

    std::ifstream ifs("prgen_50_40_2.txt");
    undirected_graph g = parse_noigen(ifs);
    
    std::map<vertex_descriptor, std::size_t> component;
    boost::associative_property_map<std::map<vertex_descriptor, std::size_t> > components(component);
    BOOST_CHECK_EQUAL(boost::connected_components(g, components), 1); // verify the connectedness assumption
    
    weight_map_type weights = get(boost::edge_weight, g);
    std::map<vertex_descriptor, bool> parity;
    boost::associative_property_map<std::map<vertex_descriptor, bool> > parities(parity);
    std::map<vertex_descriptor, vertex_descriptor> assignment;
    boost::associative_property_map<std::map<vertex_descriptor, vertex_descriptor> > assignments(assignment);
    int w = boost::stoer_wagner_mincut(g, weights, parities, get(boost::vertex_index, g), assignments);
    BOOST_CHECK_EQUAL(w, 10056);
}

// 6 min-cuts
BOOST_AUTO_TEST_CASE(test_prgen_50_70_2)
{
    typedef boost::graph_traits<undirected_graph>::vertex_descriptor vertex_descriptor;
    typedef boost::graph_traits<undirected_graph>::edge_descriptor edge_descriptor;

    std::ifstream ifs("prgen_50_70_2.txt");
    undirected_graph g = parse_noigen(ifs);
    
    std::map<vertex_descriptor, std::size_t> component;
    boost::associative_property_map<std::map<vertex_descriptor, std::size_t> > components(component);
    BOOST_CHECK_EQUAL(boost::connected_components(g, components), 1); // verify the connectedness assumption
    
    weight_map_type weights = get(boost::edge_weight, g);
    std::map<vertex_descriptor, bool> parity;
    boost::associative_property_map<std::map<vertex_descriptor, bool> > parities(parity);
    std::map<vertex_descriptor, vertex_descriptor> assignment;
    boost::associative_property_map<std::map<vertex_descriptor, vertex_descriptor> > assignments(assignment);
    int w = boost::stoer_wagner_mincut(g, weights, parities, get(boost::vertex_index, g), assignments);
    BOOST_CHECK_EQUAL(w, 21755);
}