// file network.h
//抽象基類Network
#ifndef Network_
#define Network_

#include "lqueue.h"
#include "lstack.h"

class Network {
   public:
      virtual int Begin(int i) = 0;
      virtual int NextVertex(int i) = 0;
      virtual void InitializePos() = 0;
      virtual void DeactivatePos() = 0;//以上為四個遍歷函數(shù)，純虛，不同圖不同實現(xiàn)
      virtual int Vertices() const = 0;//頂點數(shù)目，也是純虛實現(xiàn)
      virtual int Edges() const = 0;
      void BFS(int v, int reach[], int label);//寬度優(yōu)先搜索
      void DFS(int v, int reach[], int label);//深度優(yōu)先搜索
      bool FindPath(int v, int w, int &length, int path[]);//尋找路徑
      bool Topological(int v[]);
   private:
      void dfs(int v, int reach[], int label);//實質(zhì)實現(xiàn)深度優(yōu)先搜索功能的私有成員函數(shù)
      bool findPath(int v, int w, int &length,int path[], int reach[]);//實際實現(xiàn)尋找路徑的函數(shù)
};

void Network::BFS(int v, int reach[], int label)
{//寬度優(yōu)先搜索
   LinkedQueue<int> Q;
   InitializePos(); // 初始化圖遍歷器數(shù)組，調(diào)用純虛InitializePos函數(shù)，不同的類對象就有不同實現(xiàn)了
   reach[v] = label;//reach用來標記已到達的頂點，=label證明已到達頂點v了
   Q.Add(v);
   while (!Q.IsEmpty())
   {
	   int w;
	   Q.Delete(w);  //獲得一個以標記的頂點
	   int u = Begin(w);//令u為鄰接于頂點w的第一個頂點
	   while (u) {//訪問w的鄰接頂點
         if (!reach[u]) {//一個未曾到達的頂點
            Q.Add(u);
            reach[u] = label;} //標記
         u = NextVertex(w); //下一個與w鄰接的頂點
         }
      }
   DeactivatePos(); //釋放遍歷器數(shù)組
}

void Network::DFS(int v, int reach[], int label)
{//深度優(yōu)先搜索
   InitializePos(); //初始化圖遍歷器數(shù)組
   dfs(v, reach, label); //執(zhí)行dfs
   DeactivatePos(); //釋放圖遍歷器數(shù)組
}

void Network::dfs(int v, int reach[], int label)
{//實質(zhì)實現(xiàn)深度優(yōu)先搜索功能的代碼，遞歸實現(xiàn)的
   reach[v] = label;
   int u = Begin(v);
   while (u)
   {//u鄰接至v
	   if (!reach[u])
		   dfs(u, reach, label);
	   u = NextVertex(v);
   }
}

bool Network::FindPath(int v, int w, int &length, int path[])
{// 尋找一條從v到w的路徑，返回路徑的長度，并將路徑存入數(shù)組path[0:length]
 // Return false if there is no path.

   //路徑中的第一個頂點總是v
   path[0] = v;
   length = 0;  // 當前路徑長度
   if (v == w) return true;

   // 為路徑的遞歸搜索進行初始化
   int  n = Vertices();//n個頂點
   InitializePos();  //遍歷器
   int *reach = new int [n+1];
   for (int i = 1; i <= n; i++)
      reach[i] = 0;//都初始化為沒有走過
   
   //搜索
   bool x = findPath(v, w, length, path, reach);

   DeactivatePos();//釋放遍歷器空間
   delete [] reach;//釋放臨時標記數(shù)組reach
   return x;
}

bool Network::findPath(int v, int w, int &length,int path[], int reach[])
{//實質(zhì)搜索路徑的函數(shù)，其中 v!=w
 // Performs a depth-first search for a path to w.
   reach[v] = 1;
   int u = Begin(v);
   while (u)
   {
	   if (!reach[u])
	   {
		   length++;
		   path[length] = u; //將頂點u加入path
		   if (u == w) return true;
		   if (findPath(u, w, length, path, reach))
			   return true;
		   //否則不存在從u到w的路徑
		   length--; //length要復(fù)位，也即不記錄u
	   }
	   u = NextVertex(v);
   }
   return false;
}

bool Network::Topological(int v[])
{// 計算有向圖的拓撲序列
 // 如果找到了一個拓撲序列，則返回true，此時在v[0:n-1]中記錄了拓撲序列
 // 如果不存在，則返回false

   int n = Vertices();
   
   // 計算入度
   int *InDegree = new int [n+1];
   InitializePos(); // 圖遍歷器數(shù)組
   for (int i = 1; i <= n; i++) //先都初始化為0
      InDegree[i] = 0;
   for (i = 1; i <= n; i++)
   {// 從i出發(fā)的邊，這個循環(huán)計算圖初始的入度數(shù)組
      int u = Begin(i);
      while (u)
	  {
		  InDegree[u]++;
		  u = NextVertex(i);
	  }
   }
   
   //把入度為0的頂點壓入堆棧
   LinkedStack<int> S;
   for (i = 1; i <= n; i++)
	   if (!InDegree[i]) S.Add(i);
   
   // 產(chǎn)生拓撲順序
   i = 0;  // 跟蹤數(shù)組v
   while (!S.IsEmpty()) {// select from stack
      int w;             // next vertex
      S.Delete(w);
      v[i++] = w;
      int u = Begin(w);
      while (u)
	  {//更新每個與w相鄰的入度，-1
		  InDegree[u]--;
		  if (!InDegree[u]) S.Add(u);//更新過程中，若某個的入度變?yōu)?了，則壓入棧中
		  u = NextVertex(w);
	  }
   }
   
   DeactivatePos();
   delete [] InDegree;
   return (i == n);
}

#endif;