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

/************************************************************************/
/*從文件中讀入圖像信息并構成圖像
/************************************************************************/
graph* creatgraph(char* s)
{
	FILE *fp = fopen(s,"r");//打開文件
	if (!fp) {
		printf("Can't open the file!");
		exit(0);
	}
	//申請空間并生成圖像信息
	graph* g=(graph*)malloc(sizeof(graph));
	fscanf(fp,"%d",&g->vernum);
	fscanf(fp,"%d",&g->arcnum);
	int n=g->vernum;
	int * mat=(int *)malloc(sizeof(int)*n*n);//獲得圖像鄰接矩陣
	if (!mat) {
		printf("memory flow!");
		exit(0);
	}
	for (int i=0;i<n;i++ ) {
		for (int j=0;j<n;j++) {
			fscanf(fp,"%d",&mat[i*n+j]);
		}
	}
	g->nermat = mat;
	g->suit = false;
	return(g);
}

/************************************************************************/
/*得到圖像的邊信息
/************************************************************************/
void getarcinfo(graph* g,arc * a)
{
	int num = 0;
	int n= g->vernum;
	int *t = g->nermat;
	for (int i=0;i<n;i++) {//無向圖，只用掃描其中的一半
		for (int j=0;j<=i;j++) {
			if(t[i*n+j]>0)
			{
				a[num].start = i;
				a[num].end = j;
				a[num++].weight = t[i*n+j];
			}
		}
	}
}
/************************************************************************/
/*對圖像進行旅行商問題搜索
/************************************************************************/
int* TSP(graph* g)
{
	int n=g->arcnum;
	int vn = g->vernum;
	int d=INT_MAX;
	bool first = true;//判斷石構繼續循環
	bool seccess = false;//是否找到適合的路徑
	arc* a= (arc*)malloc(sizeof(arc)*n);
	getarcinfo(g,a);//獲得圖像邊的信息
	sort(a,n);//對各個邊進行排序
	int * ser = (int *)malloc(sizeof(int)*(vn+1));//當前序列
	int * path = (int *)malloc(sizeof(int)*(vn+1));//路徑儲存
	for (int i=0;i<vn;i++) {
		path[i] = -1;
	}
	for (int j=0;j<vn;j++) {
		ser[j]=j;
	}
	int k=1;int num=vn;
	while (k<=vn) {
		while (!seccess) {
			getarc(a,ser,vn);//得到當前路徑的總長度
			if (ser[vn]>d) {//比最短路徑長
				num=vn-1;
				while (ser[num]==ser[num-1]+1) {
					num--;
				}
				if (num == vn-k) {
					break;//跳出被循環
				}
				else{//尋找更短的路徑
					ser[num-1]++;
					for (int i=num;i<vn;i++) {
						ser[i]=ser[i-1]+1;
					}
				}
			}else{
				first = false;
				if (test(a,ser,vn)) {//判斷時候構成回路
					d=ser[vn];//保存路徑信息
					for (int i=0;i<=vn;i++) {
						path[i]=ser[i];
					}
					seccess = true;
					break;
				}
				else{
					num=1;//尋找下一條路徑
					while (ser[vn-num]==n-num) {
						num++;
					}
					ser[vn-num]++;
					for (int i=vn-num+1;i<vn;i++) {
						ser[i] = ser[i-1]+1;
					}
				}

			}
		}
		if (first) {
			break;
		}
		k++;
		seccess = false;
		first = true;
		for (int j=0;j<vn-k;j++) {
			ser[j] = j;
		}
		while (j<vn) {
			ser[j] = j+1;
			j++;
		}

	}
	for (int i=0;i<vn;i++) {
		if(path[i] == -1)
		{
			printf("there is even not a circle!\n");
			return(NULL);
		}
	}
	shoepath(a,path,vn);//顯示路徑信息
	free(a);
	free(ser);
	return(path);
}
/************************************************************************/
/*根據邊的序號顯示旅行商的路徑信息
/************************************************************************/
void shoepath(arc* a,int* ser,int n)
{
	int num=n-1;
	bool * over = (bool*)malloc(sizeof(bool)*n);
	int set = a[ser[0]].end;
	over[0] =true;
	for (int i=1;i<n;i++) {
		over[i] = false;
	}
	printf("MiniLength:%d\n",ser[n]);
	printf("%d->",a[ser[0]].start+1);
	while (num>0) {
		for (int i=0;i<n;i++) {
			if (!over[i]) {
				if (a[ser[i]].start == set) {
					printf("%d->",a[ser[i]].start+1);
					set = a[ser[i]].end;
					over[i] = true;
					break;
				}else if(a[ser[i]].end == set){
					printf("%d->",a[ser[i]].end+1);
					set = a[ser[i]].start;
					over[i] = true;
					break;
				}
			}
		}
		num--;
	}
	printf("%d\n",set+1);
	free(over);
}
/************************************************************************/
/*根據當前的狀態獲取幾條邊
/************************************************************************/
void getarc(arc* a,int *ser,int n)
{
	ser[n] = 0;
	for (int i=0;i<n;i++) {
		ser[n] += a[ser[i]].weight;
	}
}

/************************************************************************/
/*測試這幾條邊能不能構成回路
/************************************************************************/
bool test(arc*a,int* ser,int n)
{
	int num=n;
	bool * over = (bool*)malloc(sizeof(bool)*n);
	bool get = false;
	for (int i=0;i<n;i++) {
		over[i] = false;
	}
	int set = a[ser[0]].end;
	over[0] =true;
	num--;
	while (num>0) {
		for (int i=0;i<n;i++) {
			if (!over[i]) {
				if (a[ser[i]].start == set) {
					set = a[ser[i]].end;
					over[i] = true;
					get =true;
					break;
				}else if(a[ser[i]].end == set){
					set = a[ser[i]].start;
					over[i] = true;
					get = true;
					break;
				}
			}
		}
		if (!get) {
			free(over);
			return(false);
		}
		num--;
		get = false;
	}
	free(over);
	if (set == a[ser[0]].start) {
		return(true);
	}else{
		return(false);
	}

}