//Digraph Class Template

#include <list>
#include <vector>
#include <queue>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>

using namespace std;

template <typename DataType>

class Digraph
{
      //operation
      public: 
      DataType Data(int k) const; //number k of vertex,data value stored in vertex #k
      
      void Read(ifstream & inFile);  //input operator
      void Print(ostream & out);     //output operator
      void DepthFirstSearchAux(int start, vector <bool> & unvisited);     //depth firstof diagraph, starting at vertex start.
      void DepthFirstSearch(int start);
      //find a shortest path in the diagraph from vertex start to vertex destination 
      vector<int> ShortestPath(int start, int destination);   
      
      private:
              //head nodes of adjacency list
              class VertexInfo
              {     
                    public:
                           DataType data;
                           list<int> adjacencyList;
              };
      //data members
      vector<VertexInfo> v;
}; 
              
//definition of Data()
template <typename DataType>
inline DataType Digraph<DataType>::Data(int k) const
{
  return v[k].data;
}

//definition of Read()
template <typename DataType>
void Digraph<DataType>::Read(ifstream & inFile)
{
     VertexInfo vi;  //VertexInfo vi;
     int n,            //number of vertices adjacent to some vertex
         vertex;      //the nuber of vertex
                   
     v.push_back(vi); //garbage 0-th value so indices start with 1,as it customary
                   
     for(;;)
     {
            inFile>>vi.data;
            if(inFile.eof()) break;
            inFile>>n;
                          
            list<int> adjList;     //construct empty list
            for (int i =1; i <=n; i++)
            {
                inFile>>vertex;
                adjList.push_back(vertex);
            }
            vi.adjacencyList=adjList;
            v.push_back(vi);
     }
}
              
template <typename DataType>
void Digraph<DataType>::Print(ostream & out)
{
     out<<"Adjacency-List Representation: \n";
     for (int i=1; i < v.size(); i++)
     {
         out<<i<<":"<< v[i].data<<"--";
         for(list<int>::iterator it = v[i].adjacencyList.begin();
                                 it != v[i].adjacencyList.end(); it++)
           out<<*it<<" ";
         out<<endl;
     } 
}
              
//definition of DepthFirstSearch() and DepthFirstSearchAux()
template <typename DataType>
void Digraph<DataType>
::DepthFirstSearchAux(int start, vector<bool> & unvisited)
{
      //add statement here to process v[start].data
      cout<<v[start].data<<endl;
      unvisited[start] = false;
                    
      //traverse its adjacency list,performing depth-first searches from each unvisited vertex in it.
      for (list<int>::iterator
          it = v[start].adjacencyList.begin();
          it != v[start].adjacencyList.end(); it++)
                    
      //check if current vertex has been visited
      if (unvisited[*it])
         //start DFS from new node
         DepthFirstSearchAux(*it, unvisited);
}
              
template <typename DataType>
void Digraph<DataType>::DepthFirstSearch(int start)
{
     vector<bool> unvisited(v.size(), true);
     DepthFirstSearchAux(start, unvisited);
}
              
//definition of ShortestPath()
template<typename DataType>
vector<int> Digraph<DataType>::ShortestPath(int start, int destination)
{
     int n = v.size();               //number of vertices (#ed from 1)
     vector<int> distLabel(n, -1),   //distance labels for vertices, all marked as unvisited (-1)
     predLabel(n);                   //predecessor labels for vertices
                                      
     //perform breadth first search from Start to find destination,
     //labeling vertices with distance from start as we go.
     distLabel[start] = 0;
     int distance = 0,
         vertex;
         queue<int> vertexQueue;
         vertexQueue.push(start);
              
         while (distLabel[destination] < 0 && !vertexQueue.empty())
         {
               vertex = vertexQueue.front();
               vertexQueue.pop();
                    
               if (distLabel[vertex] > distance)
               distance ++;
                       
               for (list<int>::iterator it = v[vertex].adjacencyList.begin();
                                             it != v[vertex].adjacencyList.end(); it++)
               if (distLabel[*it]<0)
               { 
                 distLabel[*it] = distance+1;
                 predLabel[*it] = vertex;
                 vertexQueue.push(*it);
               }
         }
         distance++;
              
     //now reconstruct the shortest path if there is one 
     vector<int> path(distance+1);
     if(distLabel[destination]< 0)
     cout<< "Destination not reachable from start vertex\n";
     else
     {
         path[distance] = destination;
                  
         for (int k = distance-1; k >= 0; k--)
         path[k] = predLabel[path[k+1]];
     }
     return path;
}


//The program 

int main()
{
    
    cout<<"Enter network file: ";
    string networkFile;
    cin>>networkFile;
    
    ifstream inFile(networkFile.data());
    if (!inFile.is_open())
    {
       cerr << "***Cannot Open file " << networkFile<<" ***\n";
       exit(-1);
    }
    
    Digraph<string> d;
    d.Read(inFile);
    cout<<"The Digraph's " ;
    d.Print (cout);
    cout << endl;
    
    int start, destination;
    char response;
    
    do
    {
         cout<<"Number of Start node? ";
         cin>>start;
         cout<<"Number of destination node? ";
         cin>>destination;
         
         vector<int> path = d.ShortestPath(start,destination);
         cout<<"Shortest path is: \n";
         
         for (int k=0; k<path.size(); k++)
         {
             cout<<setw(3)<<path[k]<<' '<<d.Data(path[k])<<endl;
             cout<<"    |\n"
                   "    V\n";
         }
         cout<<setw(3)<<destination<<' '
             <<d.Data(destination)<<endl;
         cout<<"More (Y or N)? ";
         cin>> response;
    }
    while (response == 'y' || response == 'Y');
}

            vi.adjacencyList=adjList;
            v.push_back(vi);