Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
/**
* 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
You can’t perform that action at this time.