This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Esercitazione di Laboratorio: Tecniche e Linguaggi di Programmazione | |
* III Facoltà di Ingegneria: Ingegneria dell'Informazione | |
* Politecnico di Torino, a.a. 2009/2010 | |
* | |
* Copyright (C) 2009 Andrea Turso | |
* | |
* This program is free software: you can redistribute it and/or modify | |
* it under the terms of the GNU General Public License as published by | |
* the Free Software Foundation, either version 3 of the License, or | |
* (at your option) any later version. | |
* | |
* This program is distributed in the hope that it will be useful, | |
* but WITHOUT ANY WARRANTY; without even the implied warranty of | |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
* GNU General Public License for more details. | |
* | |
* You should have received a copy of the GNU General Public License | |
* along with this program. If not, see <http://www.gnu.org/licenses/>. | |
* | |
* @license GNU/GPLv3 http://www.gnu.org/licenses/gpl.txt | |
* @author Andrea Turso <trashofmasters@gmail.com> | |
*/ | |
#include <stdio.h> | |
/** COSTANTI */ | |
#define _MAX_NUMBER_OF_CITIES 50 | |
#define _UNDEFINED_DISTANCE -1 | |
/** PROTOTIPI */ | |
/** | |
* Struttura per le citta | |
* | |
* Incapsula in un'unica variabile id e posizione della citta' | |
* | |
* @var int id Id della citta | |
* @var int x Posizione della citta sull'asse x | |
* @var int y Altezza della citta rispetto all'asse x | |
*/ | |
typedef struct City { | |
int id; | |
int x; | |
int y; | |
} City; | |
/** | |
* Struttura per gli achi del grafo | |
* | |
* Incapsula in un unica variabile la citta di partenza e di | |
* destinazione insieme al peso dell'arco tra le due citta. | |
* | |
* @var City* source Citta di partenza | |
* @var City* target Citta di destinazione | |
* @var float weight Peso dell'arco, o distanza tra source e target | |
*/ | |
typedef struct Arch { | |
City *source; | |
City *target; | |
float weight; | |
} Arch; | |
/** | |
* findBestPathFromACityToTheNext | |
* | |
* Maggiori dettagli nell'implementazione. | |
* | |
* @param City* | |
* @param City* | |
*/ | |
void findBestPathFromACityToTheNext(City*, City*); | |
/** | |
* distance | |
* | |
* Maggiori dettagli nell'implementazione. | |
* | |
* @param City* | |
* @param City* | |
*/ | |
float distance(City*, City*); | |
/** | |
* inputNumberOfCities | |
* | |
* Maggiori dettagli nell'implementazione. | |
* | |
*/ | |
int inputNumberOfCities(); | |
/** | |
* inputCities | |
* | |
* Maggiori dettagli nell'implementazione. | |
* | |
* @param City* | |
* @param int | |
*/ | |
void inputCities(City*, int); | |
/** | |
* inputInitialCity | |
* | |
* Maggiori dettagli nell'implementazione. | |
* | |
* @param City* | |
* @param int | |
*/ | |
City *inputInitialCity(City*, int); | |
/** | |
* Funzione principale | |
* | |
*/ | |
int main() | |
{ | |
City *initialCity; | |
City cities[_MAX_NUMBER_OF_CITIES]; | |
int numberOfCities = 0; | |
for (int i = 0; i < _MAX_NUMBER_OF_CITIES; i++) { | |
cities[i].id = 0; | |
} | |
// Numero di citta che si vogliono inserire | |
numberOfCities = inputNumberOfCities(); | |
// Input delle citta | |
inputCities(cities, numberOfCities); | |
// Input della citta di partenza | |
initialCity = inputInitialCity(cities, numberOfCities); | |
// Outpt del percorso minimo per percorrere tutte le citta | |
printf("Suggested path:\n"); | |
findBestPathFromACityToTheNext(cities, initialCity); | |
} | |
/** | |
* findBestPathFromACityToTheNext | |
* | |
* Calcola e visualizza passo-passo il percorso minimo | |
* necessario per percorrere tutte le città. | |
* | |
* Utilizza una versione ricorsiva dell'algoritmo di Dijkstra. | |
* | |
* @param City* Città da attraversare | |
* @param City* Città di partenza | |
*/ | |
void findBestPathFromACityToTheNext(City *cities, City *initialCity) | |
{ | |
// Città non definita | |
City undefinedCity = {.id=0, .x=0, .y=0}; | |
City *currentCity; | |
Arch arches[_MAX_NUMBER_OF_CITIES]; | |
// Controllo che la città sia definita | |
if (initialCity->id) { | |
printf("Visiting order - City %d\n", initialCity->id); | |
// Inizializza gli archi con un peso non definito | |
for (int i = 0; i < _MAX_NUMBER_OF_CITIES; i++) { | |
arches[i].source = &undefinedCity; | |
arches[i].target = &undefinedCity; | |
arches[i].weight = _UNDEFINED_DISTANCE; | |
} | |
// Calcola il peso degli archi tra la città corrente e quelle in prossimità | |
for (int i = 0; i < _MAX_NUMBER_OF_CITIES; i++) { | |
currentCity = &cities[i]; | |
if (currentCity->id) { | |
arches[i].source = initialCity; | |
arches[i].target = currentCity; | |
arches[i].weight = distance(initialCity, currentCity); | |
// Ordina gli archi in ordine crescente di peso | |
for (int j = 0; j < i; j++) { | |
if (arches[i].weight < arches[j].weight) { | |
Arch temp = arches[i]; | |
arches[i] = arches[j]; | |
arches[j] = temp; | |
} | |
} | |
} | |
} | |
// Annulla la città visitata, in modo che non venga rivalutata successivamente | |
for (int i = 0; i < _MAX_NUMBER_OF_CITIES; i++) { | |
if (cities[i].id == initialCity->id) { | |
cities[i].id = 0; | |
i = _MAX_NUMBER_OF_CITIES; | |
} | |
} | |
// Estrae il primo arco con peso > 0 dal vettore di archi e | |
// configura initialCity con la città puntata dall'arco | |
for (int i = 0; i < _MAX_NUMBER_OF_CITIES; i++) { | |
if (!(arches[i].weight == _UNDEFINED_DISTANCE || arches[i].weight == 0)) { | |
initialCity = arches[i].target; | |
i = _MAX_NUMBER_OF_CITIES; | |
} | |
} | |
// Riesegue la ricerca del percorso minimo a partire dalla città più vicina | |
findBestPathFromACityToTheNext(cities, initialCity); | |
} | |
} | |
/** | |
* distance | |
* | |
* Calcola la distanza di due città come distanza punto-punto | |
* nel piano ma non applica la radice quadrata. La distanza al | |
* quadrato è sufficiente per determinare quale città è più lontana | |
* | |
* Per calcolare la radice quadrata di distanceSquared è necessario | |
* includere math.h. | |
* | |
* @param City* source Città di partenza | |
* @param City* target Città di destinazione | |
*/ | |
float distance(City *source, City *target) | |
{ | |
float dx = (target->x - source->x); | |
float dy = (target->y - source->y); | |
float distanceSquared = (dx*dx) + (dy*dy); | |
return distanceSquared; | |
} | |
/** | |
* inputNumberOfCities | |
* | |
* Chiede all'utente l'inserimento del numero di città | |
* | |
* @return int | |
*/ | |
int inputNumberOfCities() | |
{ | |
int tmp; | |
// Filtro tmp > 0, tmp < _MAX_NUMBER_OF_CITIES | |
do { | |
printf("\nInput number of cities (%d-%d): ", 0, _MAX_NUMBER_OF_CITIES); | |
scanf("%d", &tmp); | |
} while (tmp < 1 || tmp > _MAX_NUMBER_OF_CITIES); | |
return tmp; | |
} | |
/** | |
* inputCities | |
* | |
* Chiede all'utente l'inserimento delle città insieme alla loro posizione | |
* | |
* @param City* cities Array delle città | |
* @param int numberOfCities Numero di città | |
*/ | |
void inputCities(City* cities, int numberOfCities) | |
{ | |
for (int i = 0; i < numberOfCities; i++) { | |
cities[i].id = i + 1; | |
printf("City #%d", i + 1); | |
printf("\tx coordinate: "); | |
scanf("%d", &cities[i].x); | |
printf("\ty coordinate: "); | |
scanf("%d", &cities[i].y); | |
} | |
} | |
/** | |
* inputInitialCity | |
* | |
* Chiede all'utente l'inserimento della città di partenza | |
* | |
* @param City* cities Array di città | |
* @param int numberOfCities Numero di città | |
* | |
* @return City* Città di partenza | |
*/ | |
City *inputInitialCity(City* cities, int numberOfCities) | |
{ | |
int tmp; | |
do { | |
printf("\nStarting city (%d-%d): ", 1, numberOfCities); | |
scanf("%d", &tmp); | |
} while (tmp > numberOfCities || tmp < 1); | |
return &cities[tmp - 1]; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment