//---------------------------------------------------------------------------
#ifndef GRAPH_TRAV_H_
#define GRAPH_TRAV_H_
//---------------------------------------------------------------------------
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <list>
#include <algorithm>
#include "Graph_Bas.h" 

template <class T>
class graph_traver: public graph_bas<T>
{
    public:
       // 不帶權值圖構造器
       graph_traver(graphInfo<T> ginfo): graph_bas<T>(ginfo){ }
       // 先深遍歷搜索
       list<T>& dfs(const T& beginVertex);
       // 先廣遍歷搜索
       list<T>& bfs(const T& beginVertex);
       // 計算無向圖連通分量
       void component();
       // 計算有向圖強連通分量
       void strong_component();
       // 判斷圖連通性
       bool isconnected();
       bool findVertex(list<T>& L,const T &vertex) {
       	  if(find(L.begin(),L.end(),vertex) != L.end())
	         return true;
	      else
	         return false;
       }
//    private:
    protected:
       bool pathconnect(T u,T w) {
          list<T> L = dfs(u);
          if(find(L.begin(),L.end(),w) != L.end())
             return 1;
          else
             return 0;
       }
};

template <class T>
list<T>& graph_traver<T>::dfs(const T& beginVertex)
{
   stack<T> S;
   list<T> *L,adjL;                   // L必須是一個指針，以便返回到引用
   list<T>::iterator itr;
   L = new list<T>;                   // 分配內存
   S.push(beginVertex);               // 頂點入棧
   while(!S.empty()) {
      T vertex = S.top();             // 取棧頂元素
      S.pop();                        // 頂點出棧
      if(! findVertex(*L, vertex)) {
         (*L).push_back(vertex);
         adjL = AdjLists[GetVertexPos(vertex)];
         for(itr=adjL.begin(); itr!=adjL.end(); ++itr)
            if(! findVertex(*L, *itr))
               S.push(*itr);
      }
   }
   return *L;                         // 返回到一個引用
}

template <class T>
list<T>& graph_traver<T>::bfs(const T& beginVertex)
{
   queue<T> Q;                        // 聲明一個隊列
   list<T> *L,adjL;
   list<T>::reverse_iterator itrev;
   T vertex;
   L = new list<T>;
   Q.push(beginVertex);               // 起始頂點入隊
   while(!Q.empty()) {
      vertex = Q.front();
      Q.pop();                        // 出隊
      if(!findVertex(*L,vertex)) {
         (*L).push_back(vertex);
	     adjL = AdjLists[GetVertexPos(vertex)];
         for(itrev=adjL.rbegin(); itrev!=adjL.rend(); itrev++)
	        if(!findVertex(*L,*itrev))
	           Q.push(*itrev);        // 新的鄰接頂點入隊
      }
   }
   return *L;
}

template <class T>
void graph_traver<T>::component()
{
   int count=0;
   vector<int> visited(GetnumVertices());
   list<T> L,vList=GetvertexList();
   list<T>::const_iterator it,itr;
   for(it=vList.begin(); it!=vList.end(); it++) {
      if (!visited[GetVertexPos(*it)]) {
         count++;
         L = bfs(*it);
         print_List("無向圖連通分量：", L);
         for (itr=L.begin(); itr!=L.end(); itr++)
           visited[GetVertexPos(*itr)]=1;
      }
   }
   cout << "連通分量個數＝" << count << endl;
}

template <class T>
void graph_traver<T>::strong_component()
{
   int count=0;
   list<T> L,vList=GetvertexList(),markedList,scList;
   list<T>::const_iterator it,itr;
   for(it=vList.begin(); it!=vList.end(); it++) {
      if(find(markedList.begin(),markedList.end(),*it) == markedList.end()) {
         count++;
         scList.clear();
         L = bfs(*it);
         itr=L.begin();
         while(itr!=L.end()) {
           if(pathconnect(*itr,*it)) {
              scList.push_back(*itr);
              markedList.push_back(*itr);
           }
           itr++;
         }
         print_List("有向圖強連通分量: ", scList);
      }
   }
   cout << "強連通分量個數＝" << count << endl;
}

// 判斷圖連通性
template <class T>
bool graph_traver<T>::isconnected()
{
   list<T> vList=GetvertexList(), L;
   list<T>::const_iterator it;
   for(it=vList.begin(); it!=vList.end(); it++) {
     L = bfs(*it);
     if(L.size()<vList.size())
        return false;
   }
   return true;
}
#endif