#include "P265.cpp"
#include "iostream.h"
#include "assert.h"

const int MaxNumEdges=100;
template <class NameType, class DistType>
Graph <NameType, DistType>::
Graph ( const int sz=DefaultSize ) : NumVertices (0), MaxNumVertices (sz), NumEdges (0) {
   int n, e, k, j;
   NameType name, tail, head;
   DistType weight;
   NodeTable = new Vertex<NameType,DistType>[MaxNumVertices];			//創(chuàng)建頂點(diǎn)表數(shù)組
   cin >> n;										//輸入頂點(diǎn)個(gè)數(shù)   
   assert(n<=sz);   
   for ( int i=0; i<n; i++)
   {
     cin >> name;
     InsertVertex ( name );
   }		//依次輸入頂點(diǎn), 插入圖中

   cin >> e;										//輸入邊數(shù)   
   assert(e<=MaxNumEdges);   
   for ( i=0; i<e; i++) {								//依次輸入邊信息
	 cin >> tail >> head >> weight;						//輸入各邊
	 k = GetVertexPos ( tail );  j = GetVertexPos ( head );			//取兩頂點(diǎn)位置
	 InsertEdge ( k, j, weight );							//插入圖中
   }
}

template <class NameType, class DistType> Graph<NameType, DistType>::~Graph ( ) {
   for ( int i=0; i<NumVertices; i++ ) {						//刪除各邊鏈表中的結(jié)點(diǎn)
	 Edge<NameType,DistType> *p = NodeTable[i].adj;
	 while ( p != NULL ) 							//循環(huán)刪除
	   {	NodeTable[i].adj = p->link;  delete p;  p = NodeTable[i].adj; }
   }
   delete [ ] NodeTable;								//刪除頂點(diǎn)數(shù)組
}

template <class NameType, class DistType>
int Graph<NameType, DistType>::GetVertexPos
( const NameType & vertex )
{
   for ( int i=0; i< NumVertices; i++) {

	 if ( NodeTable[i].data == vertex ) return i;
   }

   return -1;
}

template <class NameType, class DistType> int Graph<NameType, DistType>::GetFirstNeighbor ( const int v ) {
//給出頂點(diǎn)位置為v的第一個(gè)鄰接頂點(diǎn)的位置, 如果找不到, 則函數(shù)返回-1。
   if ( v != -1 ) {							//v存在
	 Edge<NameType,DistType> *p = NodeTable[v].adj;				//邊鏈表第一個(gè)結(jié)點(diǎn)地址
	 if ( p != NULL ) return p->dest;				//有, 返回該邊另一個(gè)頂點(diǎn)
   }
   return -1;								//沒(méi)有邊
}

template <class NameType, class DistType>
int Graph<NameType, DistType>::GetNextNeighbor ( const int v1, const int v2 ) {
//給出頂點(diǎn)v1的某鄰接頂點(diǎn)v2的下一個(gè)鄰接頂點(diǎn)的位置, 若沒(méi)有下一個(gè)鄰接頂點(diǎn), 則函數(shù)返回-1。
   if ( v1 != -1 ) {									//v1存在
	 Edge<NameType,DistType> *p = NodeTable[v1].adj;				//邊鏈表第一個(gè)結(jié)點(diǎn)地址
	 while ( p != NULL ) {							//尋找第v2個(gè)鄰接頂點(diǎn)
	   if ( p->dest == v2 && p->link != NULL ) return p->link->dest;
	   else p = p->link;
	 }
   }
   return -1;
}

template <class NameType, class DistType>
DistType Graph<NameType, DistType>::GetWeight ( const int v1, const int v2) {
//函數(shù)返回邊(v1, v2)上的權(quán)值, 若該邊不在圖中, 則函數(shù)返回權(quán)值0。
   if ( v1 != -1 && v2 != -1 ) {
	 Edge<NameType,DistType> *p = NodeTable[v1].adj;				//邊鏈表頭指針
	 while ( p != NULL ) {
	   if ( p->dest == v2 ) return p->cost;				//找到此邊, 返回權(quán)值
	   else p = p->link;							//否則找下一條邊
	 }
   }
   return 0;										//邊不在圖中
}