///////////////////////////////////////////////////////////////////////
//
//  stl_types.h   --  STL type aliases. Change the for Metrowerks.
//
///////////////////////////////////////////////////////////////////////

#ifndef __STL_TYPES_H__
#define __STL_TYPES_H__

#include <limits.h>    //INT_MAX

#include <list>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>   //find
#include <map>
#include <utility>     //pair

typedef int                 vertex;    //a vertex is just an int, so far 
                                           
//vertex ids serve as indices into the vector of neighbor lists,
//therefore they are expected to range from 0 to num_vertices 
                                           
//a vertex can be made to contain its names, list of neighbors etc.
//to remain compatible with the code below, struct vertex will have
//to contain a cast to int, its vertex. See, for instance, the code
//at the end of this file.

typedef vector<int>         vector_of_int; 

typedef list< vertex >      list_of_vertex;     //list of vertices 
                                       
typedef vector< string >    vector_of_string;    //vector of vertex names

typedef stack< vertex >     stack_of_vertex;        //needed for algorithms
typedef queue< vertex >     queue_of_vertex;        
typedef vector< bool >      vector_of_bool;  

typedef map< pair<vertex,vertex>, int >  map_of_weights;  //just that, for
                                                     //weighted graphs 

const int INFTY = INT_MAX;  //for dijkstra's algorithm

#endif // __STL_TYPES_H__

/////////////////////////////////////////////////////////////////////// 
//
//  graph-elist.h   --   Edge list representation of a graph
// 
///////////////////////////////////////////////////////////////////////

#ifndef __GRAPH_ELIST_H__
#define __GRAPH_ELIST_H__

#include <iostream.h>
#include <string>
#include <stdlib.h>
#include <fstream.h>

// all STL stuff included here
#include "stl_types.h"

// *********** Unweighted graph by edge list ***********************
  
class graph {
protected:
  int                 num_v;       //number of vertices in graph
  list_of_vertex*     edges;       //edge list -- see note ***           
  vector_of_string    names;       //vertex names
public:
  graph(); 
  graph( char* filename );  //read edge list from a file
  ~graph();
  bool are_connected( vertex x, vertex y ) const;
  int size() const;
  const string&  name     ( vertex v ) const;   // get vertex name 
  const list_of_vertex& neighbors( vertex v ) const;   // and neighbor list 
private:
  graph( const graph & ){}  //let's ensure graph is never copied implicitly
};                            

//note ***: There are two ways to have an array of size unknown at compile
//time. You can have a pointer to the type of the thing you want to store
//in your array and use new [] later to hook up the dynamically allocated
//memory to your class; in this case you have to be careful with copy
//contructors and default operator=. Or you can declare a vector
//and resize it later. Mixing both styles is probably *not* a good idea.
//I should have had a vector of lists of neighbors.

//Here every little function is removed from class header -- does header
//readability improve so much as to warrant some additional typing?

               graph::graph( ) : num_v(0), edges(NULL) {} //empty graph
               graph::~graph(){ delete[] edges; }
int            graph::size() const { return num_v; }          
const string&  graph::name    ( vertex v ) const { return names[v]; }
const list_of_vertex& graph::neighbors( vertex v ) const { return edges[v]; }   
// Read an edge list from a file and create a graph
//expected format: 
// COMMENT LINE (discarded)
// num_v 
// v1 name_1 num_neighb_1 v11 v12 v13 ...
// v2 name_2 num_neighb_1 v21 v22 v23 ...

graph::graph( char* filename ){
  if( ! filename ) 
    { cout << "Filename needed for graph source.\n"; exit(-1); }
  ifstream infile( filename );
  if( !infile ) 
    { cout << "Failed to open file.\n"; exit(-1); }

  string dummy; getline( infile, dummy );   //discard the first line

  infile >> num_v;
  
  edges = new list_of_vertex[ num_v ];   //array of list_of_vertex
  names.resize( num_v, "" );             //resize, padding with ""
  
  int num_neighb;
  vertex id, v;
  for( int i=0; i<num_v; i++ ){
    infile >> id;
    infile >> names[id] >> num_neighb;
    for( int j=0; j<num_neighb; j++ ){
      infile >> v;
      edges[id].push_back( v );
    }
  }
}  

