/* File: shortest_path.cpp
 *
 * The module to find a shortest path.
 */

#include <climits>
#include "graph.h"                       // the graph class
#include "shortest_paths.h"              // the interface for shortest_path

#define INFINITY (LONG_MAX >> 2)         // a value for infinity
#define NONE -1                          // not a vertex

/* the prototypes for the local helper functions */
void all_pairs_shortest_paths(Graph *graph, int *Dist[], int *Mid[]);
void form_matrices(int ***A, int ***B, int oldsize, int newsize);
void setpath(int x, int y, int *count, int *path, int *M[]);

/*
 * all_pairs_shortest_paths() - given a graph, run the Floyd-Warshall all-pairs
 *     algorithm.  Set D to hold the distances and Mid to hold the median
 *     vertex of the path found.
 */
void all_pairs_shortest_paths(Graph *graph, int *Dist[], int *Mid[])
{
    int size = graph->size();                      // number of vertices
    int i, j, k;                                   // generic counters

    for (i = 0; i < size; i++)                     // initialize the distance
        for (j = 0; j < size; j++)                 // matrix to hold the length
            if (i == j)                            // of the shortest path with
            {                                      // 0 intermediate vertices
                Dist[i][j] = 0;
                Mid[i][j] = i;
            }
            else if (graph->is_adjacent(i, j))
            {
                Dist[i][j] = graph->edge_length(i, j);
                Mid[i][j] = i;
            }
            else
            {
                Dist[i][j] = INFINITY;
                Mid[i][j] = NONE;
            }

    for (k = 0; k < size; k++)                     // run the all-pairs alg.
        for (i = 0; i < size; i++)
            for (j = 0; j < size; j++)
                if (Dist[i][j] > Dist[i][k] + Dist[k][j])
                {
                    Dist[i][j] = Dist[i][k] + Dist[k][j];
                    Mid[i][j] = k;
                }
}

/*
 * shortest_path() - returns true if there is a path from "from" to "to".
 *     pathlength returns the length of the path, pathnodes returns the number
 *     of nodes on the path, and path returns the path.  If new_graph is false
 *     we do not recompute the shortest_paths algorithm.
 */
bool shortest_path(Graph *graph, int from, int to, int *pathlength,
                   int *pathnodes, int *path, bool new_graph)
{
    static int **Mid = 0;                      // save the paths found and the
    static int **Dist = 0;                     // distances for the next time
    static int size;

    int count;                                 // counts vertices on path

    if (new_graph)                             // if a new graph, allocate space
    {                                          // for matrices and run all-pairs
        form_matrices(&Mid, &Dist, size, graph->size());
        size = graph->size();                  // remember how much we allocated
        all_pairs_shortest_paths(graph, Dist, Mid);
    }

    if ((to   < 0) || (to   >= graph->size()) ||
        (from < 0) || (from >= graph->size()))
    {                                          // make sure legal nodes are 
        return false;                          // entered
    }

    if (Dist[from][to] == INFINITY)            // if there is no path...
        return false;
    else
    {
        count = 1;
        setpath(from, to, &count, path, Mid);  // retrieve the path from the 
        path[0] = from;                        // Mid matrix and set the first
        if (from != to)                        // and last vertices
            path[count++] = to;
        *pathlength = Dist[from][to];          // return the path length
        *pathnodes = count;                    // and number of vertices
    }

    return true;                               // a path exists
}

/*
 * set_path() - recursively generates the path x->y, not including the end
 *     vertices, from the matrix M of intermediate nodes.  path is the array 
 *     where the path is stored and count is the next index into path.
 */
void setpath(int x, int y, int *count, int *path, int *M[])
{
    if (x == y)                                 // no intermediate vertices
        return;
    else if ((M[x][y] == x) || (M[x][y] == y))  // also no itermediates nodes
        return;
    else                                        // M[x][y] is intermediate node
    {
        setpath(x, M[x][y], count, path, M);    // get path from x to M[x][y]
        path[(*count)++] = M[x][y];             // add node M[x][y]
        setpath(M[x][y], y, count, path, M);    // and path from M[x][y] to y
    }
}

/*
 * form_matrices() - takes pointer to 2 matrices.  If the matrices had been 
 *   allocated space, free it and reallocate so A and B are (newsize)x(newsize)
 *   matrices.  oldsize is the size of the previous allocation.
 */
void form_matrices(int ***A, int ***B, int oldsize, int newsize)
{
    int i;
    int **M1 = *A;                     // to simplify code, use a pointer
    int **M2 = *B;

    if (M1 != 0)                       // if M1 (A) holds data 
    {
        for (i = 0; i < oldsize; i++)  // free each row
            delete[] M1[i];
        delete[] M1;                   // and free matrix
    }
    if (M2 != 0)                       // if M2 (B) holds data
    {
        for (i = 0; i < oldsize; i++)  // free each row
            delete[] M2[i];
        delete[] M2;                   // and free matrix
    }

    M1 = new int * [newsize];          // allocate a pointer to each row
    M2 = new int * [newsize];
    for (i = 0; i < newsize; i++)
    {
        M1[i] = new int [newsize];     // and allocate each row
        M2[i] = new int [newsize];
    }

    *A = M1;                           // return the new memory
    *B = M2;
}