//圖類的實現文件

#include "graph.h"
#include <climits>

//構造函數
graph::graph()
{
	n=0;
	edgelist=NULL;
	vexlist=NULL;
}

//析構函數，用于釋放分配的內存空間
graph::~graph()
{
	int i;
	for(i=0;i<n;i++)
		delete[] edgelist[i];
	delete[] edgelist;
}

//數據讀取函數，內部函數，用于從數據文件中讀取路徑數據存入數組中
bool graph::readdata(string filename)
{
	int i,j;
	string tname1,tname2;
	int tweight,tprice;
	ifstream datafile;
	datafile.open(filename.c_str());
	datafile>>n;

	//分配內存空間	
	vexlist=new vexnode[n];
	edgelist=new edgenode*[n];
	for(i=0;i<n;i++)
	{
		edgelist[i]=new edgenode[n];
		for(j=0;j<n;j++)
		{
			if(i==j)
			{
				edgelist[i][j].weight=-1;
				edgelist[i][j].price=-1;
			}
			else
			{
				edgelist[i][j].weight=INT_MAX;
				edgelist[i][j].price=INT_MAX;
			}
			edgelist[i][j].pin=-1;
			edgelist[i][j].win=-1;
		}
	}

	//讀取地名信息
	for(i=0;i<n;i++)
		datafile>>vexlist[i].name;

	//讀取路徑信息－－距離，路費
	while(1)
	{
		datafile>>tname1>>tname2>>tweight>>tprice;
		datafile.ignore(1000,'\n');
		if(!datafile) break;
		for(i=0;i<n&&tname1!=vexlist[i].name;i++);
		for(j=0;j<n&&tname2!=vexlist[j].name;j++);
		edgelist[i][j].win=i;
		edgelist[i][j].pin=i;
		edgelist[i][j].weight=tweight;
		edgelist[i][j].price=tprice;
	}
	datafile.close();
	return true;
}

//路徑矩陣的計算生成函數，用于計算每兩個地點間的路徑信息
bool graph::creatgraph(string filename)
{
	int i,j,k;
	readdata(filename);

	//計算最短路程的路徑
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			if(j==i) continue;
			for(k=0;k<n;k++)
			{
				if(k==i||k==j) continue;
				if(edgelist[j][i].weight==INT_MAX||edgelist[i][k].weight==INT_MAX) continue;
				if(edgelist[j][k].weight>(edgelist[j][i].weight+edgelist[i][k].weight))
				{
					edgelist[j][k].weight=edgelist[j][i].weight+edgelist[i][k].weight;
					edgelist[j][k].win=i;
				}
			}
		}
	}

	//計算最少路費的路徑信息
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			if(j==i) continue;
			for(k=0;k<n;k++)
			{
				if(k==i||k==j) continue;
				if(edgelist[j][i].price==INT_MAX||edgelist[i][k].price==INT_MAX) continue;
				if(edgelist[j][k].price>(edgelist[j][i].price+edgelist[i][k].price))
				{
					edgelist[j][k].price=edgelist[j][i].price+edgelist[i][k].price;
					edgelist[j][k].pin=i;
				}
			}
		}
	}

	return true;
}

//查詢函數，用于兩地間路徑的輸出
bool graph::search(string start,string end)
{
	int i,j,tag;
	char ch;
	outlink *p,*q,*whead,*t,*phead;

	//特殊情況判斷
	if(start==end)
	{
		cout<<"一個城市，打的去吧！！"<<endl;
		ch=getch();
		return false;
	}
	for(i=0;i<n&&start!=vexlist[i].name;i++);
	if(i==n)
	{
		cout<<start<<"不存在！！"<<endl;
		ch=getch();
		return false;
	}
	for(j=0;j<n&&end!=vexlist[j].name;j++);
	if(j==n)
	{
		cout<<end<<"不存在！！"<<endl;
		ch=getch();
		return false;
	}
	if(edgelist[i][j].weight==INT_MAX)
	{
		cout<<start<<"與"<<end<<"之間無法到達"<<endl;
		ch=getch();
		return false;
	}

	//生成最短路程的路線表
	whead=new outlink;
	p=new outlink;
	whead->node=i;
	whead->link=p;
	p->node=j;
	p->link=NULL;

	do
	{
		p=whead;
		do
		{
			q=p;
			p=p->link;
			tag=0;
			if(edgelist[q->node][p->node].win!=q->node)
			{
				t=new outlink;
				t->node=edgelist[q->node][p->node].win;
				q->link=t;
				t->link=p;
				tag=1;
			}
			if(tag) break;
			
		}while(p->link!=NULL);
	}while(tag);

	//生成最少路費的路線表
	phead=new outlink;
	p=new outlink;
	phead->node=i;
	phead->link=p;
	p->node=j;
	p->link=NULL;

	do
	{
		p=phead;
		do
		{
			q=p;
			p=p->link;
			tag=0;
			if(edgelist[q->node][p->node].pin!=q->node)
			{
				t=new outlink;
				t->node=edgelist[q->node][p->node].pin;
				q->link=t;
				t->link=p;
				tag=1;
			}
			if(tag) break;
			
		}while(p->link!=NULL);
	}while(tag);

	//輸出結果
	system("cls");
	cout<<"查詢結果：從"<<start<<"到"<<end<<"路線為："<<endl;
	cout<<"最短路程路線為:";
	for(p=whead;p!=NULL;p=p->link)
	{
		cout<<vexlist[p->node].name;
		if(p->link!=NULL)
			cout<<"->";
	}
	cout<<endl;
	cout<<"總路程為："<<edgelist[i][j].weight<<endl;

	cout<<"最少路費路線為:";
	for(p=phead;p!=NULL;p=p->link)
	{
		cout<<vexlist[p->node].name;
		if(p->link!=NULL)
			cout<<"->";
	}
	cout<<endl;
	cout<<"總路費為："<<edgelist[i][j].price<<endl;
	ch=getch();

	//釋放查詢時所用的內存空間
	for(p=phead;q!=NULL;p=q)
	{
		q=p->link;
		delete p;
	}
	for(p=whead;q!=NULL;p=q)
	{
		q=p->link;
		delete p;
	}

	return true;
}