#include<stdlib.h>
#include<malloc.h>
#include<stdio.h>
#include<limits.h>
#include "graph.h"

int read_adjacency_matrix(char *datafile, adjmatrix mat){
	FILE *fp;
	int vertex_num;
	vindex src, dest;

	fp = fopen( datafile, "r" );
	fscanf( fp, "%d\n", &vertex_num );
	if ( vertex_num > N ) {
		fprintf( stderr, "##### このプログラムが扱えるのは頂点数が%d までのグラフです\n", N );
		exit(1);
	}
	for (src = 0; src < vertex_num; src++) {
		for (dest = 0; dest < vertex_num; dest++) {
			fscanf( fp, "%d\n", &mat[src][dest] );
		}
	}
	fclose( fp );
	return vertex_num;
}

void add_edge( graph *g, vindex src, vindex dest ) {
	edgecell *edge = (edgecell *)malloc( sizeof( edgecell ));
	edge->destination = dest;
	edge->next = g->vtop[src].adjlist;
	g->vtop[src].adjlist = edge;
}

void translate_into_graph( adjmatrix mat, graph *g ) {
	vindex i, j;
	for(i=g->vertex_num-1; i>=0; i--){
		g->vtop[i].adjlist=NULL;
		for(j=g->vertex_num-1; j>=0; j--){
			if(mat[i][j]==true){
				add_edge(g, i, j);
			}
		}
	}
}

void print_graph( graph *g ) {
	vindex v;
	printf( "digraph G {\n" );
	printf( " size=\"14,10\"; node[fontsize=10,height=0.01,width=0.01]; edge[len=3.0];\n");
	for (v = 0; v < g->vertex_num; v++) {
		edgecell *edge;
		for (edge = g->vtop[v].adjlist;edge != NULL; edge = edge->next) {
			printf( " %d -> %d;\n", v+1, edge->destination+1 );
		}
	}
		printf( "}\n" );
}

void free_graph( graph *g ) {
	vindex v;
	for (v = 0; v < g->vertex_num; v++) {
		edgecell *edge, *next_edge;
		for (edge = g->vtop[v].adjlist; edge != NULL; edge = next_edge) {
			next_edge = edge->next;
			free( edge );
		}
	}
}

//2頂点間の経路判定
boolearn judge_way(graph *g, vindex start, vindex target){
	static boolearn visited[N];
	static unsigned int depth = 0;
	//Init
	if(!depth){
		start--; target--;
		vindex iniv;
		for(iniv = 0; iniv < g->vertex_num; iniv++)
			visited[iniv] = false;
	}
	//Error
	if(depth == UINT_MAX){
		fprintf( stderr, "内部エラー\n");
		exit(1);
	}
	//Main
	visited[start] = true;
	edgecell *child;
	for(child = g->vtop[start].adjlist; child != NULL; child = child->next){
		if(child->destination == target)
			return true;
		if(!visited[child->destination]){
			depth++;
			if(judge_way(g, child->destination, target)){
				depth--;
				return true;
			}
			depth--;
		}
	}
	return false;
}

//強連結{sc(strongly connecteed)}グラフの判定
boolearn judge_sc_graph(graph *g){
	vindex v;
	for(v = 1; v <= g->vertex_num; v++)
		if(!(judge_way(g, v, (v%g->vertex_num)+1)))
			return false;
	return true;
}

//準オイラー{se(semi eularian)}グラフの判定
boolearn judge_se_graph(graph *g){
	int reldeg[N] = {0};
	vindex v, start = -1;

	edgecell *child;
	for(v = 0; v < g->vertex_num; v++){
		for(child = g->vtop[v].adjlist; child != NULL; child = child->next){
			reldeg[v]--;
			reldeg[child->destination]++;
		}
	}

	for(v = 0; v < g->vertex_num; v++){
		if(reldeg[v] == -1){
			if(start == -1)
				start = v;
			else
				return false;
		}
		else if(!(reldeg[v] == 0 || reldeg[v] == 1)){
			return false;
		}
	}
	if(start == -1)
		start = 0;

	for(v = 0; v < g->vertex_num; v++){
		if(v != start)
			if(!judge_way(g, start+1, v+1))
				return false;
	}

	return true;
}