#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <map>
#include "Blossom/PerfectMatching.h"

using namespace std;
using namespace boost;

const double DOUBLE_MAX = 1e100;

struct EdgeInfo
{
	double weight;
};

template<typename G>
void printGraph(G graph, string file)
{
	ofstream ofs(file.c_str());
	dynamic_properties dp;
	dp.property("node_id", get(vertex_index, graph));
	dp.property("label", get(&EdgeInfo::weight, graph));
	write_graphviz_dp(ofs, graph, dp);
}

/// Maximum Matching Algorithm
/// We use
/// Vladimir Kolmogorov. "Blossom V: A new implementation of a minimum cost perfect matching algorithm."
/// In Mathematical Programming Computation (MPC), July 2009, 1(1):43-67.
/// We apply the Guido Shafer Reduction to solve the Maximum
/// Weighted Matching Problem via the Maximum Weighted Perfect
/// Matching. Guido Thesis:
/// http://homepages.cwi.nl/~schaefer/ftp/pdf/masters-thesis.pdf.
/// Authors: 
///          Juan Fraire (juanfraire@gmail.com)
///          Pablo Madoery (madoerypablo@gmail.com)
///
/// @param[in] G graph: graph to apply Maximum Matching Algorithm.
/// @param[in] bool maximize: if(true) maximime weight, if(false) minimize weight.
/// @param[out] G graph: graph solution.
/// Note: the Graph use bundle property called weight associated with edges.
template<typename G>
G computeLogicalTopology(const G &graph, bool maximize)
{
	G graphExp = graph;

	map<typename G::vertex_descriptor, typename G::vertex_descriptor> mapVertices;

	typedef typename G::vertex_iterator vertex_iter;
	vertex_iter vi, vi_end;

	for (tie(vi, vi_end) = vertices(graph); vi != vi_end; ++vi)
	{
		typename G::vertex_descriptor v2 = add_vertex(graphExp);
		typename G::edge_descriptor e2 = (add_edge(*vi, v2, graphExp)).first;

		if(maximize)
		{
			graphExp[e2].weight = 0;
		}
		else
		{
			graphExp[e2].weight = DOUBLE_MAX;
		}

		mapVertices[*vi] = v2;
	}

	typedef typename G::edge_iterator edge_iter;
	edge_iter ei, ei_end;

	for (tie(ei, ei_end) = edges(graph); ei != ei_end; ++ei)
	{
		// vértices en G
		typename G::vertex_descriptor u = source(*ei, graph);
		typename G::vertex_descriptor v = target(*ei, graph);

		// vértices en G'
		typename G::vertex_descriptor u2 = mapVertices[u];
		typename G::vertex_descriptor v2 = mapVertices[v];

		typename G::edge_descriptor e2 = (add_edge(u2, v2, graphExp)).first;
		graphExp[e2].weight = graphExp[*ei].weight;
	}

	//////////////////////////////////////////////////////////////////////////

	int nNodes = num_vertices(graphExp);
	int nEdges = num_edges(graphExp);

	PerfectMatching *perfectMatching = new PerfectMatching(nNodes, nEdges);

	map<int, typename G::edge_descriptor> mapEdges;

	for (tie(ei, ei_end) = edges(graphExp); ei != ei_end; ++ei)
	{
		typename G::vertex_descriptor u = source(*ei, graphExp);
		typename G::vertex_descriptor v = target(*ei, graphExp);

		int edgeId;
		if(maximize)
		{
			edgeId = perfectMatching->AddEdge(u, v, -graphExp[*ei].weight);
		}
		else
		{
			edgeId = perfectMatching->AddEdge(u, v, graphExp[*ei].weight);
		}
		mapEdges[edgeId] = *ei;
	}

	perfectMatching->Solve(true);

	for (int edgeId = 0; edgeId < nEdges; edgeId++)
	{
		if (perfectMatching->GetSolution(edgeId) != 1)
		{
			typename G::edge_descriptor e = mapEdges[edgeId];
			remove_edge(e, graphExp);
		}
	}

	delete perfectMatching;

	typename map<typename G::vertex_descriptor, typename G::vertex_descriptor>::iterator it;
	for(it = mapVertices.begin(); it != mapVertices.end(); ++it)
	{
		typename G::vertex_descriptor v = it->second;
		clear_vertex(v, graphExp);
	}
	for(it = mapVertices.begin(); it != mapVertices.end(); ++it)
	{
		typename G::vertex_descriptor v = it->second;
		remove_vertex(v, graphExp);
	}

	return graphExp;
}

int main()
{
	typedef adjacency_list<listS, vecS, bidirectionalS, no_property, EdgeInfo> Graph;

	Graph graph;
	Graph::vertex_descriptor a = add_vertex(graph);
	Graph::vertex_descriptor b = add_vertex(graph);
	Graph::vertex_descriptor c = add_vertex(graph);
	Graph::vertex_descriptor d = add_vertex(graph);
	Graph::edge_descriptor e1 = (add_edge(a, b, graph)).first;
	Graph::edge_descriptor e2 = (add_edge(a, b, graph)).first;
	Graph::edge_descriptor e3 = (add_edge(b, c, graph)).first;
	Graph::edge_descriptor e4 = (add_edge(c, a, graph)).first;
	Graph::edge_descriptor e5 = (add_edge(c, a, graph)).first;
	Graph::edge_descriptor e6 = (add_edge(c, d, graph)).first;

	graph[e1].weight = 1.2;
	graph[e2].weight = 2.1;
	graph[e3].weight = 4.8;
	graph[e4].weight = 2.3;
	graph[e5].weight = 1.2;
	graph[e6].weight = 3.6;

	printGraph(graph, "graph.dot");

	bool maximize = true;
	Graph graph2 = computeLogicalTopology(graph, maximize);

	printGraph(graph2, "graph2.dot");

	cout << "fin" << endl;

	return 0;
}

