//*****************************************************************************************
//  This program finds the shortest path from one vertex of a 'dgraph' to all others.
//  It uses: a 'Set' to keep track of the shortest path vertices;
//           a table (of type Vertexinfo) that, for each vertex keeps track of its edges,
//               where each edge goes (to which vertex) and each edge's weight
//               - this information is supplied -;
//           a final table (of type Shortpath) that keeps track of each vertex's overall
//               weight (from the starting vertex) and how to get to it 
//               - this information must be calculated and is the program's goal -.
//  filename: graph1.cpp
//  Author: Kimberlie Davis
//*****************************************************************************************
 
#include <iostream>
#include <fstream>
#include <iomanip> 
#include <cctype>
#include "sets.cpp"
 
int const VERTICES = 5;
int const TOOLARGE = 30000;
 
using namespace std;
 
struct Pathinfo
{
  int vertexto;
  int weight;
};                  
 
struct Vertexinfo
{
  int edgecount;
  Pathinfo path[VERTICES - 1];
};
 
struct Shortpath
{
  int distance;
  int via;
};
 
 
class Paths
{
  private:
    Vertexinfo edgedata[VERTICES];
    Shortpath shortpath[VERTICES];
    Set done;
  public:
    void filldata(void);
    void filldatafile(char []);
    void printdata(void);
    void initialize(int);
    int findshortest(void);
    void updatepaths(int);
    void printpaths(int);
    void calculate(int);
};
 
//--------------------------------------------------------------------------
// 'filldata' for each vertex, receives a count of the number of edges,
//  then for each edge finds out where it goes (vertex to) and the weight.
//
//  A problem exists in that the user names the vertices from 1 up, but
//  they will be used as subscripts (which start at 0); so 1 is subtracted
//  from the vertex number being input
//--------------------------------------------------------------------------
 
void
Paths::filldata ( )
{
  int vertex, edge;
 
  cout << "For each vertex first enter the number of edges to it\n";
  cout << "then for each edge input the vertex it goes to and its weight\n\n";
 
  for (vertex = 0; vertex < VERTICES; vertex++)
  {
    cout << "  For vertex number  " << vertex+1 << '\n';
    cout << "    How many edges : ";
    cin  >> edgedata[vertex].edgecount;
 
    for (edge = 0; edge < edgedata[vertex].edgecount; edge++)
    {
      cout << "    Edge number   " << edge+1 << '\n';
      cout << "      To vertex # ";
      cin  >> edgedata[vertex].path[edge].vertexto;
      edgedata[vertex].path[edge].vertexto--;                        // <---- turn into subscript
      cout << "      Weight      ";
      cin  >> edgedata[vertex].path[edge].weight;
    }
  }
}
 
//--------------------------------------------------------------------------
// 'filldatafile' for each vertex, receives a count of the number of edges,
//  then for each edge finds out where it goes (vertex to) and the weight.
//  the data comes from a file, the filename is asked of the user
 
//  A problem exists in that the user creates the file using vertices 
//  numbered from 1 up, but they will be used as subscripts (which start at 0)
//  so 1 is subtracted from the vertex number being input
//--------------------------------------------------------------------------
 
void
Paths::filldatafile (char filename[])
{
  int vertex, edge;
  ifstream infile;
 
  infile.open(filename);
  if (!infile.fail())
  {
    for (vertex = 0; vertex < VERTICES; vertex++)
    {
      infile  >> edgedata[vertex].edgecount;
 
      for (edge = 0; edge < edgedata[vertex].edgecount; edge++)
      {
        infile  >> edgedata[vertex].path[edge].vertexto;
        edgedata[vertex].path[edge].vertexto--;                      // <---- turn into subscript
        infile  >> edgedata[vertex].path[edge].weight;
      }
    }
  }
  else
  {
    for (vertex = 0; vertex < VERTICES; vertex++)
      edgedata[vertex].edgecount = 0;
  }
 
}
 
//--------------------------------------------------------------------------
// 'printdata' displays the entered vertex information so the user can make
//  sure the data is entered correctly.  To compensate for the vertices
//  being used as subscripts, 1 is added to the vertex display.  1 is also
//  added to the edge for display since edge is also used as a subscript
//--------------------------------------------------------------------------
 
void
Paths::printdata ( )
{
  int vertex, edge;
 
  cout << "\nThe following data was input\n\n";
 
 
  for (vertex = 0; vertex < VERTICES; vertex++)
  {
    cout << "  Vertex number " << vertex+1 << "  ";
    cout << edgedata[vertex].edgecount <<" edges\n";
 
    for (edge = 0; edge < edgedata[vertex].edgecount; edge++)
    {
      cout << "    Edge number " << edge+1 ;
      cout << "   To vertex # " << edgedata[vertex].path[edge].vertexto+1;;
      cout << "  Weight " << edgedata[vertex].path[edge].weight << '\n';
    }
 
    cout << '\n';
 
  }
}
 
