#include <stdio.h>
#include "PerfectMatching.h"

class Blossom
{
public:
	void SaveMatching(int node_num, PerfectMatching* pm, char* filename, int* matches)
	{
//		FILE* fp = fopen(filename, "w");
//		if (!fp) { printf("Can't open %s\n", filename); exit(1); }
//		fprintf(fp, "%d %d\n", node_num, node_num/2);
		int i, j, m = 0;
		for (i=0; i<node_num; i++)
		{
			j = pm->GetMatch(i);
//			if (i < j) fprintf(fp, "%d %d\n", i, j);
			if (i < j)
			{
				matches[2*m] = i;
				matches[2*m++ + 1] = j;
			}
		}
//		fclose(fp);
	}

	double match(int node_num, int edge_num, int* edges, double* weightsD, int* matches)
	{
		////// matching ////////
		PerfectMatching* pm = new PerfectMatching(node_num, edge_num);
		for (int e=0; e<edge_num; e++) //pm->AddEdge(edges[2*e], edges[2*e+1], weights[e]);
									 pm->AddEdge(edges[2*e], edges[2*e+1], weightsD[e]);
		pm->Solve();
	
		double cost = -1.0; //of min-weight perfect matching
//		cost = //ComputePerfectMatchingCost(node_num, edge_num, edges, weights, pm);
//			   ComputePerfectMatchingCostDouble(node_num, edge_num, edges, weightsD, pm);

		SaveMatching(node_num, pm, "matches.txt", matches);
		delete pm;
		////// matching ends ////////

		return cost;
	}
};
