#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#pragma message("INCOMING WITH GRAPHS!")

typedef struct a_t {
    double dist;
    struct v_t *ponta;
    struct a_t *prox;
} a_t;

typedef struct v_t {
    char nome[20];
    a_t *arco;
    struct v_t *prox;
} v_t;

void imprime_rota (v_t *final,v_t **precedences,v_t *grafo);
int all_visited(int *visitedarray,int size);
void get_vertex (char *name,int index,v_t *graph);
int get_index(char *name,v_t *graph);
int vertex_num (v_t *graph);
v_t *vseek (char *node,v_t *graph);
v_t *grafo(void);
void v_ins (char *from,char *to,v_t **grph);
void a_ins (char *to,double peso,a_t **arest,v_t *graph);
void node_insert (char *from,char *to,double dist,v_t **graph);
void vdisplay (const char *prompt,v_t *graph,char separator);
void adisplay (a_t *arc);
void alist (a_t *arc);
void gprintf (v_t *grafo);
double dijkstra(v_t *graph,char *orig,char *dest);
double weight (v_t *graph,char *orig,char *dest);
int arest_num (v_t *vertex);
v_t *adj_obtain (v_t *vertex,int position);
v_t *get_min_vertex (int *visited,double *distances,int size,v_t *graph);
double dij (v_t *graph,char *orig,char *dest);

int main(void) {
    v_t *graph;
    graph = grafo();
    printf ("Vetice 4 de Bucharest: %s\n\n",(adj_obtain(vseek("Bucharest",graph),3))->nome);
    printf ("Dijkstra: %lf\n\n",dij(graph,"Arad","Bucharest"));
    printf ("A(Bucharest) = %d\n\n",arest_num(vseek("Bucharest",graph)));
    printf ("Entre Craiova e Dobreta: %.2f\n\nGRAFO:\n\n",weight(graph,"Craiova","Dobreta"));
    while (graph) {
        gprintf(graph);
        graph = graph->prox;
    }
    return 0;
}

v_t *grafo(void) {
    v_t *graph = NULL;
    node_insert("Neamt","Iasi",87,&graph);
    node_insert("Iasi","Neamt",87,&graph);
    node_insert("Iasi","Vaslui",92,&graph);
    node_insert("Vaslui","Iasi",92,&graph);
    node_insert("Vaslui","Urziceni",142,&graph);
    node_insert("Urziceni","Vaslui",142,&graph);
    node_insert("Urziceni","Hirsova",98,&graph);
    node_insert("Hirsova","Urziceni",98,&graph);
    node_insert("Urziceni","Bucharest",85,&graph);
    node_insert("Bucharest","Urziceni",85,&graph);
    node_insert("Hirsova","Eforie",86,&graph);
    node_insert("Eforie","Hirsova",86,&graph);
    node_insert("Bucharest","Giurgiu",90,&graph);
    node_insert("Giurgiu","Bucharest",90,&graph);
    node_insert("Bucharest","Fagaras",211,&graph);
    node_insert("Fagaras","Bucharest",211,&graph);
    node_insert("Bucharest","Pitesti",101,&graph);
    node_insert("Pitesti","Bucharest",101,&graph);
    node_insert("Pitesti","Rimnicu Vilcea",97,&graph);
    node_insert("Rimnicu Vilcea","Pitesti",97,&graph);
    node_insert("Pitesti","Craiova",138,&graph);
    node_insert("Craiova","Pitesti",138,&graph);
    node_insert("Rimnicu Vilcea","Craiova",146,&graph);
    node_insert("Craiova","Rimnicu Vilcea",146,&graph);
    node_insert("Rimnicu Vilcea","Sibiu",80,&graph);
    node_insert("Sibiu","Rimnicu Vilcea",80,&graph);
    node_insert("Sibiu","Fagaras",99,&graph);
    node_insert("Fagaras","Sibiu",99,&graph);
    node_insert("Craiova","Dobreta",120,&graph);
    node_insert("Dobreta","Craiova",120,&graph);
    node_insert("Dobreta","Mehadia",75,&graph);
    node_insert("Mehadia","Dobreta",75,&graph);
    node_insert("Mehadia","Lugoj",70,&graph);
    node_insert("Lugoj","Mehadia",70,&graph);
    node_insert("Lugoj","Timisoara",111,&graph);
    node_insert("Timisoara","Lugoj",111,&graph);
    node_insert("Timisoara","Arad",118,&graph);
    node_insert("Arad","Timisoara",118,&graph);
    node_insert("Arad","Zerind",75,&graph);
    node_insert("Zerind","Arad",75,&graph);
    node_insert("Zerind","Oradea",71,&graph);
    node_insert("Oradea","Zerind",71,&graph);
    node_insert("Arad","Sibiu",140,&graph);
    node_insert("Sibiu","Arad",140,&graph);
    node_insert("Oradea","Sibiu",151,&graph);
    node_insert("Sibiu","Oradea",151,&graph);
    return graph;
}

