/**
  \file shortestpath.c
  	\author Lucia Del Colombo
  Si dichiara che il contenuto di questo file e' in ogni sua parte opera
     originale dell' autore. 
   
   \brief Implementazione delle funzioni ausiliarie i cui prototipi si trovano nel file dgraph_aux.h */

#include <stdlib.h>
#include <string.h>
#include <float.h>
#include "shortestpath.h"
#include "graph_err.h"
#include "dgraph_aux.h"

/**
set: insieme dei nodi usati per calcolare i cammini minimi:
		se set[i] == 0 il nodo i non è stato ancora aggiunto all'insieme
		se set[i] == 1 il nodo è stato aggiunto all'insieme

*/
double *dijkstra(graph_t * g, unsigned int source, unsigned int **pprec)
{
    int *node_set, i, j, k, node_to_add;
    double *dist, dist_temp, dist_temp2, dist_w;
    edge_t *etemp;
    unsigned int *myprec = NULL;

/** Gestione errore */
    if (g == NULL || source > g->size) {
	errno = EINVAL;
	return NULL;
    }

/** Allocazione set di nodi, vettore delle distanze da restituire ed eventualmente del vettore pprec */
    ec_nullNULL_c((node_set =
		   (int *) calloc(g->size, sizeof(int))), errno = ENOMEM);
    ec_nullNULL_c((dist =
		   (double *) calloc(g->size, sizeof(double))), errno =
		  ENOMEM);
    if (pprec != NULL) {
	ec_nullNULL_c((myprec =
		       (unsigned int *) calloc(g->size,
					       sizeof(unsigned int))),
		      errno = ENOMEM);
    }

/** Inizializzazione: le distanze e l'insieme set di nodi usati per calcolare i costi minimi sono inizializzati a 0 */
    for (i = 0; i < g->size; i++) {
	if (i == source) {
	    node_set[i] = 1;
	    dist[i] = 0;
	} else {
	    node_set[i] = 0;
	    dist[i] = INFINITY;
	}
	if (pprec != NULL)
	    myprec[i] = UNDEF;
    }
/** Inizializzazione distanze dai nodi adiacenti all sorgente */
    for (etemp = g->node[source].adj; etemp != NULL; etemp = etemp->next) {
	dist[etemp->label] = etemp->km;
	if (pprec != NULL)
	    myprec[etemp->label] = source;
    }

/** Ciclo: inserisco tutti i nodi nell'insieme di quelli usati per calcolare i cammini minimi */
    for (i = 0; i < g->size; i++) {
	node_to_add = 0;
	dist_w = INFINITY;

/** Trovo il nodo non in set la cui distanza da w è minima */
	for (j = 0; j < g->size; j++) {
	    if (!node_set[j]
		&& ((dist_w == INFINITY && dist[j] != INFINITY)
		    || (dist_w != INFINITY && dist[j] != INFINITY
			&& dist[j] < dist_w))) {
		node_to_add = j;
		dist_w = dist[j];
	    }
	}
	node_set[node_to_add] = 1;

/** Trovo il costo minimo usando il nuovo nodo node_to_add */
	for (k = 0; k < g->size; k++) {
	    if ((dist_temp2 = trova_costo(g, node_to_add, k)) < 0)
		dist_temp = INFINITY;
	    else {
		dist_temp = dist_w + dist_temp2;

		if (!node_set[k]
		    && (dist[k] == INFINITY || dist_temp < dist[k])) {
		    dist[k] = dist_temp;
		    if (pprec != NULL && k != source)
			myprec[k] = node_to_add;
		}
	    }
	}

    }
    free(node_set);
    if (pprec != NULL)
	*pprec = myprec;
    return dist;
}


char *shpath_to_string(graph_t * g, unsigned int n1, unsigned int n2,
		       unsigned int *prec)
{
    char *route;
    int *vtemp, k, lroute, i = 0;

/** se non si è verificato un errore ma la rotta non esiste errno deve valere 0 */
    errno = 0;
    if (prec == NULL) {
	errno = EINVAL;
	return NULL;
    }

/** Gestione errore */
    if (g == NULL || n1 < 0 || n1 > g->size || n2 < 0 || n2 > g->size) {
	errno = EINVAL;
	return NULL;
    }

    if (prec[n2] == UNDEF) {
	errno = EINVAL;
	return NULL;
    }


/** Allocazione stringa */
    ec_nullNULL_c((vtemp =
		   (int *) calloc(g->size, sizeof(int))), errno = ENOMEM);
    k = prec[n2];
    lroute = strlen(g->node[n1].label) + 1;
    while (k != n1) {
	vtemp[i] = k;
	lroute += strlen(g->node[k].label) + 1;
	k = prec[k];
	i++;
    }
    lroute += strlen(g->node[n2].label) + 2;
    ec_nullNULL_c((route = (char *) malloc(lroute + 2)), errno = ENOMEM);
    route[0] = '\0';
    strcat(route, g->node[n1].label);
    while (i-- != 0) {
	strcat(strcat(route, "$"), g->node[vtemp[i]].label);
    }
    strcat(strcat(route, "$"), g->node[n2].label);
    free(vtemp);

    return route;

}