#include "StdAfx.h"
#include "Graph.h"

//圖的鄰接矩陣表示,任意兩個頂點最短路徑算法

#include "assert.h"
#include "queue.h"

#include "Sqlist.h"
//#include "MinSpanTree.h"

extern CSqlist VerticesList;			//頂點表

CGraph::CGraph ( int sz ){
	//構造函數
	for ( int i=0; i<sz; i++ )					//鄰接矩陣初始化
		for ( int j=0; j<sz; j++ ) Edge[i][j] = MAXINT;
}


int CGraph::GetValue ( const int i )			//取頂點i的值, i不合理則返回空
{ return VerticesList.Get(i); }	

int CGraph::GetWeight ( const int v1, const int v2 ) 
{
	//給出以頂點v1和v2為兩端點的邊上的權值
	if ( v1 != -1 && v2 != -1 ) return Edge[v1][v2];
	else return NULL;							//帶權圖中權值為0, 表示無權值
}

int CGraph::GetFirstNeighbor ( const int v ) {
	//給出頂點位置為v的第一個鄰接頂點的位置, 如果找不到, 則函數返回-1。
	if ( v != -1 ) {
		for ( int col=0; col<VERTICES; col++ ) if ( Edge[v][col] > 0 && Edge[v][col] < MAXINT ) return col;
	}
	return -1;
}

int CGraph::GetNextNeighbor ( const int v1, const int v2 ) {
	//給出頂點v1的某鄰接頂點v2的下一個鄰接頂點
	if ( v1 != -1 && v2 != -1 )
	{
		for ( int col=v2+1; col<VERTICES; col++ )
			if ( Edge[v1][col] > 0 && Edge[v1][col] < MAXINT ) return col;
	}
	return -1;
}

void CGraph::InsertVertex ( int vertex )		//插入一個頂點vertex, 該頂點沒有入邊
{
	if(VerticesList.Length()<=MaxNumVertices)
		VerticesList.Insert ( vertex, VerticesList.Length() );		
};

void CGraph:: InsertEdge ( const int v1, const int v2, int weight )	//插入一條邊(v1, v2), 該邊上的權值為weight
{
	Edge[v1][v2]=weight;
};

/*int *CGraph::Prim(int& count){
	MinSpanTree T;
	int NumVertices = VERTICES;
    int * lowcost = new int [NumVertices];
    int * nearvex = new int [NumVertices];
    int *iPointIndex = new int [VERTICES+1];
    count = 0;
       for(int i=1; i<NumVertices;i++){
             lowcost[i]=Edge[0][i];
             nearvex[i]=0;
	   }
          nearvex[0]=-1;
		  iPointIndex[count++]=0;
          MSTEdgeNode e;
   for( i=1; i<NumVertices;i++){
    int min=MAXINT;int v=0;
    for(int j=0; j<NumVertices;j++)
         if(nearvex[j]!=-1&&lowcost[j]<min){v=j;min=lowcost[j];}
		 iPointIndex[count++]=v;
		 if(v){
			 e.tail=nearvex[v];
	         e.head=v;
	         e.cost=lowcost[v];
	         T.Inser(e);
	         nearvex[v]=-1;
         for(int j=1; j<NumVertices;j++)
	    if(nearvex[j]!=-1&&Edge[v][j]<lowcost[j])
		{lowcost[j]=Edge[v][j];nearvex[j]=v;}
		 }
   }
	return iPointIndex;
}
*/

 
int *CGraph::DFS(int& count) //對連通圖進行深度優先搜索的主過程
{				
	int *iPointIndex = new int [VERTICES+1];
	int *visited	 = new int [VERTICES];			//創建輔助數組
	count			 = 0;
	for (int i=0; i<VERTICES; i++)
	{
		visited [i] = 0;							//輔助數組初始化
	}

	for (i=0; i<VERTICES; i++) 
	{
		if (!visited[i])  
			DFS (i ,visited, count, iPointIndex);	//從頂點0開始深度優先搜索
	}

	iPointIndex[count++] =18;
	count=19;

	return iPointIndex;
}

void CGraph::DFS( const int v, int visited [ ], int& count, int *iPointIndex) 
{
	//從頂點位置v出發, 以深度優先的次序訪問所有可讀入的尚未訪問過的頂點。算法中用到一個輔助數組
	// visited, 對已訪問過的頂點作訪問標記。
	
	//訪問該頂點的數據
	iPointIndex[count++] = GetValue(v);
	visited[v] = 1;									//訪問標志改為已訪問過
	int w = GetFirstNeighbor(v);					//找頂點v的第一個鄰接頂點w
	while ( w != -1 )								//有鄰接頂點
	{				
		if ( !visited[w] )
		{	
			DFS(w, visited, count, iPointIndex);	//若未訪問過, 從w遞歸訪問
		}
		w = GetNextNeighbor( v,w );				//找頂點v的下一個鄰接頂點
	}
}

 
void CGraph:: AllLengths ( )
{
	//Edge[n][n]是一個具有n個頂點的圖的鄰接矩陣。a[i][j]是頂點i和j之間的最短路徑長度。path[i][j]是相應路
	//徑上頂點j的前一頂點的頂點號, 在求最短路徑時圖的類定義中要修改path為path[NumVertices][NumVertices]。
	for ( int i=0; i<VERTICES; i++ )
	{
		for ( int j=0; j<VERTICES; j++ ) 	//矩陣a與path初始化
		{						
			if (i!=j) 
				dist[i][j] = Edge[i][j];
			else 
				dist[i][j]=0;

			if ( i != j && dist[i][j] < MAXINT ) 
				path[i][j] = i;							// 有路徑
			else 
				path[i][j] =-1;							// i到j無路徑
		}
	}

	for ( int k=0; k<VERTICES; k++ )	//產生a(k)及相應的path(k)
	{
		for ( i=0; i<VERTICES; i++ )
		{
			if (path[i][k] >= 0)
			{
				for ( int j=0; j<VERTICES; j++ )
				{
					if( path[k][j]>=0 && dist[i][k] + dist[k][j] < dist[i][j] )
					{
						dist[i][j] = dist[i][k] + dist[k][j];
						path[i][j] = path[k][j];		//縮短路徑長度, 繞過k到j
					}
				}
			}
		}
	}
}

int *CGraph::BestPath(int start,int end, int &verNum, int& distance)
{
	int* iPointIndex = NULL; 
	CWordArray wArray; 
	wArray.RemoveAll();
	verNum = 0;
	for (int index= path[start][end]; index!=start;)
	{
		if (start != end)
		{
			if(Edge[index][path[start][index]]>0&&Edge[index][path[start][index]]<MAXINT)
			{
				wArray.Add(index);
			    index= path[start][index];
			}
			else
			{
				wArray.Add(path[start][index]);
				wArray.Add(index);
			    index= path[start][index];
			}
		}
		else
			break;
	
	}
	int count = wArray.GetSize();
	iPointIndex = new int[count+3];
	iPointIndex[verNum++] = start;

	for (int i= count; i>0; i--)
	{
		iPointIndex[verNum++] = wArray.GetAt(i-1);
	}

	iPointIndex[verNum++] = end;

	distance = dist[start][end];

	return iPointIndex;
}