void v_ins (char *from,char *to,v_t **grph) {
   if (!vseek(from,*grph)) {
       v_t *p1 = (v_t *) malloc(sizeof(v_t));
       strcpy (p1->nome,from);
       p1->arco = NULL;
       p1->prox = *grph;
       *grph = p1;
   }
   if (!vseek(to,*grph)) {
       v_t *p2 = (v_t *) malloc(sizeof(v_t));
       strcpy (p2->nome,to);
       p2->arco = NULL;
       p2->prox = *grph;
       *grph = p2;
   }
}

v_t *vseek (char *node,v_t *grafo) {
    v_t *info = NULL;
    while (grafo) {
        if (!strcmp(grafo->nome,node)) info = grafo;
        grafo = grafo->prox;
    }
    return info;
}

void a_ins (char *to,double peso,a_t **arest,v_t *graph) {
    a_t *p1 = (a_t *) malloc (sizeof(a_t));
    p1->dist = peso;
    p1->ponta = vseek(to,graph);
    p1->prox = *arest;
    *arest = p1;
}

void node_insert (char *from,char *to,double dist,v_t **graph) {
    v_t *point = NULL;
    v_ins(from,to,graph);
    point = vseek(from,*graph);
    if (point) a_ins(to,dist,&(point->arco),*graph);
}

void vdisplay (const char *prompt,v_t *graph,char separator) {
    if (graph) printf ("%s %s%c",prompt,graph->nome,separator);
}

void adisplay (a_t *arc) {
    if (arc) {
        vdisplay("Para:",arc->ponta,'\t');
        printf ("Distancia = %.2lf\n",arc->dist);
    }
}

void gprintf (v_t *grafo) {
    if (grafo && grafo->arco) {
        vdisplay ("Cidade:",grafo,'\n'); alist(grafo->arco);
        printf ("\n");
    }
}

void alist (a_t *arc) {
    while (arc) {
        adisplay(arc);
        arc = arc->prox;
    }
}

double dijkstra(v_t *graph,char *orig,char *dest) {
    const int v_max = vertex_num(graph);
    double mindist[v_max],dist = 0.0;
    int visited[v_max],v_control = 0,inds[v_max];
    int way[v_max][v_max],aux2,adjacents,aux4;
    register int ctrl,crl2;
    char nomes[20];
    v_t *inicio = vseek(orig,graph);
    v_t *final = vseek(dest,graph);
    v_t *aux = graph;
    v_t *aux3;
    if (!inicio || !final) {
        printf ("Cidade inexistente detectada.\n");
        return 0.0;
    }
    for (ctrl=0;ctrl<v_max;ctrl++) {
        for (crl2=0;crl2<v_max;crl2++) way[ctrl][crl2] = 0;
        mindist[ctrl] = 10000000;
        visited[ctrl] = 0;
        inds[ctrl] = 0;
    }
    while (aux) {
        aux2 = get_index(aux->nome,graph);
        if (!weight(graph,inicio->nome,aux->nome) && mindist[aux2]) {
            mindist[aux2] = 10000000;
        }
        else {
            mindist[aux2] = weight(graph,inicio->nome,aux->nome);
        }
        way[aux2][inds[aux2]] = aux2;
        inds[aux2]++;
        aux = aux->prox;
        printf ("aux2 = %d\tinds[aux2] = %d\n",aux2,inds[aux2]);
    }
    mindist[get_index(orig,graph)] = 0;
    visited[get_index(orig,graph)] = 1;
    while (!all_visited(visited,v_max)) {
        aux = get_min_vertex (visited,mindist,v_max,graph);
        visited[get_index(aux->nome,graph)] = 1;
        adjacents = arest_num(aux);
        for (ctrl=0;ctrl<adjacents;ctrl++) {
            aux3 = adj_obtain(aux,ctrl); aux2 = get_index(aux->nome,graph); aux4 = get_index(aux3->nome,graph);
            if (mindist[aux4] > (mindist[aux2]+weight(graph,aux->nome,aux3->nome))) {
                mindist[aux4] = mindist[aux2]+weight(graph,aux->nome,aux3->nome);
                way[aux4][inds[aux4]++] = aux2;
                inds[aux4]++;
            }
        }
    }
    aux4 = get_index(dest,graph); dist = mindist[aux4];
    printf ("Caminho: %s",orig);
    for (ctrl=inds[aux4]-1;ctrl>-1;ctrl--) {
        get_vertex(nomes,way[aux4][ctrl],graph);
        printf ("->%s",nomes);
    }
    printf ("\n");
    return dist;
}

