//graph.cpp
#include<iostream>
#include "graph.h"//引入頭文件
 
/*
 *前置條件：圖不存在
 *輸    入：無 
 *功    能：圖的初始化
 *輸    出：無
 *后置條件：得到一個有向圖
 */
template <class T>
ALGraph<T>::ALGraph(T a[ ], int n, int e)
{
    arcNum = e;                             //邊數
	vertexNum=n;                            //頂點數
    int i,j;
	for (i=0; i<vertexNum; i++)
	{  
       VertexNode<T> tempvertex;
	   tempvertex.vertex = a[i];
	   tempvertex.firstedge = NULL;
	   adjlist[i] = tempvertex;
	}	
	for (int k=0; k<arcNum; k++)           //依次輸入每一條邊，并在相應邊表中插入結點
    { 
		cout<<"請輸入邊所依附的兩個頂點的序號";
		cin>>i>>j;                         //輸入邊所依附的兩個頂點的序號
        ArcNode *s=new ArcNode; s->adjvex=j;  //生成一個邊表結點s
	    s->next=adjlist[i].firstedge;      //將結點s插入到結點i的邊表的表頭  
        adjlist[i].firstedge=s;
	}
	InsertArc(0,1);                   //插入邊
	InsertArc(0,2);
	InsertArc(0,3);
	InsertArc(1,3);
	InsertArc(1,4);
	InsertArc(2,0);
	InsertArc(2,4);
	InsertArc(3,1);
	InsertArc(3,4);
	InsertArc(4,2);
	InsertArc(4,3);
}
/*   前置條件：圖已存在
 *   輸    入：無 
 *   功    能：銷毀圖
 *   輸    出：無
 *   后置條件：釋放圖所占用的存儲空間
 */
template <class T>
ALGraph<T>::~ALGraph( )
{
  for (int i=0; i<vertexNum; i++)
  {
    ArcNode * p=adjlist[i].firstedge;
	while (p!=NULL)                                              //循環刪除
	{
	  adjlist[i].firstedge=p->next;
	  delete p;                                                 //釋放結點空間
      p=adjlist[i].firstedge;
	}
  }
}
/*   
 *前置條件：圖已存在
 *輸    入：頂點i
 *功    能：輸出圖中頂點i的數據信息
 *輸    出：圖中頂點i的數據信息
 *后置條件：圖保持不變
 */
template <class T>
T ALGraph<T>::GetVex(int i)
{
	if ( i>vertexNum || i<0 ) throw "輸入頂點的位置不正確"; //頂點i不存在則拋出異常
	return adjlist[i].vertex;                               //返回第i個頂點的數據域  
}

/*
 *前置條件：圖已存在
 *輸    入：頂點i
 *功    能：將圖中頂點i的數據域置為value
 *輸    出：無
 *后置條件：圖保持不變
 */
template <class T>
void ALGraph<T>::PutVex(int i, T value)
{
	if ( i>vertexNum || i<0 ) throw "輸入頂點的位置不正確"; //頂點i不存在則拋出異常
	adjlist[i].vertex = value;                              //第i個頂點的數據域置為value
}
/*
 *前置條件：圖已存在
 *輸    入：頂點value,位置i
 *功    能：在圖中i位置插入一個頂點name 
 *輸    出：如果插入不成功，拋出異常
 *后置條件：如果插入成功，圖中增加了一個頂點
 */
template <class T>
void ALGraph<T>::InsertVex(int i, T value)
{
	if ( i>vertexNum || i<0 || i>MaxSize ) throw "輸入頂點的位置不正確"; //頂點i不存在則拋出異常
	vertexNum++;                                            //頂點數加1
	VertexNode<T> tempvertex;
	tempvertex.vertex = value;
	tempvertex.firstedge = NULL;
	adjlist[i] = tempvertex;  	                    //第i個頂點的數據域置為value	
}
/*   
 *前置條件：圖已存在
 *輸    入：頂點i 
 *功    能：在圖中刪除頂點i 
 *輸    出：如果刪除不成功，拋出異常
 *后置條件：如果刪除成功，圖中減少了一個頂點,相應頂點所建立的邊也消去
 */
