/* File: find_path.cpp
 *
 * Reads in a graph and a series of pairs of nodes.  For each pair of nodes,
 * it returns the shortest path connecting them.
 */

#include <iostream>                      // C++ I/O
using namespace std;
#include <new>                           // C++ memory management
#include "graph.h"                       // the graph class
#include "shortest_paths.h"              // the shortest paths module

void read_graph(Graph **graph);
bool get_vertices(int *x, int *y);
void print_path(bool exists, int length, int numvertices, int *path);

int main(void)
{
    Graph *graph;                        // the graph
    int x, y;                            // two vertices
    int length;                          // a length
    int numvertices;                     // the number of vertices
    int *path;                           // an array to hold the path
    bool newgraph;                       // had the graph changed?
    bool ok;                             // is the path ok (i.e. it exists)

    read_graph(&graph);                  // input the graph
    newgraph = true;
    path = new int [graph->size()];      // allocate space for the path

    while (get_vertices(&x, &y))         // if user enters 2 vertices
    {                                    // find the path and print it
        ok = shortest_path(graph, x, y, &length, &numvertices, path, newgraph);
        print_path(ok, length, numvertices, path);
        newgraph = false;                // no longer a new graph for path alg.
    }

    delete[] path;                       // clean up and exit
    delete graph;

    return 0;
}

/*
 * read_graph() - read in the graph
 */
void read_graph(Graph **graph)
{
    int size;                                    // the size of the graph
    bool done = false;                           // are we done?
    int x, y, length;                            // buffers input values

    cin >> size;                                 // read in the size
    *graph = new Graph(size);                    // and create the graph

    while (!done)                                // until no more data
    {
        cin >> x;                                // read in the first vertex
        if (x < 0)                               // if not a valid vertex,
            done = true;                         //   we are done
        else
        {
            cin >> y >> length;                  // else read in rest of data 
            (*graph)->add_edge(x, y, length);    // and add edge to graph
        }
    }
}

/*
 * get_vertices() - x and y are set to the next two input vertices
 */
bool get_vertices(int *x, int *y)
{
    bool good_data = true;                  // did we successfully read?

    cout << "Enter two vertices >> ";
    cin >> *x;                              // read in x

    if (*x < 0)                             // if x is not valid
        good_data = false;                  // then user wants to exit

    else if (!(cin >> *y))                  // else read in y
    {                                       // and check for errors
        cout << "Error inputting data\n";
        good_data = false;
    }

    if (!good_data)                         // if bad data, let user know we
        cout << "Bye!\n";                   // will be leaving
    return good_data;
}

/*
 * print_path() - output the path found.  exists is true if a path exists,
 *    length is the length of the path, numvertices is the number of vertices
 *    on the path, and path is an array storing the path.
 */
void print_path(bool exists, int length, int numvertices, int *path)
{
    int i;

    if (!exists)                               // is there a path?
        cout << "No path exists.\n\n";
    else
    {
        cout << "The shortest path has length " << length << ".\n";
        cout << "The path is";
        for (i = 0; i < numvertices; i++)      // output the path vertices
            cout << ' ' << path[i];
        cout << "\n\n";
    }
}