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

#define UNVISITED 0
#define VISITED 1
#define INFINITE 0xffffffff

//Edge類
class Edge  { 
public: 
	int weight;    //weight是邊的權(quán)
	int from;      //from是邊的始點(diǎn)
	int to;        //to是邊的終點(diǎn)
	Edge()  {		// 構(gòu)造函數(shù)
		from = -1;  to = -1;  weight = 0;
	}							
	Edge(int f,int t,int w)   { // 構(gòu)造函數(shù)
		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;             //圖的頂點(diǎn)的個(gè)數(shù)
	int numEdge;				//圖的邊的數(shù)目
	int *Mark;					/*Mark指針指向保存有圖的頂點(diǎn)的標(biāo)志位的數(shù)組,標(biāo)志位用來標(biāo)記某頂點(diǎn)是否被訪問過*/
	int *Indegree;				//Indegree指針指向保存有圖的頂點(diǎn)的入度的數(shù)組
	Graph(int numVert)  {		//構(gòu)造函數(shù)
		numVertex = numVert;      //確定圖的頂點(diǎn)的個(gè)數(shù)
		numEdge = 0;				//確定圖的邊的數(shù)目
		Indegree = new int[numVertex]; /*為保存圖的頂點(diǎn)的入度申請(qǐng)數(shù)組,Indegree為數(shù)組指針*/
		Mark = new int[numVertex];	 /*為圖的頂點(diǎn)的標(biāo)志位申請(qǐng)數(shù)組,Mark為數(shù)組指針*/
		
		for (int i = 0; i < numVertex; i ++)  {	/*確定圖的頂點(diǎn)的標(biāo)志位和入度,即所有頂點(diǎn)的標(biāo)志位初始化為未被訪問過,入度初始化為0*/
			Mark[i] = UNVISITED;
			Indegree[i] = 0;
		}
	}
	
	~Graph() {				//析構(gòu)函數(shù)
		delete [] Mark;
		delete [] Indegree;
	}
	
	virtual Edge FirstEdge(int oneVertex) {	// 返回與頂點(diǎn)oneVertex相關(guān)聯(lián)的第一條邊
		Edge myEdge;
		myEdge.from = oneVertex; 
		myEdge.to = -1;
		return myEdge;
	}
	
	virtual Edge NextEdge(Edge preEdge) {      // 返回與邊PreEdge有相同關(guān)聯(lián)頂點(diǎn)的下一條邊
		return preEdge;
	}

	int VerticesNum() {		//返回圖的頂點(diǎn)個(gè)數(shù)
		return numVertex;
	}
	
	int EdgesNum() {			//返回圖的邊數(shù)
		return numEdge;
	}
	
	int FromVertex(Edge oneEdge) {  // 返回oneEdge的始點(diǎn)
		return oneEdge.from;
	}
	
	int ToVertex(Edge oneEdge) {	// 返回oneEdge的終點(diǎn)
		return oneEdge.to;
	}
	
	int Weight(Edge oneEdge) {		// 返回oneEdge的權(quán)值
		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;
};