double weight (v_t *graph,char *orig,char *dest) {
    double res = 0.0;
    if (!vseek(orig,graph) || !vseek(dest,graph)) return 0;
    v_t *partida = vseek(orig,graph);
    a_t *aux = partida->arco;
    while (aux) {
        if (!strcmp(dest,aux->ponta->nome)) res = aux->dist;
        aux = aux->prox;
    }
    return res;
}

int arest_num (v_t *vertex) {
    int num = 0;
    a_t *list = vertex->arco;
    while (list) {
        num++;
        list = list->prox;
    }
    return num;
}

int vertex_num (v_t *graph) {
    int num = 0;
    v_t *aux = graph;
    while (aux) {
        num++;
        aux = aux->prox;
    }
    return num;
}

v_t *adj_obtain (v_t *vertex,int position) {
    a_t *list = vertex->arco;
    v_t *adj = NULL;
    register int ctrl;
    for (ctrl=0;ctrl<position && list;ctrl++) list = list->prox;
    adj = list->ponta;
    return adj;
}

int get_index(char *name,v_t *graph) {
    const int max = vertex_num(graph);
    register int ctrl;
    char cities[max][20];
    v_t *aux = graph;
    for (ctrl = 0;ctrl<max;ctrl++) {
        strcpy(cities[ctrl],aux->nome);
        if (!strcmp(cities[ctrl],name)) return ctrl;
        aux = aux->prox;
    }
    return -1;
}

void get_vertex (char *name,int index,v_t *graph) {
    const int max = vertex_num(graph);
    register int ctrl;
    char cities[max][20];
    char result[20];
    v_t *aux = graph;
    if (index<0 || index>=max) return;
    for (ctrl = 0;ctrl<max;ctrl++) {
        strcpy(cities[ctrl],aux->nome);
        aux = aux->prox;
    }
    strcpy (name,cities[index]);
}

int all_visited(int *visitedarray,int size) {
    register int ctrl;
    for (ctrl=0;ctrl<size;ctrl++) {
        if (!visitedarray[ctrl]) return 0;
    }
    return 1;
}

v_t *get_min_vertex (int *visited,double *distances,int size,v_t *graph) {
    v_t *result;
    register int ctrl;
    int index;
    char name[20];
    double min = 10000000;
    for (ctrl=0;ctrl<size;ctrl++) {
        if ((distances[ctrl]<min) && !visited[ctrl]) {
            min = distances[ctrl];
            index = ctrl;
        }
    }
    get_vertex(name,index,graph);
    result = vseek(name,graph);
    return result;
}

double dij (v_t *graph,char *orig,char *dest) {
    int v_max = vertex_num (graph);
    char cidade_atual[20];
    double min_control;
    int min_index;
    v_t **prior = (v_t **) malloc (sizeof(v_t[v_max]));
    double result = 0.0;
    double mindist[v_max];
    v_t *atual = vseek(orig,graph);
    v_t *final = vseek(dest,graph);
    v_t *aux;
    int visited[v_max];
    double dist_atual,nova_distancia;
    register int ctrl;
    for (ctrl=0;ctrl<v_max;ctrl++) {
        mindist[ctrl] = 99999;
        visited[ctrl] = 0;
    }
    visited[get_index(atual->nome,graph)] = 1;
    mindist[get_index(atual->nome,graph)] = 0;

    while (strcmp(atual->nome,dest)) {
        dist_atual = mindist[get_index(atual->nome,graph)];
        for (ctrl=0;ctrl<arest_num(atual);ctrl++) {
            aux = adj_obtain(atual,ctrl);
            nova_distancia = dist_atual + weight(graph,atual->nome,aux->nome);
            if (nova_distancia<mindist[get_index(aux->nome,graph)]) {
                mindist[get_index(aux->nome,graph)] = nova_distancia;
                prior[get_index(aux->nome,graph)] = atual;
            }
        }
        min_control = 99999;
        for (ctrl=0;ctrl<v_max;ctrl++) {
            if (mindist[ctrl]<min_control) {
                min_control = mindist[ctrl];
                min_index = ctrl;
            }
        }
        atual = get_min_vertex(visited,mindist,v_max,graph);
        visited[get_index(atual->nome,graph)] = 1;
    }
    result = mindist[get_index(dest,graph)];
    imprime_rota(final,prior,graph);
    printf ("\n");
    return result;
}

void imprime_rota (v_t *final,v_t **precedences,v_t *grafo) {
    v_t *atual = final;
    if (atual) {
        imprime_rota(precedences[get_index(atual->nome,grafo)],precedences,grafo);
        if (precedences[get_index(atual->nome,grafo)]) printf ("->");
        printf ("%s",atual->nome);
    }
}