/*
 * TEST - TEST ADDITIVE COLORING CONJECTURE
 * Made in 2015-2016 by Daniel Severin
 * Partially supported by grants PID-UNR 416, PICT-2013-0586 and PIP-CONICET 11220120100277
 *
 * See GPL.txt for licensing information
 * 
 * WARNING: it requires ACOPT.exe compiled without "VERBOSE" definition; it also requires DSATUR.exe
 */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>

/* for linux users: do not define VISUALC */
#ifdef VISUALC
#include <windows.h>
#endif

#define VERBOSE
//#define CLOSEDADDITIVE

using namespace std;

/* GLOBAL VARIABLES */

FILE *stream; /* file handler */
int vertices, edges; /* number of vertices and edges */
int *edge_u, *edge_v; /* array of endpoints of edges */

/* FUNCTIONS */

/*
 * set_color - change color of text
 */
void set_color(int color)
{
#ifdef VISUALC
	SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), color);
#endif
}

/*
 * bye - finish executing and show a message
 */
void bye(char *string)
{
	set_color(12);
	cout << string << endl;
	set_color(7);
	exit(1);
}

/*
 * read_graph - read graph in the following format
 * first number is the number of instances, then for each instance we have:
 * first number is the number of vertices, second number is the number of edges
 * remaining number are the endpoints of each edge (u,v) with u < v, first u, then v 
 */
void read_graph(char separator)
{
	/* ask for memory */
	edge_u = new int[edges];
	edge_v = new int[edges];

	/* read edges of the graph */
	for (int e = 0; e < edges; e++) {
		int u, v;
		if (separator == ',') fscanf(stream, "%d,%d\n", &u, &v);
		else fscanf(stream, "%d %d", &u, &v);
		if (u < 0 || u >= v || v >= vertices) {
			cout << "Error reading edge " << e + 1 << "!" << endl;
			bye("Bye!");
		}
		edge_u[e] = u;
		edge_v[e] = v;
	}
}

/*
 * write_dimacs - write graph in DIMACS format
 */
void write_dimacs()
{
	FILE *stream2 = fopen("instance.txt", "wt");
	if (stream2 == NULL) bye("Error writing instance.txt");

	fprintf(stream2, "p edge %d %d\n", vertices, edges);
	for (int e = 0; e < edges; e++) {
		int u = edge_u[e];
		int v = edge_v[e];
		fprintf(stream2, "e %d %d\n", u+1, v+1);
	}
	fclose(stream2);
}

/*
 * write_graph - write graph in my format
 */
void write_graph()
{
	FILE *stream2 = fopen("instance.graph", "wt");
	if (stream2 == NULL) bye("Error writing instance.graph");

	fprintf(stream2, "%d:%d\n", vertices, edges);
	for (int e = 0; e < edges; e++) {
		int u = edge_u[e];
		int v = edge_v[e];
		fprintf(stream2, "%d,%d\n", u, v);
	}
	fclose(stream2);
}

/*
 * main - Main program
 */
int main(int argc, char **argv)
{
	set_color(15);
	cout << "TEST - Test Additive Coloring Conjecture." << endl;
	cout << "Made in 2015-2016 by Daniel Severin." << endl;
	set_color(7);

	if (argc < 2) {
		cout << "Usage: test file.all" << endl;
		return 1;
	}

	/* read file */
	stream = fopen(argv[1], "rt");
	if (!stream) bye("The file can not be opened");
	int count;
	fscanf(stream, "%d", &count);

	int instances = 0;
	
	/* read each instance */
	for (int i = 1; i <= count; i++) {
		if (i % 1000 == 0) cout << "Overall percentage: " << ((float)i * 100.0) / (float)count << "%  (" << i << "/" << count << ")" << endl;
		fscanf(stream, "%d %d", &vertices, &edges);
		read_graph(' ');

#ifdef VERBOSE
		/* we show some data */
		set_color(11);
		cout << "Graph " << i << " has " << vertices << " vertices and " << edges << " edges (density = " << 200.0*(float)edges / (float)(vertices*(vertices - 1)) << "%)." << endl;
#endif

#ifdef CLOSEDADDITIVE
		/* CHECK IF G HAS TRUE TWINS */
		bool **adjacency = new bool*[vertices]; /* binary adjacency matrix */
		for (int u = 0; u < vertices; u++) {
			adjacency[u] = new bool[vertices];
			for (int v = 0; v < vertices; v++) adjacency[u][v] = false;
		}
		/* generate adjacency matrix */
		for (int e = 0; e < edges; e++) {
			int u = edge_u[e];
			int v = edge_v[e];
			adjacency[u][v] = true;
			adjacency[v][u] = true;
		}
		/* scan every edge */
		bool discard = false;
		for (int e = 0; e < edges; e++) {
			int u = edge_u[e];
			int v = edge_v[e];
			/* check if u and v have the same close neighborhood */
			bool flag = true;
			for (int w = 0; w < vertices; w++) {
				if (w != u && w != v) {
					if (adjacency[u][w] != adjacency[v][w]) {
						flag = false;
						break;
					}
				}
			}
			if (flag) {
				/* u and v are true twins, discard current graph! */
#ifdef VERBOSE
				cout << "Vertices " << u << " and " << v << " are true twins. Discarding graph!" << endl;
#endif
				discard = true;
				break;
			}
		}
		for (int v = 0; v < vertices; v++) delete[] adjacency[v];
		delete[] adjacency;

		if (discard) continue;
#endif

		/* save graph in .txt format (DIMACS) */
		write_dimacs();

		/* perform optimization for obtaining chi(G) */
		system("dsatur.exe instance.txt -v >result_dsatur.txt");
		FILE *stream2 = fopen("result_dsatur.txt", "rt");
		char str1[20], str2[20], str3[20];
		int chi;
		fscanf(stream2, " %s %s %s %d", str1, str2, str3, &chi);
		fclose(stream2);
		if (chi < 2 || chi > vertices) bye("Error after execution of DSATUR");

		/* save graph in .graph format */
		write_graph();

		/* perform optimization for obtaining eta(G) with acopt */
		char command[128];
		/* the following line is faster since an additive chi(G)-coloring is searched instead of searching for eta(G)
		   if you want the latter, replace that line with:
		sprintf(command, "acopt.exe instance.graph %d >result_acopt.txt", chi); */
		sprintf(command, "acopt.exe instance.graph %d %d >result_acopt.txt", chi, chi);
		int val = system(command);
		if (val != 0) bye("CONJECTURE IS NOT VALID! :(");
		stream2 = fopen("result_acopt.txt", "rt");
		int eta;
		fscanf(stream2, "%d", &eta);
		fclose(stream2);
		if (eta < 1 || eta > chi) bye("Error after execution of ACOPT");
		instances++;

		/* free memory */
		delete[] edge_v;
		delete[] edge_u;
	}

	set_color(10);
	cout << "Conjecture holds! :)" << endl;
	cout << "Instances tested: " << instances << endl;

	fclose(stream);
	return 0;
}