#include <cassert>
#include <cstddef>
#include <iostream>
#include <map>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/graphviz.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>
#include "stoer_wagner_mincut.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::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> undirected_unweighted_graph;

// 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;

	undirected_graph g;
	vertex_descriptor v1 = boost::add_vertex(g),
		v2 = boost::add_vertex(g),
		v3 = boost::add_vertex(g),
		v4 = boost::add_vertex(g),
		v5 = boost::add_vertex(g),
		v6 = boost::add_vertex(g),
		v7 = boost::add_vertex(g),
		v8 = boost::add_vertex(g);
	BOOST_CHECK_NE(v1, v2);
	
	boost::add_edge(v1, v2, 2, g);
	boost::add_edge(v2, v3, 3, g);
	boost::add_edge(v3, v4, 4, g);
	boost::add_edge(v1, v5, 3, g);
	boost::add_edge(v2, v5, 2, g);
	boost::add_edge(v2, v6, 2, g);
	boost::add_edge(v3, v7, 2, g);
	boost::add_edge(v4, v7, 2, g);
	boost::add_edge(v4, v8, 2, g);
	boost::add_edge(v5, v6, 3, g);
	boost::add_edge(v6, v7, 1, g);
	boost::add_edge(v7, v8, 3, g);
	
	//boost::write_graphviz(std::clog, g);

	weight_map_type weights = boost::get(boost::edge_weight, g);
	std::map<vertex_descriptor, bool> ps;
	boost::associative_property_map<std::map<vertex_descriptor, bool> > parities(ps);
	std::map<vertex_descriptor, vertex_descriptor> as;
	boost::associative_property_map<std::map<vertex_descriptor, vertex_descriptor> > assignments(as);
	int w = stoer_wagner_mincut(g, weights, parities, assignments);
	BOOST_CHECK_EQUAL(w, 4);
	const bool parityV1 = boost::get(parities, v1);
	BOOST_CHECK_EQUAL(boost::get(parities, v1), boost::get(parities, v2));
	BOOST_CHECK_EQUAL(boost::get(parities, v1), boost::get(parities, v5));
	BOOST_CHECK_EQUAL(boost::get(parities, v1), boost::get(parities, v6));
	const bool parityV3 = boost::get(parities, v3);
	BOOST_CHECK_NE(parityV1, parityV3);
	BOOST_CHECK_EQUAL(boost::get(parities, v3), boost::get(parities, v4));
	BOOST_CHECK_EQUAL(boost::get(parities, v3), boost::get(parities, v7));
	BOOST_CHECK_EQUAL(boost::get(parities, v3), boost::get(parities, v8));
}

BOOST_AUTO_TEST_CASE(test1)
{
	typedef boost::graph_traits<undirected_graph>::vertex_descriptor vertex_descriptor;
	typedef boost::graph_traits<undirected_graph>::edge_descriptor edge_descriptor;
	
	undirected_graph g;
	vertex_descriptor v1 = boost::add_vertex(g),
		v2 = boost::add_vertex(g),
		v3 = boost::add_vertex(g),
		v4 = boost::add_vertex(g),
		v5 = boost::add_vertex(g),
		v6 = boost::add_vertex(g),
		v7 = boost::add_vertex(g);
	
	boost::add_edge(v6, v3, 1, g);
	boost::add_edge(v1, v7, 3, g);
	boost::add_edge(v6, v7, 4, g);
	boost::add_edge(v4, v2, 6, g);
	boost::add_edge(v1, v2, 4, g);
	boost::add_edge(v7, v4, 1, g);
	boost::add_edge(v5, v7, 2, g);
	boost::add_edge(v3, v5, 5, g);
	boost::add_edge(v6, v4, 2, g);
	
	//boost::write_graphviz(std::clog, g);
	
	weight_map_type weights = boost::get(boost::edge_weight, g);
	std::map<vertex_descriptor, bool> ps;
	boost::associative_property_map<std::map<vertex_descriptor, bool> > parities(ps);
	std::map<vertex_descriptor, vertex_descriptor> as;
	boost::associative_property_map<std::map<vertex_descriptor, vertex_descriptor> > assignments(as);
	int w = stoer_wagner_mincut(g, weights, parities, assignments);
	BOOST_CHECK_EQUAL(w, 3);
	const bool parityV3 = boost::get(parities, v3);
	BOOST_CHECK_EQUAL(parityV3, boost::get(parities, v5));
	const bool parityV6 = boost::get(parities, v6);
	BOOST_CHECK_NE(parityV3, parityV6);
	BOOST_CHECK_EQUAL(parityV6, boost::get(parities, v4));
	BOOST_CHECK_EQUAL(parityV6, boost::get(parities, v7));
	BOOST_CHECK_EQUAL(parityV6, boost::get(parities, v2));
	BOOST_CHECK_EQUAL(parityV6, boost::get(parities, v1));
}