/******************************************************************************************************************/
/* Programma per Calcolare il percorso piu' breve tra una coppia di vertici del grafo specificata dall'utente */
/* e per calcolare una serie di statistiche sulle distanze dei percorsi piu' brevi tra tutte le coppie di vertici */
/* Del Grafo */
/******************************************************************************************************************/
/***************************/
/* Autore: Luca Mencarelli */
/***************************/
/*****************************/
/* Inclusione delle Librerie */
/*****************************/
#include <stdio.h> /* Inclusione della libreria standard indispesabile per le operazioni di input-output */
#include <string.h> /* Inclusione della libreria per la gestione dei dati di tipo stringa */
/*****************************************/
/* Definizione delle costanti simboliche */
/*****************************************/
/* Le costanti MAX_ARCHI e MAX_VERTICI definiscono la capacita' massima della matrice dei pesi degli archi.
Si assume per scelta di progetto che il numero degli archi e dei vertici non superi 100. */
#define MAX_ARCHI 100
#define MAX_VERTICI 100
/************************/
/* Definizione dei tipi */
/************************/
/* Struttura dati per la descrizione dei vertici */
typedef struct vertice
{
char nome_vertice[10];
} vertice_t;
/* Struttura dati per memorizzare i totali: archi e vertici */
typedef struct dati
{
int numero_vertici;
int numero_archi;
} dati_t;
/* Struttura dati che contiene tutti dati ma come interi e 8 */
typedef struct arco
{
float peso; /* peso dell'arco */
int vertice_partenza; /* vertice di partenza */
int vertice_destinazione; /* vertice di arrivo */
} arco_t;
/********************************/
/* Dichiarazione delle funzioni */
/********************************/
/* Dichiarazione della funzione per Inizializzare il vettore dei tragitti */
void inizializza_vettore(vertice_t [MAX_VERTICI]);
/* Dichiarazione della funzione di caricamento da file della matrice pesi*/
dati_t carica_file(arco_t voli[MAX_ARCHI], vertice_t vettore_vertice[MAX_VERTICI]);
/* Dichiarazione della funzine per la codifica della vertice */
int codifica_vertice(char [8], vertice_t[MAX_VERTICI]);
/* Dichiarazione della funzione
per inizializzare la matrice dei tragitti precedenti */
void inizializza_matrice_precedenti(int [MAX_VERTICI][MAX_VERTICI], int);
/* Dichiarazione della funzione per iniziallizzare a 999 le matrici */
void azzera_matrice(float [MAX_VERTICI][MAX_VERTICI], int );
/* Dichiarazione della funzione per caricare le matrici */
void carica_matrice(float [MAX_VERTICI][MAX_VERTICI], arco_t [MAX_ARCHI], dati_t);
/* Dichiarazione della funzione Recupera Codice vertice */
int recupera_codice_vertice(char [8],vertice_t[MAX_VERTICI]);
/* Dichiarazione della funzione Floyd Warshall
per il calcolo dei percorsi migliori in basei al peso del volo */
void floyd_warshall_pesi(int , int [MAX_VERTICI][MAX_VERTICI],
float [MAX_VERTICI][MAX_VERTICI]);
/* Dichiarazione della funzione che carica il traggito
in base al peso del volo */
int carica_tragitto_peso(int,int,arco_t [MAX_ARCHI],
int [MAX_VERTICI][MAX_VERTICI],
float [MAX_VERTICI][MAX_VERTICI]);
/* Dichiarazione della funzione Stampa scali */
void stampa_pesi(arco_t [MAX_ARCHI], int, vertice_t [MAX_ARCHI]);
int uscita_programma(void);
/* Definizione della funzione main */
int main(void)
{
/* Dichiarazione delle variabili locali alla funzione */
float pesi[MAX_VERTICI][MAX_VERTICI]; /* Matrice che identifica il
peso del volo in euro */
int prec_pesi[MAX_VERTICI][MAX_VERTICI]; /* Matrice dei precedenti i
n base ai pesi*/
arco_t archi[MAX_ARCHI]; /* Vettore voli per la
memorizzazione dei voli
caricati da file */
vertice_t vettore_vertice[MAX_VERTICI]; /* Vettore per la codifica
della vertice */
dati_t dati; /* Variabile di appoggio */
int esci = 0; /* Variabile per uscire
dal programma */
int peso_archi = 0; /* Variabile che valorizza
gli scali in base
al peso del volo */
char desc_partenza[10]; /* Variabile per la descrizione
della vertice di partenza */
char desc_arrivo[10]; /* Variabile per la descrizione
della vertice di arrivo */
int cod_partenza = 0; /* Variabile per il codice
della vertice di partenza */
int cod_arrivo = 0; /* Variabile per il codice
della vertice di arrivo */
arco_t tragitto_pesi[MAX_ARCHI]; /* Vettore che identifica
il tragitto
in base al peso dell'arco */
char scelta[4]; /* Variabile che serve per scegliere
se uscire dal programma
oppure no */
inizializza_vettore(vettore_vertice); /* Chiamata alla funzione
Inizializza Vettore */
dati = carica_file(archi, vettore_vertice); /* Chiamata alla funzione per
il caricamento dati dal file */
/* Ciclo while per la richiesta all'utente delle vertice del volo */
while (esci == 0)
{
printf("-------------------------------------\n");
printf("| BENVENUTI NEL PROGRAMMA DEI GRAFI |\n");
printf("-------------------------------------\n");
/* Inizializzazione della matrice dei percorsi precedenti */
inizializza_matrice_precedenti(prec_pesi, dati.numero_vertici);
/* Inizializzazione a 999 (infinito) delle Matrici dei pesi e dei tempi */
azzera_matrice(pesi,dati.numero_vertici);
/* Caricamento dei dati dei voli nelle matrici pesi e tempi */
carica_matrice(pesi,archi,dati);
/* Richiesta all'utente della vertice' di partenza */
printf("\n Inserisci la vertice di partenza: ");
scanf("%s",desc_partenza);
/* Richiesta all'utente della vertice' di arrivo */
printf("\n Inserisci la vertice di arrivo : ");
scanf("%s",desc_arrivo);
/* Recupero codici delle vertice*/
cod_partenza = recupera_codice_vertice(desc_partenza,vettore_vertice);
cod_arrivo = recupera_codice_vertice(desc_arrivo,vettore_vertice);
/* Chiama l'ottimizzazione dei pesi*/
floyd_warshall_pesi(dati.numero_vertici,prec_pesi,pesi);
/* Carica il caricamento dei tragitti */
peso_archi = carica_tragitto_peso(cod_partenza,cod_arrivo,
tragitto_pesi,prec_pesi,pesi);
if(peso_archi == 0)
{
printf("\n Il percorso non e' disponibile");
}
else
{
/* Stampa finale degli scali in base ai pesi*/
printf("\n ** Stampa percorsi ** \n");
stampa_pesi(tragitto_pesi,peso_archi,vettore_vertice);
}
do
{
printf("\n\n Vuoi uscire ? (si/no) : ");
scanf("%s", scelta);
if(strcmp(scelta, "si") == 0)
{
esci = 1;
}
else
{
esci = 0;
}
if(strcmp(scelta, "si") != 0 && strcmp(scelta, "no") != 0)
{
printf("\nATTENZIONE PAROLA SBAGLIATA RIPROVA!!!\n");
}
}while(strcmp(scelta, "si") != 0 && strcmp(scelta, "no") != 0);
}
/* Termina il programma e restituisco il valore 0 al Sistema Operativo */
return(0);
}
/* Definizione della funzione per Inizializzare il vettore dei traggitti */
void inizializza_vettore(vertice_t vettore_vertice[MAX_VERTICI])
{
int i = 0;
/* Ciclo per inizializzare il vettore */
for (i = 0; i < MAX_VERTICI; i++)
{
/* Copia la stringa "nessuno" */
strcpy(vettore_vertice[i].nome_vertice, "nessuno");
}
}
/* Definizione della funzione di caricamento da file della matrice pesi*/
dati_t carica_file(arco_t archi[MAX_ARCHI], vertice_t vettore_vertice[MAX_VERTICI])
{
/* Dichiarazione delle variabili locali alla funzione */
int numero_vertici = 0;
/* Variabile per memorizzare il ritorno della fscanf in base al tipo di dati letto */
int n_vertici_raggiungibili = 0; /* numero dei vertici raggiungibili */
FILE *fp;
dati_t dati; /* Varibile di tipo struttura dati_t */
char vertice_tmp[10]; /* Variabile temporanea che prende il nome del vertice */
int i = 0,
j = 0; /* Variabili di controllo per il ciclo for */
int indice_vettore = 1; /* Indice del vettore */
int esci = 0; /* Uscita dal programma dopo il messaggio di errore di apertura del file */
char scelta[3]; /* Variabile per scegliere di uscire dal programma */
do
{
/* Apertura file dati */
fp = fopen("./dati.in", "r");
if (fp == NULL)
{
printf("\nImpossibile aprire il file di testo vdati.in!\n");
printf("\nControllare che il file esista nella stessa cartella in cui si esegue il programma\n");
esci = 1;
uscita_programma();
}
else
{
/* Lettura del numero di aeroporti, posizionato nella prima riga del file */
fscanf(fp, "%d", &numero_vertici);
dati.numero_vertici = numero_vertici;
/* Doppio ciclo di lettura del file per memorizzare i dati
nel vettore voli: primo in base al numero vertice e secondo per i voli
della vertice del blocco corrispondente*/
for (i = 1; i <= numero_vertici; i++)
{
if(fscanf(fp, "%d", &n_vertici_raggiungibili) == 1)
{
for (j = 1; j <= n_vertici_raggiungibili; j++)
{
if(fscanf(fp, "%s", vertice_tmp) == 1)
{
/* Legge con fscanf e poi memorizza i dati nel vettore */
archi[indice_vettore].vertice_partenza =
codifica_vertice(vertice_tmp, vettore_vertice);
}
if(fscanf(fp, "%s", vertice_tmp) == 1)
{
archi[indice_vettore].vertice_destinazione =
codifica_vertice(vertice_tmp, vettore_vertice);
}
if(fscanf(fp, "%f", &archi[indice_vettore].peso) == 1)
{
indice_vettore++;
}
}
}
}
}
}while(esci = 0);
fclose(fp);
dati.numero_archi = indice_vettore;
return dati;
}
/* Definizione della funzine per la codifica della vertice */
int codifica_vertice(char vertice_tmp[10], vertice_t vettore_vertice[MAX_VERTICI])
{
/* Dichiarazione delle variabili locali alla funzione */
int trova_vertice = 1;
int i = 0; /* indice per il ciclo */
while(trova_vertice == 1)
{
i++;
if(strcmp(vertice_tmp, vettore_vertice[i].nome_vertice) == 0)
{
trova_vertice = 0;
}
else if(strcmp(vettore_vertice[i].nome_vertice, "nessuno") == 0)
{
strcpy(vettore_vertice[i].nome_vertice, vertice_tmp);
trova_vertice = 0;
}
}
return i;
}
/* Definizione della funzione per inizializzare la matrice dei tragitti precedenti */
void inizializza_matrice_precedenti(int precedenti[MAX_VERTICI][MAX_VERTICI], int n)
{
int i = 0,
j = 0;
for (i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
{
precedenti[i][j] = i;
}
}
}
/* Definizione della funzione per iniziallizzare a zero le matrici */
void azzera_matrice(float pesi[MAX_VERTICI][MAX_VERTICI], int n)
{
/* Dichiarazione delle variabili locali alla funzione */
int i = 0,
j = 0;
for (i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
{
/* Mette a infinito*/
pesi[i][j] = 999;
if (i==j)
{
/* Mette a zero partenza = destinazione*/
pesi[i][j] = 0;
}
}
}
}
/* Definizione della funzione per caricare le matrici */
void carica_matrice(float pesi[MAX_VERTICI][MAX_VERTICI],
arco_t archi[MAX_ARCHI],dati_t dati)
{
/* Dichiarazione delle variabili locali alla funzione */
int i = 0;
/* Scorre i voli per caricare le matrici di adiacenza */
for (i = 1; i <= dati.numero_archi; i++)
{
pesi[archi[i].vertice_partenza][archi[i].vertice_destinazione] = archi[i].peso;
}
}
/* Definizione della funzione Recupera Codice vertice */
int recupera_codice_vertice(char vertice_tmp[8],vertice_t vettore_vertice[MAX_VERTICI])
{
/* Dichiarazione delle variabili locali alla funzione */
int trova_vertice = 1; /* Varabile che testa l'uscita dal while */
int i = 0; /* Variabile di indice */
/* Cilco per trovare la vertice e ritorno il codice*/
while(trova_vertice == 1)
{
i++;
/* Confronta il vettore con la stringa*/
if(strcmp(vertice_tmp, vettore_vertice[i].nome_vertice) == 0)
{
trova_vertice = 0;
}
else if(strcmp(vettore_vertice[i].nome_vertice, "nessuno") == 0)
{ /* Se vuoto è finito il vettore*/
trova_vertice = 0;
i = 0;
}
}
return i;
}
/* Definizione della funzione Floyd Warshall per il calcolo dei percorsi migliori in base al peso dell'arco */
void floyd_warshall_pesi(int n, int prec_pesi[MAX_VERTICI][MAX_VERTICI],
float pesi[MAX_VERTICI][MAX_VERTICI])
{
/* Dichiarazione variabili locali alla funzione */
int i = 0,
j = 0, /* Indici per l'ottimizzazione della matrice del peso dell'arco */
k = 0;
/* Ciclo per passo k*/
for (k = 1; k <= n; ++k)
{
for (i = 1; i <= n; ++i)
{
for (j = 1; j <= n; ++j)
{
/* Testo se i e j sono vertici diversi
e se il peso tra il vertice i e k e tra k e j
e' diverso da 999 cioe' esiste il percorso*/
if ((pesi[i][k] != 999) && (pesi[k][j]!= 999) && (i != j))
{
/* Se il peso da i a j passando per k, quindi i->k + k->j
e' minore del peso da i a j oppure se il peso da i a j = 0
allora sostituisco il peso da i a j con quello passando per k */
if ((pesi[i][k] + pesi[k][j] < pesi[i][j]) ||(pesi[i][j] == 999))
{
/* Aggiorno il peso migliore, il percorso e i tempi */
pesi[i][j] = pesi[i][k] + pesi[k][j];
prec_pesi[i][j] = prec_pesi[k][j];
}
}
}
}
}
}
/* Definizione della funzione che carica il tragitto in base al peso del volo */
int carica_tragitto_peso(int cod_partenza,int cod_arrivo,
arco_t tragitto_pesi[MAX_ARCHI],
int prec_pesi[MAX_VERTICI][MAX_VERTICI],
float pesi[MAX_VERTICI][MAX_VERTICI])
{
/* Dichiarazione delle variabili locali alla funzione */
int i = 0;
int precedente = 0;
int infinito = 0;
int partenza = cod_partenza;
int destinazione = cod_arrivo;
/* Ciclo while per recuperare il percorso degli scali*/
while (destinazione != partenza && (partenza != 0) && (destinazione != 0)
&& infinito == 0)
{
i++;
/* Uso il vertice precedente per recuperare i dati dei pesi e dei tempi*/
precedente = prec_pesi[partenza][destinazione];
tragitto_pesi[i].vertice_partenza = precedente;
tragitto_pesi[i].vertice_destinazione = destinazione;
tragitto_pesi[i].peso = pesi[partenza][destinazione];
if (i > 1)
{
/*Se è il secondo giro aggiorno il peso valorizzato in precedenza */
tragitto_pesi[i-1].peso = tragitto_pesi[i-1].peso - tragitto_pesi[i].peso;
}
destinazione = precedente;
/* Il percorso non esiste perchè ha peso infinito */
if (tragitto_pesi[i].peso == 999)
{
i = 0;
infinito = 1;
}
}
return i;
}
/* Definizione della funzione Stampa scali */
void stampa_pesi(arco_t tragitto_pesi[MAX_ARCHI],
int pesi,vertice_t vettore_vertice[MAX_VERTICI])
{
/* Dichiarazione delle variabili locali alla funzione */
int i; /* Variabile di indicizzazione */
float peso_totale = 0; /* Variabile per indicare il peso totale del volo */
/* Ciclo For per stampare gli eventuali pesi precendeti, vado a ritroso per ricostruire il
percorso*/
for (i = pesi; i >= 1; i--)
{
printf("\nDa %s --> a %s con peso %.1f",
vettore_vertice[tragitto_pesi[i].vertice_partenza].nome_vertice,
vettore_vertice[tragitto_pesi[i].vertice_destinazione].nome_vertice,
tragitto_pesi[i].peso);
peso_totale = peso_totale + tragitto_pesi[i].peso;
}
printf("\n\n peso totale = %.1f", peso_totale);
}
int uscita_programma(void)
{
return -1;
}