// Aren Jansen
// HW7 DFS Solution Code
// depth first search example in a directed graph

#include <iostream>
#include <cstring>
using namespace std;

class node;
typedef node *NP;
class edge;
typedef edge *EP;
void dfs( NP start );
ostream& operator << ( ostream & os, node & n );

class node{    // nodes for a graph
 public:
  static int time; // count steps in dfs
  char* name;
  bool visited;    // four items used in dfs
  int discovered;
  int finished;
  NP prev;// item before this one in dfs
  EP adjList;// list of nodes adjacent to *this
  node( char n[] )
     : visited(false), adjList(0), 
       discovered(0), finished(0), prev(0)
  { name = new char[strlen(n)+1];
    strcpy(name,n);
  }
  ~node(){ delete[] name; }
  void edge2( NP to );
};

int node::time = 0;

class edge{
 public:
  const NP terminus;
  EP next;
  edge( const NP to, EP nn  )
   : terminus( to ), next(nn){}
};

void node::edge2( NP to )
{ // insert a new edge in list
   EP newedge = new edge( to, adjList );
   adjList = newedge;
}


void dfs( NP start )
{// depth first search of the nodes reachable from start
   start->visited = true;
   node::time++;
   start->discovered = node::time;
   
   for ( EP iter = start->adjList; iter; iter = iter->next )
   {
      NP nextNode = iter->terminus;
      if ( !nextNode->visited )
      {
	 nextNode->prev = start;
	 dfs(nextNode);
      }
   }
   node::time++;
   start->finished = node::time;
   cout << *start;
}

ostream& operator << ( ostream & os, node & n )
{
  cout << "Node " << n.name << " was discoved at time "
       << n.discovered << " and finished at "
       << n.finished << ".\n";
}

int main()
{// test of dfs code

/*
        Test Graph

         4<-----5
         |      ^
         |      |
         V      V
         0----->1<---->7----->8
         |      |      ^
         |      |      |
         V      V      V
         2<---->3----->9<---->6
*/

   NP np[10];
   np[0] = new node("node 0");
   np[1] = new node("node 1");
   np[2] = new node("node 2");
   np[3] = new node("node 3");
   np[4] = new node("node 4");
   np[5] = new node("node 5");
   np[6] = new node("node 6");
   np[7] = new node("node 7");
   np[8] = new node("node 8");
   np[9] = new node("node 9");

   np[0]->edge2( np[1] );    // 0->1
   np[0]->edge2( np[2] );    // 0->2
   np[1]->edge2( np[3] );    // 1->3
   np[1]->edge2( np[7] );    // 1->7
   np[1]->edge2( np[5] );    // 1->5
   np[2]->edge2( np[3] );    // 2->3
   np[3]->edge2( np[9] );    // 3->9
   np[3]->edge2( np[2] );    // 3->2
   np[4]->edge2( np[0] );    // 4->0
   np[5]->edge2( np[4] );    // 5->4
   np[5]->edge2( np[1] );    // 5->1
   np[6]->edge2( np[9] );    // 6->9
   np[7]->edge2( np[8] );    // 7->8
   np[9]->edge2( np[6] );    // 9->6
   np[9]->edge2( np[7] );    // 9->7

   cout << "Starting from node 0 we get\n";
   node::time = 0;
   dfs( np[0] );

   for( int i=0; i<10; i++ )
      np[i]->visited = false;

   cout << "\nStarting from node 6 we get\n";
   node::time = 0;
   dfs( np[6] );

   np[7]->edge2( np[1] );    // 7->1
   for( int i=0; i<10; i++ )
      np[i]->visited = false;

   cout << "\nStarting from node 6 after inserting 7->1 we get\n";
   node::time = 0;
   dfs( np[6] );


  return 0;
}