// Graph.cpp: implementation of the Graph class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "圖的操作界面.h"
#include "Graph.h"

#include<queue>
using namespace std;

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////




//////////////////////////////////////////////////////////////////////////////////////////////////


Graph::Graph(int v,int e,CString ch1)   //邊的個數和結點個數和各頂點
{
	numVertex=v;
	str=_T("");
	numEdge=e;
	ch=ch1;
	list=new LinkHead[v];        //初始化各值

	for(int i=0;i<v;i++) {list[i].Mark=0;list[i].next=0;}
}

bool Graph::InsertEdge(CString v,CString u,int Mark,int weight) //插入兩個頂點的邊和權值
{ 
	int i=-1;int j=-1;
	for(int k=0;k<n();k++)   //找兩個頂點所在的數組的坐標
	{
		 if(v==ch[k]) i=k;
	     if(u==ch[k]) j=k;
	}
	if(i==-1 || j==-1) return 0;
	Edge current=new EdgeLink(i,j,weight);    //頭插入建鏈
	current->next=list[i].next;
	list[i].next=current;
	if(Mark==0)                  //無向邊要作兩次的插入
	{
		current=new EdgeLink(i,j,weight);
	    current->next=list[j].next;
    	list[j].next=current;
	}
	return 1;
}

Graph::~Graph()           //析構函數
{
	if(list!=0)
	{
		for(int v=0;v<n();v++)    //先刪除鏈
			while(list[v].next!=0)
			{
				Edge temp=list[v].next;
				list[v].next=list[v].next->next;
                delete temp;  
			}
			delete [] list; //再刪除鏈頭
	}
}

Edge Graph::first(int v) {return list[v].next;} //邊的下一邊

bool Graph::isEdge(Edge w) {return w!=0;}   //邊是否存在

Edge Graph::next(Edge w)
{
	if(w!=0) return w->next;
	else return 0;
}

int Graph::v1(Edge w)    //邊的第一個頂點
{
	return w->v1;
}

int Graph::v2(Edge w) {return w->v2;} //邊的第二個頂點

int Graph::weight(int i,int j)    //兩個頂點間的權值
{
	for(Edge curr=list[i].next;curr!=0;curr=curr->next)
		if(curr->v2==j) return curr->weight;
		return 32767;         //無連通時
}

int Graph::weight(Edge w)   //邊的權值
{
	if(w!=0) return w->weight;
	else return w->weight;
}

void Graph::ReStart() //恢復數組的記錄頂點是否被訪問過
{
	for(int i=0;i<n();i++)
		list[i].Mark=0;
}

//**********************************************************************************************//

Graph1::Graph1(int v,int e,CString ch1)  //邊的個數和頂點個數，和各頂點
{
	ch=ch1;
	str=_T("");
	numVertex=v;
	numEdge=e;
    matrix=new int[v*v];                    //初始化
	for(int i=0;i<v*v;i++) matrix[i]=32767;
	for( i=0;i<v;i++) matrix[i*v+i]=0;


}

Graph1::~Graph1()   //析構函數
{
	if(matrix!=0) delete [] matrix;
}

bool Graph1::InsertEdge(CString v,CString u,int weight,int Mark) //插入兩個頂點的邊和權值
{
	int i=-1;int j=-1;
	for(int k=0;k<numVertex;k++)   //找兩個頂點所在的數組的坐標
	{
		 if(v==ch[k]) i=k;
	     if(u==ch[k]) j=k;
	}
	if(i==-1||j==-1) return 0;
	matrix[i*n()+j]=weight;       //是否是有向邊
	if(Mark==0) matrix[j*n()+i]=weight;
	return 1;
}


Edge1 Graph1::first(int v)
{
	int stop=(v+1)*numVertex;                 //在行里面尋找
	for(int pos=v*numVertex;pos<stop;pos++)
		if(pos==v*numVertex+v) continue;
		else if(matrix[pos]!=32767)  return &matrix[pos];   //找到返回
	return 0;
}

bool Graph1::isEdge(Edge1 w)  //邊是否存在
{
	return w!=0;
}

Edge1 Graph1::next(Edge1 w) //邊的下一邊
{
	int stop=(v1(w)+1)*numVertex;
	for(int pos=(w-matrix)+1;pos<stop;pos++)
		if(pos==v1(w)) continue;                        //（U，U）有它用不算
		else if(matrix[pos]!=32767) return &matrix[pos];
	return 0;
}

int Graph1::v1(Edge1 w)//邊的第一個頂點
{
	return (w-matrix)/numVertex;
}

int Graph1::v2(Edge1 w) //邊的第二個頂點
{
	return (w-matrix)%numVertex;
}

int Graph1::weight(Edge1 w)  //邊的權值，則邊的兩個頂點的坐標的值
{
	return matrix[(w-matrix)/numVertex*n()+(w-matrix)%numVertex];
}


//**********************************************************************************************//

CString Graph::TopSort()
{
	
	int *unsort=new int[n()];  //申請一個數組，用來記錄
	CString topsort;          //定義一個串，用來返回
	int top=-1;              //用上面的數組來作棧

	for(int i=0;i<n();i++) unsort[i]=0;  //初始化
	for(i=0;i<n();i++)
		for(Edge w=first(i);isEdge(w);w=next(w))  //計算直接前驅的個數
			unsort[v2(w)]++;
	for(i=0;i<n();i++)
		if(unsort[i]==0)    //把數組值為0的元素壓棧
		{ 
			  unsort[i]=top;    
			  top=i;
		}
	while(top!=-1)        //數組值為0的元素出棧
	{
		int v=top;
		top=unsort[top];
		topsort+=ch[v];
        topsort+=" ";
		for(Edge w=first(v);isEdge(w);w=next(w))
		{
			unsort[v2(w)]--;   //直接后繼頂點的值減一
			if(!unsort[v2(w)])
			{
				unsort[v2(w)]=top;
				top=v2(w);
			}
		}
	}
	ReStart();
	return topsort;
}

