#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <libgen.h>

#include "assert.h"
#include "graph.h"

//#define DEBUG
#define BUF_SIZE 1000

int direct_graph;
int n_vertex;
VERTEX **vertexs;
int n_edge;
EDGE **edges;

void graph_create(void);
void graph_free(void);
int graph_coloring(void);
	int compare(const void *a, const void *b);
void DEBUG_graph(void);

int
main(int argc, char*argv[])
{
	int i;
	int n_color;

	graph_create();
	n_color = graph_coloring();

	printf("===================\n");
	for (i=0; i < n_vertex; i++){
		printf("vertex id : %d, color : %d\n",vertexs[i]->id, vertexs[i]->color);
	}
	printf("===================\n");
	printf("color number : %d.\n",n_color);
	printf("===================\n");

	graph_free();
	return 0;
}

void 
graph_create(void)
{
	FILE *fp;
	int i,j;
	char row[BUF_SIZE];
	char *value[MAX_EDGE];

	fp = fopen("input.txt","rt");
	if (fp==NULL){
		fprintf(stderr,"ERROF : Can't open input.txt.\n");
		exit(1);
	}

	fscanf(fp,"(%d %d)\n",&n_vertex, &n_edge);
	vertexs = (VERTEX**) calloc(n_vertex,sizeof(VERTEX*));
	mem_assert(vertexs);
	edges = (EDGE**) calloc(n_edge,sizeof(EDGE*));
	mem_assert(edges);
	for (i=0 ; i < n_vertex; i++) vertexs[i] = vertex_create(i);
	for (i=0 ; i < n_edge ; i++) edges[i] = edge_create(i);

	for (i=0 ; i < n_vertex; i++){
		fgets(row,BUF_SIZE,fp);
		bufsplit(row,n_edge,value);
		for (j=0; j < n_edge ; j++){
			if (!strcmp(value[j],"1")) {
				if (edges[j]->end_vertex == NULL){
					vertex_add_end_edge(vertexs[i],edges[j]);
					edge_add_end_vertex(edges[j],vertexs[i]);
				} else {
					vertex_add_start_edge(vertexs[i],edges[j]);
					edge_add_start_vertex(edges[j],vertexs[i]);
					edge_set_direct(edges[j], 0);
				}
			}
			if (!strcmp(value[j],"-1")) {
				vertex_add_start_edge(vertexs[i],edges[j]);
				edge_add_start_vertex(edges[j],vertexs[i]);
				edge_set_direct(edges[j], 1);
			}
		}
	}
	fclose(fp);
}

void
graph_free(void)
{
	int i;
	for (i=0; i < n_vertex ; i++)
		vertex_free(vertexs[i]);
	for (i=0; i < n_edge ; i++)
		edge_free(edges[i]);
	free(vertexs);
	free(edges);
}

int
graph_coloring(void)
{
	int i,j;
	int max_color=0;
	int color=0;

	// sort by degree of vertex
	qsort(vertexs,n_vertex,sizeof(VERTEX*),compare);

	// graph coloring
	for (i=0 ; i < n_vertex ; i++){
		color = 1;
		while (1) {
			for (j=0 ; j < vertexs[i]->n_start_edge ; j++){
				if ( vertexs[i]->start_edge[j]->end_vertex->color == color ){
					color++;
					break;
				}
			}
			if (j < vertexs[i]->n_start_edge)  continue;
			for (j=0 ; j < vertexs[i]->n_end_edge ; j++){
				if ( vertexs[i]->end_edge[j]->start_vertex->color == color ){
					color++;
					break;
				}
			}
			if (j < vertexs[i]->n_end_edge) continue;
			break;
		}
		if ( max_color < color ) max_color = color;
		vertex_set_color(vertexs[i],color);
	}
	return max_color;
}

int
compare(const void *a, const void *b)
{
	VERTEX *vertex1 = *((VERTEX**)a);
	VERTEX *vertex2 = *((VERTEX**)b);

	int n_vertex1_edge = vertex1->n_start_edge + vertex1->n_end_edge;
	int n_vertex2_edge = vertex2->n_start_edge + vertex2->n_end_edge;

	return (n_vertex2_edge - n_vertex1_edge);
}



#ifdef DEBUG
void 
DEBUG_graph(void)
{
	int i,j;
	
	printf ("======= edge =====\n");
	for (i=0; i < n_edge; i++){
		printf("id : %d\n",edges[i]->id);
		printf("start vertex : %d\n",edges[i]->start_vertex->id);
		printf("end vertex : %d\n",edges[i]->end_vertex->id);
	}
	
	printf ("======= vertex =====\n");
	for (i=0; i < n_vertex; i++){
		printf("id : %d, color : %d\n",vertexs[i]->id, vertexs[i]->color);
		for (j=0; j < vertexs[i]->n_start_edge; j++)
			printf("start edge : %d\n",vertexs[i]->start_edge[j]->id);
		for (j=0; j < vertexs[i]->n_end_edge; j++)
			printf("end edge : %d\n",vertexs[i]->end_edge[j]->id);
	}
	printf ("====================\n");
}
#endif