gistfile1.h

/**
 * 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];
}