//--------------------------------------------------------------------------
// 'initialize' takes the starting vertex and stores it as the the 'via' 
//  for each vertex.  It also sets the distance to a very large number;
//  except the starting vertex where the distance is set to 0
//--------------------------------------------------------------------------
 
void
Paths::initialize (int startnode)
{
  int i;
  for (i = 0; i < VERTICES; i++)
  {
    shortpath[i].distance = TOOLARGE;
    shortpath[i].via = startnode;
  }
 
  shortpath[startnode].distance = 0;
}
 
 
 
//--------------------------------------------------------------------------
// 'findshortest' searches the distance/via table for the smallest weight
//  of a vertex that hasn't yet been completed (i.e. not in the Set)
//--------------------------------------------------------------------------
 
int
Paths::findshortest ( )
{
  int vertex, smalldist, smallvertex;
 
  smalldist = TOOLARGE;
  smallvertex = TOOLARGE;
 
  for (vertex = 0; vertex < VERTICES; vertex++)
    if (!done.in(vertex) && shortpath[vertex].distance < smalldist)
    {
      smalldist = shortpath[vertex].distance;
      smallvertex = vertex;
    }
 
  return smallvertex;
}
 
//--------------------------------------------------------------------------
// 'updatepaths' uses the newest vertex which was added to the Set to modify
//  the distances of the remaining vertices (if smaller)
//  in addition to the newly added vertex, it uses the Set, the Vertexinfo
//  and the Shortpath tables
//--------------------------------------------------------------------------
void
Paths::updatepaths(int value)
{
   int total;
   int subscript;
 
   for(int i = 0; i < edgedata[value].edgecount; i++)
   {
          if(!done.in(edgedata[value].path[i].vertexto))
          {
             total = edgedata[value].path[i].weight + shortpath[value].distance;
 
             if(total < shortpath[i].distance)
             {
                      shortpath[i].distance  = total;
                      shortpath[i].via = value;   
 
             }                         
          } 
   }           
}
 
//--------------------------------------------------------------------------
// 'calculate' initialized the Set done, adds the starting vertex to done,
//  then performs a loop finding the next shortest path, adding it to the 
//  set, and updating the shortpath table
//--------------------------------------------------------------------------
 
void
Paths::calculate (int addnode)
{ 
  int loop;
 
  done.initialize(); 
  done.add(addnode);
  updatepaths (addnode); 
 
  for (loop = 1; loop < VERTICES; loop++)
  {  
    addnode = findshortest( );
    if (addnode != TOOLARGE)
    {
      done.add(addnode);
      updatepaths(addnode);
    }
  }
} 
 
//--------------------------------------------------------------------------
// 'printpaths' displays a table showing the starting vertex then every
//  vertex, its final weight (distance) and how to get there (via)
//  this last information is in the Shortpath table
//--------------------------------------------------------------------------
void
Paths::printpaths(int value)
{
      cout << "Vertex: " << "      " << "Distance: " << "        " << "Via: " << endl;
      for(int i = 0; i < 5; i++)
      {         
          cout << i+1 << "                " << shortpath[i].distance << "               " << shortpath[i].via+1 << endl;
      }    
}
 
//------------------------- main routine -------------------------
 
int
main()
{ 
  Paths findall;
  int startvertex, addnode;
  char response;
  char file[25];
 
  do
  { 
    cout << "Is the data being input from a file (y/n) ? ";
    cin  >> response;
    if (tolower(response) == 'y')
    {
      cin.get();
      cout << "Please enter the filename : "<<flush;
      cin.getline(file, 25);
      findall.filldatafile(file);
    }
    else
      findall.filldata();
    findall.printdata();                              
    cout << "Is the data correct (y/n) ? ";      
    cin  >> response;                                
  }
  while (tolower(response) == 'n');
 
  do
  {
    cout << "\nWhat is your starting vertex number? ";
    cin  >> startvertex;
 
    addnode = startvertex - 1;
    findall.initialize (addnode);
    findall.calculate (addnode);
 
    findall.printpaths (startvertex);
 
    cout << "\nWould you like to see the distances starting from another vertex (y/n) ? ";
    cin  >> response;
  }
  while ( tolower(response) == 'y' );
 
  system("pause");
  return 0;
}