// check if x --> y edge exists
bool graph::are_connected( vertex x, vertex y ) const {
  list_of_vertex& lst = edges[x];  //reference to neighbor list of vertex x
  
  //find( iterator start, iterator finish, value ) is an STL generic algorithm
  //that takes the begin and end iterators of a container (list, vector etc.) 
  //and a value to look for in that container. It returns either an iterator
  //to the first occurance of the value in container or end() iterator if value
  //was not found
  
  return find( lst.begin(), lst.end(), y ) != lst.end() ;    
}  

// ******************* Weighted graph ************************************

// Inherited from graph. The storage is the same, except that now some
// structure for storing weights is needed. A weight can be added to
// a vertex on list_of_vertex, so that for each point  v0  we have a list of
// its neighbors now with weights: { (v1, weaght1),  (v2, weight2), ... }.

// Let us try another approach - have a map from pairs 
//                    (vertex, vertex) --> weight.
// This will not require modifying (unweighted) graph's data (so that we 
// can use inheritance to share code). This is 
// reasonable only if the graph has relatively few edges, otherwise a 
// weight matrix is more efficient and more natural.

// A note on inheritance: the new constructor overrides that of graph.
// If graph contained any functions that had to have a different meaning
// for weighted_graph, they could have been declared as *virtual*, and so
// could the destructor ~graph(). To find out why, see Stroustroup on
// Virtual Functions. 

class weighted_graph : public graph {  //inherit neighbor lists etc.
protected:
  map_of_weights weights;
public:
  weighted_graph( char* filename ); 
  int weight( vertex i, vertex j );
private:
  weighted_graph( const weighted_graph& ){}; //no one calls c.c. on this class!
};

int weighted_graph::weight( vertex i, vertex j ) {
  const pair<int,int> p (i,j);
  return weights[ make_pair(i,j) ];   //this is an STL map operation. See note.
}

// Note: Since looking up the weight of an edge doesn't imply changing
// any of the graph's data, it would seem reasonable to declare the
// above function as  int weight(vertex, vertex) const;  Unfortunately,
// operator[] of an STL map doesn't just do a lookup on a key in [..], 
// but also *inserts a default value* into the map if the key wasn't
// found. This is done so that values can be inserted into the map
// on new keys just by saying  weights[ make_pair(i,j) ] = new_value_at_i_j;
// Thus operator[] actually always calls map::insert method, so the map
// will be modified frequently on lookup. See map.h  --end note

// Read edge list from file, create graph -- almost the same as graph::graph
// COMMENT LINE (discarded)
// num_v 
// v1 name_1 num_neighb_1 v11 weight11 v12 weight12 ...
// v2 name_2 num_neighb_1 v21 weight21 v22 weight22 ...

weighted_graph::weighted_graph( char* filename ){
  if( ! filename ) 
    { cout << "Filename needed for graph source.\n"; exit(-1); }
  ifstream infile( filename );
  if( !infile ) 
    { cout << "Failed to open file.\n"; exit(-1); }

  string dummy; getline( infile, dummy );   //discard the first line

  infile >> num_v;
  
  edges = new list_of_vertex[ num_v ];   //array of list_of_vertex
  names.resize( num_v, "" );             //resize, padding with ""
  
  int num_neighb, wght;
  int  id, v;
  for( int i=0; i<num_v; i++ ){
    infile >> id;

    infile >> names[id] >> num_neighb;
    for( int j=0; j<num_neighb; j++ ){
      infile >> v >> wght;
      edges[id].push_back( v );
      weights[ make_pair(id,v) ] = wght; //make a new key and insert a new
                                         //weight into the map. See note above.
    }
  }
}  

// struct vertex {
//   int id_;                                           //id of vertex
//   string name_;                                      //name of vertex
//   vertex() : id_(-1), name_("") {}                   //unset vertex
//   vertex( int n, string& s ) : id_(n), name_(s) {}
//   operator int() { return id_; }   //casts a vertex into its id number.
//                                    //this will allow us to use a vertex
//                                    //wherever a vertex is required as index
//                                    //into a vector or an entry of a matrix
//   string name(){ return name_; }
//   int    id(){ return id_; }
// };
#endif // __GRAPH_ELIST_H__

