// *************************************************
// *                                               *
// *  graphalgs.C                                  *
// *                                               *
// *  Headers for functions that operate publicly  *
// *   on the graph class.                         * 
// *                                               *
// *  Written 10 Nov 1998 by Jason Zych            *
// *    MP9 functions added by Lilian Fernandes    *
// *                                               *
// *************************************************


#include "graphalgs.h"
#include "queueal.h"

// Print
//    - parameters : dirGraph - graph to print
//    - prints out graph information
template <class Vtype, class Etype>
void Print(InfoGraph<Vtype, Etype>& dirGraph)
{

   Vertex v1; 
   Edge e1; 
  
   v1 = dirGraph.FirstVertex();
   while (!dirGraph.IsNil(v1)) 
   {
      cout << "Now processing Vertex " << dirGraph.VertexInfo(v1);
      cout << endl << endl;

      // printing departed edges
      e1 = dirGraph.FirstDepartEdge(v1); 
      while (!dirGraph.IsNil(e1))
      {
         cout << "   Departing Edge:" << endl; 
         cout << "      Source: " << dirGraph.VertexInfo(dirGraph.Source(e1));
         cout << endl;
         cout << "      Target: " << dirGraph.VertexInfo(dirGraph.Target(e1));
         cout << endl;
         cout << "      EdgeInfo: " << dirGraph.EdgeInfo(e1) << endl; 
         e1 = dirGraph.NextDepartEdge(e1); 
      }       
      cout << endl; 
    
 
      // printing entering edges
      e1 = dirGraph.FirstEnterEdge(v1); 
      while (!dirGraph.IsNil(e1))
      {
         cout << "   Entering Edge:" << endl;          
         cout << "      Source: " << dirGraph.VertexInfo(dirGraph.Source(e1));
         cout << endl;
         cout << "      Target: " << dirGraph.VertexInfo(dirGraph.Target(e1));
         cout << endl;
         cout << "      EdgeInfo: " << dirGraph.EdgeInfo(e1) << endl; 
         e1 = dirGraph.NextEnterEdge(e1); 
      }
      cout << endl; 
      
      v1 = dirGraph.NextVertex(v1); 
   }

} 


// BFS
//    - parameters : theGraph - a graph to traverse 
//                 : sourceVert - the vertex at which to start
//                                   the BFS
//    - prints graph information in BFS order
void BFS(InfoGraph<int, int>& dirGraph, Vertex& sourceVert)
{
  Queue<Vertex> BFSQueue;
  Vertex currVertex,neighbour;
  Edge e;

  /* We haven't visited any vertex yet */
  dirGraph.ClearVertexMarks();

  /* Mark the first vertex and enqueue it */
  dirGraph.SetVertexMark(sourceVert,1);
  BFSQueue.Enqueue(sourceVert);

  /* Now process all vertices in the queue */
  while(!BFSQueue.Is_Empty())
  {
    currVertex = BFSQueue.Dequeue();
    cout<<dirGraph.VertexInfo(currVertex)<<endl;

    /* Enqueue all its unmarked neighbours */
    e = dirGraph.FirstDepartEdge(currVertex); 
    while (!dirGraph.IsNil(e))
    {
      neighbour = dirGraph.Target(e);
      if(dirGraph.GetVertexMark(neighbour) != 1)
      {
        dirGraph.SetVertexMark(neighbour,1);
        BFSQueue.Enqueue(neighbour);
      }
      e = dirGraph.NextDepartEdge(e); 
    }       
  } 
}


// DFS
//    - parameters : theGraph - a graph to traverse
//                 : sourceVert - the vertex at which to start
//    - prints graph information in DFS order
void DFS(InfoGraph<int, int>& dirGraph, Vertex& sourceVert)
{
  /* We haven't visited any vertex yet */
  dirGraph.ClearVertexMarks();

  RecursiveDFS(dirGraph,sourceVert);
}



// RecursiveDFS
//    - parameters : theGraph - a graph to traverse
//                 : currVert - the current vertex to run DFS on
//    - prints graph information in DFS order
void RecursiveDFS(InfoGraph<int, int>& dirGraph, Vertex& currVertex)
{
  Vertex neighbour;
  Edge e;

  dirGraph.SetVertexMark(currVertex,1);
  cout<<dirGraph.VertexInfo(currVertex)<<endl;

  /* For each neighbour of currVertex do */
  e = dirGraph.FirstDepartEdge(currVertex); 
  while (!dirGraph.IsNil(e))
  {
    neighbour = dirGraph.Target(e);
    if(dirGraph.GetVertexMark(neighbour) != 1)
      RecursiveDFS(dirGraph,neighbour);
    e = dirGraph.NextDepartEdge(e); 
  }     
}



