#include #include #include #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;ctrlnome,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;ctrlnome,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;ctrlprox; 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;ctrlnome); 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;ctrlnome); aux = aux->prox; } strcpy (name,cities[index]); } int all_visited(int *visitedarray,int size) { register int ctrl; for (ctrl=0;ctrlnome,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;ctrlnome,aux->nome); if (nova_distancianome,graph)]) { mindist[get_index(aux->nome,graph)] = nova_distancia; prior[get_index(aux->nome,graph)] = atual; } } min_control = 99999; for (ctrl=0;ctrlnome,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); } }