/////////////////////////////////////////////////////////////////////// 
//
//  elist-alg.h   --   Algorithms that depend on edge lists
// 
///////////////////////////////////////////////////////////////////////

#ifndef __ELIST_ALG_H__
#define __ELIST_ALG_H__

#include <iostream.h>
#include <string>
#include <stdlib.h>
#include <fstream.h>

// STL stuff included here
#include "stl_types.h"
#include "graph-elist.h"

int min(int x, int y) { return  x<y ? x : y; }  

// ***************** Helpers ***********************************************

void print_weighted_graph( weighted_graph& gr ){
  for( int i=0; i < gr.size(); i++) 
    for( int j=0; j < gr.size(); j++)
      if( gr.are_connected(i,j) ) 
	cout << i << " --(" << gr.weight(i,j)  
	     << ")--> " << j <<"\n";  
}

//the above would be taking const weighted_graph& gr as an argument, but
//for the map lookup occuring in weight(i,j). See note above.

// a generic helper function to 'push' all the elements from one STL contained
// into another STL container/adapter (which has a 'push' method, of course).
// this can also be done with generic methods such as for_each

template< class Receiver, class Source >
void push_all( Receiver& R, Source& S ){
  typename Source::iterator p = S.begin();  
  typename Source::iterator e = S.end();      
  while( p != e ) R.push( *p++ ); 
}     

// ****************** Algorithms depending on edge list ********************

void   depth_first_traversal ( const graph& gr , vertex origin );
void breadth_first_traversal ( const graph& gr , vertex origin );
void dijkstra                ( weighted_graph& gr, vertex origin );   

// ************************ Traversals ***********************************

// depth-first traversal can be easily implemented recursively, as follows:
//   1. provertexe a way of marking vertices -- visited or not yet visited
//   2. for each vertex:
//        a) check if it's marked. If yes, return immediately. Otherwise:
//        b) mark it (and process/print it)
//        c) for every one of its neighbors (from nhbrs list) call
//           the very same procedure.
// Since on every step a vertex is either found marked or marked if
// unmarked before, the algorithm will terminate (after all vertices 
// connected to the origin are marked)  
               
// This is non-recursive traversal. All pending neighboring vertices 
// are placed on a stack. 
           
// This function should be made to take a third parameter -- the action
// to perform on a vertex, a functional object with overloaded operator() .
// All such objects can be inherited from (an abtsract) class vertex_action,
// which should then be the type of the third argument.
           
void depth_first_traversal( const graph& gr , vertex origin ){

  stack_of_vertex pending_stack;             //stack of pending vertices
  pending_stack.push( origin );              //init stack
  int n = gr.size();
  vector_of_bool marked( n, false );         //vector of marks, 
                                             //init to unmarked
  vertex current;                                               
  while( ! pending_stack.empty() ){
    current = pending_stack.top();
    pending_stack.pop();                                  
    if( ! marked[current] ){                    
      marked[current] = true;                  //mark the unmarked
      cout << gr.name( current ) << " ";       //process a vertex -- print
      
      list_of_vertex lst = gr.neighbors( current );  //push all neighbors onto 
      push_all( pending_stack, lst );                //the pending_stack   
    } 
  }
  cout << endl;   
}  

// The same code as for depth-first, only a queue is used instead of a stack!
// I know of no natural way of doing this recursively.
  
void breadth_first_traversal( const graph& gr , vertex origin ){

  queue_of_vertex   pending_queue;           //queue of pending vertices
  pending_queue.push( origin );              //init stack
  vector_of_bool marked( gr.size(), false ); //vector of marks, 
                                             //init to unmarked
  vertex current;                                               
  while( ! pending_queue.empty() ){
    current = pending_queue.front();
    pending_queue.pop();                                  
    if( ! marked[current] ){                    
      marked[current] = true;                  //mark the unmarked
      cout << gr.name( current ) << " ";       //process a vertex -- print

      list_of_vertex lst = gr.neighbors( current ); //push all neighbors onto 
      push_all( pending_queue, lst );               //the pending_queue
    } 
  }
  cout << endl;   
}

