#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
#include <string.h>
#include "Graph.h"
#include "List.h"
#include "Queue.h"
Graph initGraph(int nodes_count, char** cityNames) {
Graph G = (Graph)malloc(sizeof(struct TGraph));
assert(G != NULL);
G->adj = (List *)calloc(nodes_count, sizeof(List));
assert(G->adj != NULL);
G->nodes_count = nodes_count;
G->cityNames = cityNames;
return G;
}
void freeGraph(Graph G) {
if (G != NULL) {
if (G->nodes_count > 0) {
int i = 0;
for (i = 0; i < G->nodes_count; i++) {
freeList(G->adj[i]);
}
}
free(G);
}
}
void printGraphAux(Graph G) {
if (G != NULL) {
int x = 0;
for (x = 0; x < G->nodes_count; x++) {
printf("(city: %s, id:%d) ", G->cityNames[x], x);
printList(G->adj[x]);
printf("\n");
}
}
}
void printGraph(Graph G) {
printGraphAux(G);
printf("\n\n");
}
void addEdge(Graph G, int source, int target, int peso) {
assert(G != NULL);
assert(source < G->nodes_count);
assert(target < G->nodes_count);
if (source != target) {
G->adj[source] = appendNodeList(G->adj[source], target, peso);
}
}
List removeEdge(Graph G, int source, int target) {
assert(G != NULL);
assert(source < G->nodes_count);
assert(target < G->nodes_count);
if (source != target) {
G->adj[source] = removeNodeList(G->adj[source], target);
}
return G->adj[source];
}
void addNode(Graph G, char* newCity) {
if (G != NULL) {
List * old=G->adj;
char** old_matrix = G->cityNames;
int i=0;
G->adj = (List *)calloc(G->nodes_count+1, sizeof(List));
assert(G->adj != NULL);
G->cityNames = (char**)calloc(G->nodes_count+1, sizeof(char*));
assert(G->cityNames != NULL);
for(i=0;i<G->nodes_count;i++){
G->adj[i]=old[i];
G->cityNames[i] = old_matrix[i];
}
G->nodes_count += 1;
G->adj[G->nodes_count-1] = NULL;
G->cityNames[G->nodes_count-1] = (char*) calloc(strlen(newCity)+1, sizeof(char));
assert(G->cityNames[G->nodes_count-1] != NULL);
strcpy(G->cityNames[G->nodes_count-1], newCity);
}
}
void removeNode(Graph G, int node_to_remove) {
if (G != NULL) {
int i = 0;
int x = 0;
List *tmp = G->adj;
char** old_matrix = G->cityNames;
G->adj = (List *)calloc(G->nodes_count-1, sizeof(List));
assert(G->adj != NULL);
G->cityNames = (char**)calloc(G->nodes_count-1, sizeof(char*));
assert(G->cityNames != NULL);
for (i = 0; i < G->nodes_count; i++) {
if (i != node_to_remove) {
G->adj[x] = checkListRemoval(tmp[i], node_to_remove);
G->cityNames[x] = old_matrix[i];
x++;
} else {
free(old_matrix[i]);
freeList(tmp[i]);
}
}
free(tmp);
free(old_matrix);
G->nodes_count -= 1;
}
}
List checkListRemoval(List L, int node_to_remove) {
if (L != NULL) {
L->next = checkListRemoval(L->next, node_to_remove);
if (L->target == node_to_remove) {
List tmp = L->next;
free(L);
return tmp;
} else if (L->target > node_to_remove) {
L->target -= 1;
}
}
return L;
}
List bfs(Graph G, int source, int target){
assert(G != NULL); // controllo che il grafo non sia nullo
assert(source < G->nodes_count || target < G->nodes_count); // controllo che i vertici inseriti appartengano al grafo
Queue Q = initQueue();
int* visit_path = (int*)calloc(G->nodes_count, sizeof(int));
assert(visit_path != NULL);
int* current_weight = (int*) calloc(G->nodes_count, sizeof(int));
assert (current_weight != NULL);
// calloc inizializza gli interi a zero, che nella enum corrisponde a WHITE
GraphColor* visited = (GraphColor*) calloc(G->nodes_count, sizeof(GraphColor));
assert(visited != NULL);
enqueue(Q, source);
visited[source] = BLACK;
// il nodo di partenza e' raggiungibile da se stesso con un percoso nullo
visit_path[source] = source;
current_weight[source] = 0;
int target_found = 0;
int v;
while(!isEmptyQueue(Q) && !target_found){
// non occorre controllare che la coda abbiamo terminato l'operazione correttamente
// dato che in questo punto del codice sicuramente non e' vuota;
dequeue(Q, &v);
for(List iter = G->adj[v]; iter != NULL; iter = iter->next){
if(visited[iter->target] == WHITE){
enqueue(Q, iter->target);
// segno di aver visitato il vertice in cui termina l'arco
visited[iter->target] = BLACK;
// segno che il vertice in questione e' raggiungibile con un arco partendo dal vertice v
visit_path[iter->target] = v;
// bcalcolo il peso del percorso
current_weight[iter->target] = current_weight[v] + iter->peso;
if(iter->target == target){
target_found = 1;
break;
}
}
}
}
freeQueue(Q);
List path = NULL;
if(target_found != 0) {
// genera il percorso da source a target(se presente) e lo inserisce in una lista
path = generatePath(visit_path, current_weight, source, target);
}
free(visited);
free(visit_path);
free(current_weight);
return path;
}
List dijkstra(Graph G, int source, int target){
assert(G != NULL); // controllo che il grafo non sia nullo
assert(source < G->nodes_count || target < G->nodes_count); // controllo che i vertici inseriti appartengano al grafo
Queue Q = initQueue();
int* visit_path = (int*)calloc(G->nodes_count, sizeof(int));
assert(visit_path != NULL);
// a differenza dell bfs, dijkstra deve tenere traccia anche del peso dei percorsi finora analizzati
int* current_weight = (int*) calloc(G->nodes_count, sizeof(int));
assert(current_weight != NULL);
// calloc inizializza gli interi a zero, che nella enum corrisponde a WHITE
GraphColor* visited = (GraphColor*) calloc(G->nodes_count, sizeof(GraphColor));
assert(visited != NULL);
enqueue(Q, source);
visited[source] = BLACK;
// il nodo di partenza e' raggiungibile da se stesso con un percoso nullo
visit_path[source] = source;
current_weight[source] = 0; // questa assegnazione e' inutile ma rende piu' semplice da capire l'algoritmo
int target_found = 0;
int v;
while(!isEmptyQueue(Q)){
// non occorre controllare che la coda abbiamo terminato l'operazione correttamente
// dato che in questo punto del codice sicuramente non e' vuota;
dequeue(Q, &v);
for(List iter = G->adj[v]; iter != NULL; iter = iter->next){
if(visited[iter->target] == WHITE){
enqueue(Q, iter->target);
// segno di aver visitato il vertice in cui termina l'arco
visited[iter->target] = BLACK;
// segno che il vertice in questione e' raggiungibile con un arco partendo dal vertice v
visit_path[iter->target] = v;
// calcolo il peso del percorso
current_weight[iter->target] = current_weight[v] + iter->peso;
if(iter->target == target){
target_found = 1;
}
}else if(visited[iter->target] == BLACK && (current_weight[iter->target] > current_weight[v] + iter->peso)){
// nel caso un vertice venga raggiunto da un percorso "piu' leggero", cambio il predecessore, ed il peso, del nodo in questione
visit_path[iter->target] = v;
current_weight[iter->target] = current_weight[v] + iter->peso;
}
}
}
freeQueue(Q);
List path = NULL;
if(target_found != 0){
// genera il percorso da source a target(se presente) e lo inserisce in una lista
path = generatePath(visit_path, current_weight, source, target);
}
free(visited);
free(visit_path);
free(current_weight);
return path;
}
List generatePath(int* visit_info, int* weight_info, int source, int target){
if(source == target){
return initNodeList(source, weight_info[source]);
}else{
List path = generatePath(visit_info, weight_info, source, visit_info[target]);
path = appendNodeList(path, target, weight_info[target]);
return path;
}
}
int getCityIndexByName(Graph G, char* key){
assert(G != NULL);
assert(G->cityNames != NULL);
int index = -1;
int i;
for(i=0; i<G->nodes_count; i++){
if(!strcmp(G->cityNames[i], key)){
index = i;
break;
}
}
return index;
}
int getCityIndex(Graph G, char* message){
int choice;
do{
printf("\nMete disponibili:\n");
for(int i=0; i<G->nodes_count; i++){
printf("Nome: %s, id: %d\n", G->cityNames[i], i);
}
printf("\nSeleziona una meta di %s:", message);
scanf("%d", &choice);
if(choice < 0 || choice >= G->nodes_count){
printf("Scelta non valida.\n");
}
}while(choice < 0 || choice >= G->nodes_count);
return choice;
}
