/*
 * Dijkstra's least cost routing algorithm with one parameter, link cost.
 * 
 * See http://www.cs.earlham.edu/~charliep/classes/cs73/djikstra.txt for a
 * description of the assignment.
 * 
 * The input file which describes a network consists of node, node, cost rows,
 * one per edge in the network.
 * 
 * NB - I choose to normalize the data files one.net and two.net with node
 * numbers in the range 0-n rather than 1-n+1 as they were provided.
 * 
 * One severe limitation of this implementation is that node identifiers must be
 * contiguous integers ranging from 0 to the number of nodes.
 * 
 * The generated routing tables need to be adusted for adjacent vs. disjoint
 * routes before they are used.  All the necessary information is contained
 * in them to do this, just recurse until destination = directly connected route.
 * 
 * Charlie Peck 
 * March, 1999
*/

#include <stdio.h>
#include <limits.h>

#define SUCCESS 0
#define FAILURE 1

#define TRUE 1
#define FALSE 0

#define MAX_LINKS 64
#define MAX_NODES 32

#define DIMENSIONS 3
#define NODE_A 0
#define NODE_B 1
#define COST 2

#define INITIALIZE 0
#define CHEAPEST 1
#define EXISTS 2

int     load_network(int argc, char *argv[], int network[][], int *link_count, 
                     int *node_count);
void    display_network(int network[][], int link_count, int node_count);
void    display_tables(int route[], int cost[], int source, int node_count);
int     calculate_cost(int source, int destination, int network[][], int link_count);
int     node_iterator(int _command, int *node, int cost[], int node_count);

long    function_counter = 0;
long    loop_counter = 0;


int     main(int argc, char *argv[]) {

    int     network[MAX_LINKS][DIMENSIONS] = {{0}, {0}};
    int     source = 0, destination = 0;
    int     cost[MAX_NODES] = {INT_MAX};
    int     route[MAX_NODES] = {INT_MAX};
    int     other_nodes[MAX_NODES] = {0};
    int     link_count = 0, node_count = 0, current = 0, new_cost = 0;
    int     status = FAILURE, index = 0;

    status = load_network(argc, argv, network, &link_count, &node_count);
    if (status == FAILURE)
        return (FAILURE);
        
    display_network(network, link_count, node_count); 
    
    /* 
     * In turn make each node in the network the source.
    */ 
    for (source = 0; source < node_count; source++) {
        loop_counter++;

        /*
         * Initialize the route and cost tables for this source node.
        */ 
        for (index = 0; index < node_count; index++) {
            loop_counter++;

            cost[index] = calculate_cost(source, index, network, link_count);
            if (cost[index] != INT_MAX)
                route[index] = index;
            else
                route[index] = -1;
        }

        /*
         * Initialize the iterator with all the other nodes in the network.
        */ 
        node_iterator(INITIALIZE, &source, cost, node_count);

        /* 
         * Visit all the other nodes in order of closest to most distant.
        */ 
        while (node_iterator(CHEAPEST, &current, cost, node_count)) {
            loop_counter++;

            /*
             * If there isn't a way to get from the source to here skip it.
            */ 
            if (cost[current] == INT_MAX) {
                break;
            }
            
            /*
             * Check all of other places we can go from here. 
            */ 
            for (destination = 0; destination < node_count; destination++) {
                loop_counter++;

                /* 
                 * If we can't get there from here skip it.
                */ 
                if (calculate_cost(current, destination, network, link_count) != INT_MAX) {

                    /* 
                     * If it's still in the list of nodes that we care about
                    */ 
                    if (node_iterator(EXISTS, &destination, cost, node_count)) {

                        new_cost = cost[current] +
                            calculate_cost(current, destination, network, link_count);

                        /*
                         * Is this route cheaper than the one we currently have?
                        */ 
                        if (new_cost < cost[destination]) {
                            route[destination] = current;
                            cost[destination] = new_cost;
                        }
                    }
                }
            }
        }

        display_tables(route, cost, source, node_count);
    }

    printf("dijkstra - function_counter = %ld\n", function_counter);
    printf("dijkstra - loop_counter = %ld\n", loop_counter);

    return (SUCCESS);
}


