// Main program
#include <iostream>
#include "graph.cc"
using namespace std;
 
main ()
{
 
  graph flightfares;
  flightfares.build_graph();
  flightfares.print_graph();
  flightfares.find_shortest_dist();
  // My program will get right here then hit seg fault
}
 
 
 
 
 
 
// Class and implementation program 
// graph.cc
#include <iostream>
#include <vector>
#include <string>
#include <float.h>
using namespace std;
 
 
 
 
struct costpair
  {
    int vnum;
    float fare;
    costpair(int v = 0, float f = 0):vnum(v), fare(f){};
  };
 
 
 
 
 
struct node
  {
    costpair info;
    node * next;
  };
 
 
 
 
 
class graph
  {
    public:
      graph();
      ~graph();
      void build_graph();
      void print_graph();
    void find_shortest_dist();
 
 
 
    private:
      // Attributes
      vector<string> vnames;
      vector<node*> adjlist;
    double dist[];
    int pred[];
    bool undecided[];
 
      // Member functions
      int index(string name);
      void insert_edge(string name1, string name2, float fare);
      int add_vertice(string name);
      void add_edge(int index1, costpair temp);
      node * createnode(costpair temp);
    void initialize();
  };
 
// Constructor
graph::graph()
{
 
}
 
 
 
 
// Destructor
graph::~graph()
{
  for (int i = 0; i < vnames.size(); i++)  // This loop will run and delete all lists
    {
      node * p = adjlist.at(i);
      node * temp;
      while (p!=NULL)
        {
          temp = p->next;  // Saves pointer to rest of list
          delete p;
          p = temp;
        }
    } 
}
 
 
 
void graph::build_graph()
  {
    string name1, name2;
    int index1, index2;
    float fare;
 
    cin >> name1 >> name2 >> fare;  //Priming Read
    while(name1 != "zzz") // Runs till end of file
      {
        insert_edge (name1, name2, fare);
 
        // This if checks for EOF and reads next line if present
        if(!(cin >> name1 >> name2 >> fare))
          {
            break;
          }
       }
  }
 
 
 
 
// Returns the index of given name
int graph::index(string name)
  {
    for (int i = 0; i < vnames.size(); i++)
      {
        if (vnames.at(i) == name)   return i;
      }
 
    return (-1); // Name was not found
}
 
 
 
// Function to insert new edge
// Called once two names and a fare have been read
void graph::insert_edge(string name1, string name2,
float fare)
  {
    int index1 = index(name1);
    // Next if checks if first name needs to be added
    if (index1 == -1) index1 = add_vertice(name1);  
    int index2 = index(name2);
    // Next if checks if second name needs to be added
    if (index2 == -1) index2 = add_vertice(name2);
    // At this point, index1 and index2 contain the indices of name1 and name2
 
    // This adds the edge
    add_edge(index1, costpair(index2, fare));
}
 
 
 
 
// This functin addes a name to the name vector
// and pushes the adjacency vector back.
// Then the new index of the name is returned
int graph::add_vertice(string name)
  {
    vnames.push_back(name);
    adjlist.push_back(NULL);
    return (vnames.size()-1);
  }
 
 
 
 
//  Here a node is added to the adjacency vector
void graph::add_edge(int index1, costpair temp)
  {
    node * p = createnode(temp);  // Creates node
 
    // Adds node to appropriate list 
    p->next = adjlist.at(index1);
    adjlist.at(index1) = p;
 
  }
 
 
 
// This function creates a node and adds info to node
node * graph::createnode(costpair temp)
  {
    node * p = new node;
    p->info = temp;
    p->next = NULL;
    return p;
  }
 
 
 
// This fuction prints all vertices along with edges
void graph::print_graph()
  {
    for (int i = 0; i < vnames.size(); i++) // Runs for all vertices
      {
        cout << "The vertex is " << vnames.at(i) << endl;
        node * p = adjlist.at(i);  // Pointer to traverse list
        if (p == NULL)  // Checks if list is empty or not
          {
            cout << "This vertex has no neighbors" << endl;
          }
        else
          {
            cout << "The neighbors of this node are " << endl;
            while (p!=NULL)
              {
                cout << vnames.at(p->info.vnum) << "(" << p->info.fare << ")" << endl;
                p = p->next;          
              }
           }
        }
  }
 
 
 
 
 
 
void graph::find_shortest_dist()
{
  initialize();  // Will initialize the several arrays needed
 
}
 
 
void graph::initialize()
{
  dist[vnames.size()];
  pred[vnames.size()];
  undecided[vnames.size()];
 
 
  for (int i = 0; i < vnames.size(); i++)
    {
      dist[i] =  DBL_MAX;
      pred[i] = -1;
      undecided[i]= false;
    }
}