CString Graph::BFS(int start)  //廣度優先遍歷
{  
	ReStart();
	queue<int> Q;
	Q.push(start);
	CString Bfs="";//定義一個串，以返回串
	list[start].Mark=1;  //記錄訪問過的頂點
	while(!Q.empty())   //進行遍歷直到棧空為止；
	{
		int v=Q.front();
		Q.pop();               //出棧

	   Bfs+=ch[v];
	   Bfs+=" ";
 
		for(Edge w=first(v);isEdge(w);w=next(w))
			if(list[v2(w)].Mark==0)
			{
				list[v2(w)].Mark=1;
			    Q.push(v2(w));            //壓棧
			}
	}
	ReStart();   ////恢復鄰接表的用來記錄頂點是否被訪問的數（則將鏈頭組MARK的1改為0）          
	return Bfs;
}


CString Graph::DFS(int v)    //深度優先遍歷
{
	list[v].Mark=1;
	str+=ch[v];
	str+=" ";
	for(Edge w=first(v);isEdge(w);w=next(w))
	   if(list[v2(w)].Mark==0)
		  DFS(v2(w));
	return str;
}

//****************************************************************************************//

int Graph1::minVertex(int *D)   //在D數組中找值最小的且沒有訪問過的頂點
{
	int v;
	for(int i=0;i<n();i++)
		if(matrix[i*n()+i]==0) {v=i;break;}
	for( i=v+1;i<n();i++)
		if((matrix[i*n()+i]==0)&&(D[i]<D[v])) v=i;
	return v;
}

CString Graph1::Prim(CString c)  //最小生成樹
{
    int s=0;
	for(;s<n();s++)
		if(c==ch[s]) break;
	if((s==n())&& (c!=ch[s-1])) return str="";
	ReStart();
	int *dist=new int[n()];    //申請一個數組
	int *V=new int[n()];

	for(int i=0;i<n();i++)//初始化dist數組，所有頂點都屬于V-TV集合
		dist[i]=32767;

	 dist[s]=0; //為了將s加入生成樹中作為“種子”，把s的dist值設為最小

	for(i=0;i<n();i++) //循環n次，每次往T中加入一個新頂點
	{
		int v=minVertex(dist);                             //選擇V-TV中dist值最小的頂點v
		if(dist[v]==32767) return str="有無連通的點!";     //有無法到達的頂點

	    matrix[v*n()+v]=1;

	    if(v!=s) matrix[ V[v]*n()+v]=0-matrix[ V[v]*n()+v]; //把邊（V[v],v）在原矩陣中作標記
		                                                    //在矩陣中生成樹，把原來的權值變
		                                                    //為負，過后再恢復
		                                                

	    for(Edge1 w=first(v);isEdge(w);w=next(w))   //重新計算V-TV中的頂點到TV跌頂點的邊的最
			                                        //小權
		if(dist[v2(w)]>weight(w))                   
		{
			dist[v2(w)]=weight(w);
		    V[v2(w)]=v;
		}
	}
   printTree(s,n()); //打印樹，以線表形式打印；
   CString str1;
   str1=str;
   str="";
   return str1;
}


void Graph1::printTree(int s,int h)         //打印樹函數，類似于深度遍歷
{
                                            //h為需要打印的“——”個數
	for(int k=0;k<n()-h;k++) {str+="  ";str+="  ";} //實際上是共讀入兩個空格

	for(k=0; k<h; k++)       str+="__";

	str+=ch[s];
	str+="\r\n";                        //讀入換行回車符
    h--;                                //孩子的深度一樣，“——”數一樣

	for(Edge1 w=first(s);isEdge(w);w=next(w))  //如果在與結點S有邊關系的結點在樹中則遞歸
		if(matrix[v1(w)*n()+v2(w)]<=0)         //權值小于0的為樹中的邊
		{
			matrix[v1(w)*n()+v2(w)]=0-matrix[v1(w)*n()+v2(w)];
		    printTree( v2(w) ,h);
		}
}

int* Graph1::Dijkstra(CString c)    //求V到其余頂點的最短路徑
{

    int v=0;
	for(;v<n();v++)
		if(c==ch[v]) break;
	if( (v==n()) && (c!=ch[v-1]) ) return 0;

	int *dist=new int[n()];
	for(int i=0;i<n();i++) dist[i]=32767;  //初始化數組，各點不連通

	dist[v]=0;       //V已訪問

	for(i=0;i<n();i++)
	{
		int u=minVertex(dist);
		matrix[u*n()+u]=1;           //訪問U，此時dist[u]為v到u的最短路徑的長度

  //存在無法達到的頂點；

		for(Edge1 w=first(u);isEdge(w);w=next(w)) //重新計算數組
			if(dist[v2(w)]>(dist[u]+weight(w)))
               dist[v2(w)]=dist[u]+weight(w);
	}
	ReStart();
	return dist;    //返回數組
}

void Graph1::ReStart()
{
	for(int i=0;i<n();i++)
		matrix[i*n()+i]=0;
}


//**********************************************************************************************//