// ************************ Dijkstra's Algorithm ***************************

//According to the description of Dijkstra's algorithms, keep
//a tally of minimal known distances (KDs in the handout). 
//Keep the list S of vertices with already known shortest paths and
//actual shortest distances (=KD), a priority queue Q of pending 
//vertices. Each time a new vertex is chosen for S (popped off Q),
//update the KDs of its neighbors and push these updated vaues
//back into Q. Some vertices may thus appear in the queue several
//times. It's OK, we check is the vertex popped off Q is actually
//already in S and ignore it if so.

//NOTE: Dijkstra's algorithm works only for non-negative weights!
//      If some edge weights are negative, its results will be wrong. 

//Some preparatory types, not used elsewhere

struct kd_pair {
  vertex vert;
  int    dist;
  kd_pair( vertex v, int d ) : vert(v), dist(d) {}
  bool operator< ( const kd_pair& rhs ) const {
    return dist < rhs.dist;
  }
};

// Change this for MSL -- my UserTypePriorityQ project

typedef priority_queue< kd_pair, 
                        vector<kd_pair>, 
                        greater<kd_pair> >  kd_queue;

//instead of keeping a _set_ S of vertices whose KD are final (i.e. for
//which the shortest paths are found), keep a vector of marks. Those
//marked are in S, those unmarked are still outside (maybe in Q)
//Use a vector of KDs ("tally" -- I just like the word) for bookkeeping

void dijkstra( weighted_graph& gr, vertex source ){

  kd_queue        Q;
  vector_of_int   kd_tally ( gr.size(), INFTY ); //KDs of vertices
  vector_of_bool  marked   ( gr.size(), false ); //marked <=> is in S

  Q.push( kd_pair(source,0) );   //initialize queue - push the source on Q 
  kd_tally[source]=0;
  
  //main loop                         
  
  while( ! Q.empty() ){
    kd_pair current_pair = Q.top();
    Q.pop();
    vertex vx = current_pair.vert;      //current vertex
    int ds = current_pair.dist;         //its KD

    if( ! marked[vx] ){       //if vx is already in S, discard
      marked[vx] = true;      //else add vx to S (mark)
      
      cout << "added vetrex " << gr.name(vx) 
	   << " with KD = " << kd_tally[vx] << '\n';
      
      //for all neighbors of vx, update KD and push onto Q 
      list_of_vertex lst = gr.neighbors( vx );
      list_of_vertex::iterator p = lst.begin();  
      list_of_vertex::iterator e = lst.end();       
      while( p != e ){                     // *p runs over vertices in ngbr lst
	kd_tally[*p] = min( kd_tally[*p],              //along old path, if any
			    kd_tally[vx] + gr.weight(vx,*p) ); 
	                                               //along new path
	Q.push( kd_pair( *p, kd_tally[*p] ) ); 

	cout << "pushed vertex " << gr.name(*p) 
             << " with KD = " << kd_tally[*p] << '\n';

	++p;
      }
    }
  }
  for( int i=0; i < gr.size(); i++ )                    //print the results
    cout << gr.name(source) << " --> " << gr.name(i) 
	 << " : " << kd_tally[i] << "\n";
  cout << endl;
}    

#endif // __ELIST_ALG_H__

/////////////////////////////////////////////////////////////////////// 
//
//  test-graph.h   --   Call all of the above algortihms 
// 
///////////////////////////////////////////////////////////////////////

#include <iostream.h>

#include "graph-elist.h"
#include "elist-alg.h"

void print_weighted_graph( weighted_graph& gr );

main(){
  graph G( "gr0.dat" );

  cout << "\nDepth first traversal:\n";
  depth_first_traversal( G, 0 );
  
  cout << "\nBreadth first traversal:\n";
  breadth_first_traversal( G, 0 );

  cout << "\nReading weighted graph:\n"; 
  weighted_graph wg1( "wgr0.dat" );
  print_weighted_graph( wg1 );

  cout << "\nDijkstra's algorithm from origin 0:\n";
  weighted_graph wg2( "wgr1.dat" );
  print_weighted_graph( wg2 );
  dijkstra( wg2, 0 );   //this is the example from the handout

}