int     load_network(int _argc, char *argv[], int network[MAX_LINKS][DIMENSIONS],
                     int *link_count, int *node_count) {

    FILE    *infile_handle;
    char    infile_name[128];
    int     node_a = 0, node_b = 0, cost = 0;

    function_counter++;

    if (_argc != 2) {
        printf("Enter the name of the network description file: ");
        fscanf(stdin, "%s", infile_name);
    } else
        strcpy(infile_name, argv[1]);

    if (!(infile_handle = fopen(infile_name, "r"))) {
        fprintf(stderr, "dijkstra - error opening input file %s\n", infile_name);
        return (FAILURE);
    }
    
    while (fscanf(infile_handle, "%d %d %d", &node_a, &node_b, &cost) != EOF) {
        loop_counter++;
        network[*link_count][NODE_A] = node_a;
        network[*link_count][NODE_B] = node_b;
        network[*link_count][COST] = cost;
        (*link_count)++;

        if (node_a > *node_count)
            *node_count = node_a;

        if (node_b > *node_count)
            *node_count = node_b;
    }

    fclose(infile_handle);

    /* 
     * 0 - 3 is 4 nodes, etc. given the specifications.
    */
    (*node_count)++;    

    if (*node_count > MAX_NODES) {
        fprintf(stderr, "dijkstra - node_count is greater than MAX_NODES\n");
        return (FAILURE);
    }
    
    return (SUCCESS);
}


int     calculate_cost(int _source, int _destination, int network[MAX_LINKS][DIMENSIONS],
                       int _link_count) {

    int     index = 0, value = INT_MAX;

    function_counter++;

    for (index = 0; index < _link_count; index++) {
        loop_counter++;

        if ((network[index][NODE_A] == _source) &&
            (network[index][NODE_B] == _destination)
            ||
            (network[index][NODE_B] == _source) &&
            (network[index][NODE_A] == _destination)
            )
            if (network[index][COST] < value)
                value = network[index][COST];
    }

    return (value);
}


int     node_iterator(int _command, int *node, int cost[MAX_NODES], int _node_count) {

    static int      nodes[MAX_NODES] = {INT_MAX};
    int             index = 0, new_cost = INT_MAX, choice = 0;

    function_counter++;

    if (_command == INITIALIZE) {

        for (index = 0; index < _node_count; index++) {
            loop_counter++;

            if (index == *node)
                nodes[index] = FALSE;
            else
                nodes[index] = TRUE;
        }

        return (TRUE);
    }
    
    if (_command == CHEAPEST) {
        int     empty = TRUE;

        for (index = 0; index < _node_count; index++) {
            loop_counter++;

            if (nodes[index] == TRUE) {
                empty = FALSE;

                if (cost[index] <= new_cost) {
                    new_cost = cost[index];
                    choice = index;
                }
            }
        }

        if (empty) {
            *node = INT_MAX;
            return (FALSE);
        } else {
            *node = choice;
            nodes[choice] = FALSE;
            return (TRUE);
        }
    }
    
    if (_command == EXISTS) {

        if (nodes[*node] == TRUE)
            return (TRUE);
        else
            return (FALSE);
    }
    
    fprintf(stderr, "dijkstra - invalid command given to node_iterator\n");
    return (FALSE);
}


void    display_network(int network[MAX_LINKS][DIMENSIONS], int _link_count,
                        int _node_count) {

    int     index = 0;

    fprintf(stdout, "dijkstra - link_count = %d, node_count = %d\n", _link_count,
        _node_count);

    for (index = 0; index < _link_count; index++)
        fprintf(stdout, "dijkstra - node a: %d   node b: %d   cost: %d\n",
            network[index][NODE_A], network[index][NODE_B],
            network[index][COST]);
            
    return;
}


void    display_tables(int route[MAX_NODES], int cost[MAX_NODES], int _source,
                       int _node_count) {

    int     index = 0;

    for (index = 0; index < _node_count; index++)
        fprintf(stdout, "dijkstra - source = %d, destination = %d, route = %d, cost = %d\n",
            _source, index, route[index], cost[index]);

    return;
}