//--- Digraph
//===========

#include <list>
#include <vector>
#include <queue>
#include <iostream>
#include <fstream>
using namespace std;

template <class DataType>
class Digraph
{
// Operations
public:
/* Retrieve data value in a given vertex.
 *
 * Receive:  Digraph containing this function (implicitly)
 *           Number k of a vertex
 * Return:   Data value stored in vertex #k
 ***********************************************************/
DataType Data(int k) const;

/* Input operator
 *
 * Receive:       ifstream inFile and digraph (implicitly)
 * Input(inFile): The lines in inFilemust be organized so  
 *                that the data item in a vertex is on one 
 *                line and on the next line is the number of 
 *                vertices adjacent to it followed by a list 
 *                of the numbers of these adjacent vertices.
 * Pass back:     modified ifstream inFile
 ***********************************************************/
void Read(ifstream & inFile);

/* Output operator
 *
 * Receive:   ostream out and digraph (implicitly).
 * Output:    Each vertex's data value and its 
 *             adjacency list
 * Pass back: modified ostream out
 **********************************************************/
void Print(ostream & out);

/* Depth first search of digraph, starting at vertex start.
 *
 * Receive:   Digraph containing this function (implicitly)
 *            Vector unvisited with unvisited[i] = true if 
 *              vertex i has not yet been visited, and
 *              false otherwise
 * Pass back: Updated list unvisited
 * Output:    Depends on the type of processing done when
 *            a node is visited
 *********************************************************/
void DepthFirstSearchAux(int start, vector<bool> & unvisited);

void DepthFirstSearch(int start);

/* Find a shortest path in the digraph from vertex start to
 * vertex destionation.
 *
 *  Receive: Digraph d, start and destination vertices
 *  Return:  A vector of vertices along this shortest path
 **********************************************************/
vector<int> ShortestPath(int start, int destination);


private:
// "Head nodes" of adjacency lists
  struct VertexInfo
  {
    DataType data;
    list<int> adjacencyList;
  };

// Data Members
  vector<VertexInfo> v;
}; // end of class declaration


//--- Definition of Data()
template <class DataType>
inline DataType Digraph<DataType>::Data(int k) const
{ return v[k].data; }

//--- Definition of Read()
template <class DataType>
void Digraph<DataType>::Read(ifstream & inFile)
{
  Digraph<DataType>::VertexInfo vi;
  int n,           // number of vertices adjacent to some vertex
      vertex;      // the number of a vertex

  v.push_back(vi); // garbage 0-th value so indices start with 1,
                   // as is 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);
  }
}
 
//-- Definition of Print();
template <class 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;
  }
}  

//-- Definitions of DepthFirstSearch() and DepthFirstSearchAux()
template <class DataType>
void Digraph<DataType>
::DepthFirstSearchAux(int start, vector<bool> & unvisited)
{
  // Add statements 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 <class DataType>
void Digraph<DataType>::DepthFirstSearch(int start)
{
  vector<bool> unvisited(v.size(), true);
  DepthFirstSearchAux(start, unvisited);
}


//--- Definition of ShortestPath()
template<class 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 distances from start as we go.

  distLabel[start] = 0;
  int distance = 0,             // distance from start vertex
      vertex;                   // a vertex
  queue<int> vertexQueue;       // queue of vertices
  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;
}