template <class T>
void ALGraph<T>::DeleteVex(int i)
{
	if ( i<0 || i>MaxSize) throw "位置";       //頂點輸入錯誤則拋出異常
	int k;	
	for ( k=0; k<vertexNum; k++)               //刪掉入度邊
	   if(k!=i)	 DeleteArc(k, i);
	ArcNode *s;                                //生成一個邊表結點s
	if( adjlist[i].firstedge != NULL)
	{
		ArcNode *s;                         
		s=adjlist[i].firstedge->next;    
		while(s!=NULL)
		{
			ArcNode *p;                      
			p = s;
			adjlist[i].firstedge->next = s->next;
			s=s->next;
			delete p;                        //刪除p結點
		}
		s=adjlist[i].firstedge;
		adjlist[i].firstedge=NULL;
		delete s;
	}
	for (k=i; k<vertexNum; k++)
	{ 		
	   adjlist[k]=adjlist[k+1];             //存儲頂點信息       
	} 
   vertexNum--;                             //頂點數減1
   for (k=0; k<vertexNum; k++)
	if( adjlist[k].firstedge != NULL )
	{
		s=adjlist[k].firstedge;                //將結點s插入到結點i的邊表的表頭
		while(s!=NULL)
		{
			if(s->adjvex > i)                  //搜索i結點
				s->adjvex--;
			s = s->next;		
		}			
	}
}
/*   
 *前置條件：圖已存在
 *輸    入：頂點i、j
 *功    能：在圖中插入頂點i、j及其所依附的邊 
 *輸    出：如果插入不成功，拋出異常
 *后置條件：如果插入成功，圖中增加了一條邊
 */
template <class T>
void ALGraph<T>::InsertArc(int i, int j)
{
	if ( i>MaxSize || j>MaxSize) throw "位置";//頂點輸入錯誤則拋出異常
	ArcNode *s=new ArcNode; s->adjvex=j;      //生成一個邊表結點s
	s->next=adjlist[i].firstedge;             //將結點s插入到結點i的邊表的表頭  
    adjlist[i].firstedge=s;	
} 
/* 
 *前置條件：圖已存在
 *輸    入：頂點i、j 
 *功    能：在圖中刪除頂點i、j 依附的邊 
 *輸    出：如果刪除不成功，拋出異常
 *后置條件：如果刪除成功，圖中減少了一條邊
*/
template <class T>
void ALGraph<T>::DeleteArc(int i, int j)
{
	if ( i>MaxSize||  j>MaxSize) throw "位置";  //頂點輸入錯誤則拋出異常
	ArcNode *s;                                 
	ArcNode *tempnode;
	s = adjlist[i].firstedge;
	tempnode = adjlist[i].firstedge;
	while(s!=NULL && s->adjvex!=j)
	{
		tempnode = s;
		s = s->next;
	}
	if(s!=NULL)
	{
		tempnode->next = s->next;
		delete s;
	}	
}
/*   
 *前置條件：圖已存在
 *輸    入：遍歷的起始頂點v
 *功    能：從頂點v出發深度優先遍歷圖
 *輸    出：圖中頂點的一個線性排列
 *后置條件：圖保持不變
 */
template <class T>
void ALGraph<T>::DFSTraverse(int v)
{
	if ( v>vertexNum) throw "位置";                          //頂點輸入錯誤則拋出異常
	ArcNode * p;                                             
	int j;
	cout<<adjlist[v].vertex<<" ";  
	visited[v]=1;
    p=adjlist[v].firstedge;    
   while (p)                                                //依次搜索頂點v的鄰接點j
   {
      j=p->adjvex;
      if (visited[j]==0) DFSTraverse(j);
	  p=p->next;           
   }
}
/*
 *前置條件：圖已存在
 *輸    入：遍歷的起始頂點v
 *功    能：從頂點v出發廣度優先遍歷圖
 *輸    出：圖中頂點的一個線性排列
 *后置條件：圖保持不變
 */
template <class T>
void ALGraph<T>::BFSTraverse(int v)
{
  if ( v>vertexNum) throw "位置";                           //頂點輸入錯誤則拋出異常
  int front,rear,j;
  ArcNode * p;                                              //生成一個邊表結點p
  int Q[MaxSize];
  front=rear=-1;                                            //初始化隊列, 假設隊列采用順序存儲且不會發生溢出
  cout<<adjlist[v].vertex<<" ";  visited[v]=1; Q[++rear]=v; //被訪問頂點入隊
  while (front!=rear)
  {
     v=Q[++front];
     p=adjlist[v].firstedge;                                //邊表中的工作指針p初始化
     while (p) 
	 {
       j= p->adjvex;
       if (visited[j]==0) {
          cout<<adjlist[j].vertex<<" "; visited[j]=1;Q[++rear]=j;
     }
     p=p->next;
	}
  }
}