//***********   Graph.h   ************//
//圖的基類

#define UNVISITED 0
#define VISITED 1
#define INFINITE 9999

//Edge類
class Edge  { 
public: 
	int weight;    //weight是邊的權
	int from;      //from是邊的始點
	int to;        //to是邊的終點
	Edge()  {		// 構造函數
		from = -1;  to = -1;  weight = 0;
	}							
	Edge(int f,int t,int w)   { // 構造函數
		from=f;   to=t;   weight=w;
	}
	bool operator < (const Edge &arg) {return (this->weight < arg.weight);};
	bool operator == (const Edge &arg) {return (this->weight == arg.weight);};
	bool operator > (const Edge &arg) {return (this->weight > arg.weight);};
	bool operator <= (const Edge &arg) {return (this->weight <= arg.weight);};
	bool operator >= (const Edge &arg) {return (this->weight >= arg.weight);};
};

//圖基類
class Graph  {
public:
	int numVertex;             //圖的頂點的個數
	int numEdge;				//圖的邊的數目
	int *Mark;					/*Mark指針指向保存有圖的頂點的標志位的數組,標志位用來標記某頂點是否被訪問過*/
	int *Indegree;				//Indegree指針指向保存有圖的頂點的入度的數組
	Graph(int numVert)  {		//構造函數
		numVertex = numVert;      //確定圖的頂點的個數
		numEdge = 0;				//確定圖的邊的數目
		Indegree = new int[numVertex]; /*為保存圖的頂點的入度申請數組,Indegree為數組指針*/
		Mark = new int[numVertex];	 /*為圖的頂點的標志位申請數組,Mark為數組指針*/
		
		for (int i = 0; i < numVertex; i ++)  {	/*確定圖的頂點的標志位和入度,即所有頂點的標志位初始化為未被訪問過,入度初始化為0*/
			Mark[i] = UNVISITED;
			Indegree[i] = 0;
		}
	}
	
	~Graph() {				//析構函數
		delete [] Mark;
		delete [] Indegree;
	}
	
	virtual Edge FirstEdge(int oneVertex) {	// 返回與頂點oneVertex相關聯的第一條邊
		Edge myEdge;
		myEdge.from = oneVertex; 
		myEdge.to = -1;
		return myEdge;
	}
	
	virtual Edge NextEdge(Edge preEdge) {      // 返回與邊PreEdge有相同關聯頂點的下一條邊
		return preEdge;
	}

	int VerticesNum() {		//返回圖的頂點個數
		return numVertex;
	}
	
	int EdgesNum() {			//返回圖的邊數
		return numEdge;
	}
	
	int FromVertex(Edge oneEdge) {  // 返回oneEdge的始點
		return oneEdge.from;
	}
	
	int ToVertex(Edge oneEdge) {	// 返回oneEdge的終點
		return oneEdge.to;
	}
	
	int Weight(Edge oneEdge) {		// 返回oneEdge的權值
		return oneEdge.weight;
	}
	
	bool IsEdge(Edge oneEdge)  {	//如果oneEdge是邊則返回TRUE，否則返回FALSE
		if (oneEdge.weight > 0 && oneEdge.weight < INFINITE && oneEdge.to >= 0)
			return true;
		else
			return false;
	}
	
	virtual void setEdge(int from, int to, int weight) = 0;
	virtual void delEdge(int from, int to) = 0;
};