II UNIVERSITA' DEGLI STUDI DI ROMA

Tor Vergata

Corso di

Fondamenti di Informatica II

prof. Giovanni Cantone

The Best Way

Antonio D´Ottavio

Anno Accademico 1997/98

Introduzione

Il progetto “The Best Way” si propone di risolvere il problema classico della individuazione del percorso più breve che connette due città qualsiasi appartenenti ad un grafo, percorso che può essere diretto o indiretto nel caso in cui si arrivi alla città di destinazione passando per altre città diverse da quella di partenza.

Per realizzare l´obiettivo ci si appoggia alla classe The_Graph pertanto lo scopo della presente trattazione sarà evidenziare quelle che sono state le variazioni apportate a tale classe per adattarla alle finalità che “The_Best_Way” si propone.

Analisi compatibilità con la classe The_Graph.

Si è impostato il problema nella maniera che risulta intuitiva avendo a disposizione la classe The_Graph, in particolare, si sono evidenziate le seguenti relazioni di equivalenza :

The_Graph The_Best_Way

Vertice Località geografica

Arco Strada di interconnessione tra 2 località

Si noti che si è scelto l´implementazione dei grafi orientati in quanto può capitare che una data strada di interconnessione tra 2 città sia interrotta oppure vi sia una deviazione, pertanto la lunghezza della strada che connette 2 città dipende dal verso con il quale si percorre la stessa e non può essere implementata tramite un grafo non orientato.

Sfruttando le stesse funzioni disponibili per The_Graph si sono rapidamente implementate le seguenti funzionalità :

1) Inserzione di una citta'

2) Creazione di una strada

3) Visualizzazione della mappa

4) Determinazione del numero di citta'

5) Determinazione del numero di strade

6) Eliminazione di una strada

7) Eliminazione di una citta'

8) Eliminazione della mappa

L´unico adattamento che si è reso necessario è stata la creazione di un nuovo tipo di dato composito in grado di ospitare sia il nome della strada in una stringa che la sua lunghezza in un double, si è pertanto introdotta la String_Double_Obj , una classe che come le String_Obj , Char_Obj , Int_Obj e Double_Obj eredita dalla classe Element ed ospita in maniera protetta sia un double che una stringa accessibili quindi unicamente dalle member function della stessa classe.

Si noti che per le member function di questa classe si sono utilizzate dei nomi pertinenti al problema del minimo percorso al fine di rendere più leggibile il codice e la sua documentazione in quanto molte di queste member function nascono dalla necessità di accedere , modificare o testare i dati che ogni String_Double_Obj protegge.

Successivamente si è evidenziata la necessità di consentire la memorizzazione della mappa ed il suo ripristino da file in quanto la procedura di impostazione della mappa risulta essere lunga e ripetitiva tanto da renderla proibitiva nel caso in cui le città ad essa appartenenti siano molte. Si osservi ad esempio che per la sola inserzione di una strada a senso unico tra 2 città è necessario inserire i nomi della città sorgente e della città di destinazione, il nome della strada e la sua lunghezza, nonchè il tipo di dato per tutti questi attributi.

Si è infatti preferito non scendere nel dettaglio associando una stringa ai nomi delle città e delle strade ed un double alle lunghezze dei percorsi al fine di assecondare l´implicita genericità del problema dei minimi percorsi , il quale cioè si può presentare in altre forme che si differenziano unicamente per il tipo di dato trattato.

Tale problematica ha portato alla ridefinizione delle funzioni tramite le quali si impostavano i valori degli oggetti, nella fattispecie vi è stata una razionalizzazione del codice rispetto a quanto si aveva per la versione polimorfica di The_Graph, tale razionalizzazione consiste nella unificazione delle funzioni per l´impostazione delle variabili esterne, sono dunque scomparse dal main le funzioni Set_Source_Vertex_Name() , Set_Dest_Vertex_Name() e Set_Arc_Name sostituite dalla unica Set_Element_Name_Pointer() la quale riceve in ingresso il nome del puntatore da aggiornare ed anche lo stream dal quale attingere i dati pertanto si può utilizzare la stessa funzione sia che i dati vengano immessi da tastiera che nel caso in cui i dati vengano prelevati da un file.

Memorizzazione e ripristino della mappa da un file.

Le 2 funzioni sono naturalmente complementari e la definizione del protocollo per la realizzazione di una è inevitabilmente applicato anche alla seconda. Seguendo questa logica si è partiti dal cercare di capire cosa si vorrebbe prelevare da un file per ripristinare una mappa, e si è capito che dato che la mappa è unbounded, l´unico modo per ricrearla è prendere i dati memorizzati sul file e darli in ingresso alla stessa routine che si era utilizzata per la creazione della mappa.

Si assume quindi che non viene memorizzato il grafo ma soltanto i dati necessari alla sua ricostruzione pervenendo pertanto alla stesura del seguente protocollo di memorizzazione :

Tipo

dato Vertice

Nome

Vertice

n° archi uscenti

Tipo dato arco

Nome arco

Tipo dato Vertice Destinazione

Nome Vertice Destinazione

...

Tipo

dato Vertice

Nome

Vertice

n° archi uscenti

Tipo dato arco

Nome arco

Tipo dato Vertice Destinazione

Nome Vertice Destinazione

...

Quindi in sostanza ogni record del file contiene un vertice e tutti i suoi archi uscenti, comprensivi del tipo di dato in quanto si dovrà andare a ricostruire il giusto oggetto, pertanto le member function Save() delle classi String_Obj , Char_Obj , Int_Obj , Double_Obj e String_Double_Obj provvedono ad inserire prima della attributo rispettivamente le lettere S , C , I , D , K . Tale attributo sarà poi estratto dalla stessa funzione Type_Selection che abbiamo utilizzato anche per l´immissione del tipo di dato da tastiera.

Si noti che per lo String_Double_Obj il nome arco conterrà sia una stringa che il double ciascuno seguito da \t.

Questo tipo di memorizzazione consente di ricreare agevolmente prima i soli vertici e successivamente tramite un riposizionamento all´inizio del file ricreare l´intero grafo.

Ciò è reso necessario dal fatto che gran parte delle routine della classe The_Graph sono protette dall´immissione di dati non coerenti quale ad esempio la richiesta di creazione di una strada verso una città inesistente. In tal modo il problema viene risolto in quanto si legge il vertice tramite una getline con terminatore \t dopodiche si legge tutto il resto del record tramite una getline con terminatore \n , con il risultato che la prossima lettura dal file restituisce il nome del 2° vertice e così via.

Una volta che sono stati creati tutti i vertici si passa alla creazione del grafo che sostanzialmente consiste nell´estrarre il nome del vertice, tramite la Is_Member_Of ricavare un puntatore ad esso e poi ricostruire la lista degli archi uscenti tramite la Create_An_Arc applicata tante volte quanti sono gli archi uscenti dal singolo vertice.

Questo tipo di memorizzazione è implementata tramite gli operatori di estrazione << e di inserimento >> applicati al giusto buffer.

I dati vengono quindi memorizzati sotto forma di stringhe pertanto il ripristino della oggetto utilizza le funzioni di libreria atoi ed atof per la conversione da stringa al coerente tipo di dato.

Naturalmente poi le funzioni di salvataggio e di ripristino da file consentono all´utente di selezionare il nome del file su cui operare, ma tali routine per motivi di tempo non contengono i dovuti controlli sulle segnalazioni di errori che la libreria fstream mette a disposizione.

Calcolo delle distanze minime

Si è scelto di implementare la soluzione proposta da Dijkstra, essa infatti è in grado dato un grafo ed una città ad esso appartenente di ricavare le minime distanze tra questa città e tutte le altre città appartenenti al grafo, nonchè i nomi delle strade percorrendo le quali si può giungere alle mete. L´algoritmo è sostanzialmente il seguente :

Si ha una struttura dati nel quale si memorizzano i nomi di tutte le città con le relative distanze rispetto alla città di partenza, tale distanza è 0 per la città sorgente oppure il massimo numero previsto dal tipo di dato nel caso in cui non vi sia alcun collegamento diretto tra la città sorgente e la città di destinazione considerata, nel caso invece che esista un collegamento diretto si scrive la distanza in km di questo collegamento.

Si deve poi calcolare tra tutte le città appartenenti al grafo quella più vicina alla città di partenza, essa entrerà a far parte della insieme delle città visitate, quindi si debbono ricalcolare le distanze delle città collegate a quest´ultima scegliendo la minima tra la distanza precedentemente calcolata e la distanza ottenuta sommando il tratto tra la città sorgente e la città appena immessa nel set delle città visitate + la distanza tra quest´ultima e la città destinazione della arco.

Si procede calcolando ancora la più vicina tra le città non visitate e ricalcolando le distanze per gli archi da essa uscenti, il risultato è che quando tutte le città sono state visitate ogni città presenta la minima distanza rispetto alla città sorgente e se si è avuta la accortezza di tener nota delle variazioni dei percorsi, si avrà a disposizione anche il percorso corretto per giungere a destinazione.

Implementazione

Pur utilizzando anche in questo caso la classe The_Graph e le sue member functions, si rende necessario utilizzare una nuova struttura dati in grado di contenere tutte le città appartenenti al grafo e le informazioni circa la minima distanza dalla città sorgente ed il minimo percorso inteso come susseguirsi dei nomi delle strade. Inoltre si deve avere a disposizione un campo bool in cui memorizzare l´informazione se la città è già stata inserita nel set delle città visitate.

Sostanzialmente la struttura di cui si ha bisogno è una lista pertanto molte delle member function sono comuni anche alla Arc_List definita per The_Graph quindi sostanzialmente si è implementato un nuovo oggetto, il Town_Node il cui settore dati è esplicato dal seguente:

Destination Town

Min_Distance

Visited

Next_town

Town_Node.h

#include "String_Obj.h"

class Town_Node

{

friend class Town_List ;

friend class Graph ;

friend class Arc_Node ;

protected:

Gen_Data_Ptr Destination_Town ;

Gen_Data_Ptr Min_Distance ;

bool Visited ;

Town_Node *Next_Town ;

public:

void Display_Town();

Town_Node(Gen_Data_Ptr Town_Name);

Town_Node();

virtual ~Town_Node();

};

Town_Node.cpp

#include <float.h>

#include <iostream.h>

#include "Town_Node.h"

#include "String_Double_Obj.h"

Town_Node::Town_Node()

{

}

Town_Node::~Town_Node()

{

}

Town_Node::Town_Node(Gen_Data_Ptr Town_Name)

{

Destination_Town = Town_Name ;

Min_Distance = new String_Double_Obj("",DBL_MAX) ;

Next_Town = 0 ;

Visited = false ;

}

// viene visualizzata la singola città della lista

void Town_Node::Display_Town()

{

cout << "\n";

Destination_Town->Display();

cout << "\t\t";

Min_Distance->Display_The_Distance();

Min_Distance->Display_The_Way();

}

Si osservi che il campo Min_Distance è uno String_Double_Obj di cui il double viene utilizzato per memorizzare la distanza minima dalla città sorgente la quale viene aggiornata nel corso della elaborazione mentre la stringa viene utilizzata per memorizzare il percorso aggiornato.

String_Double_Obj.h

#include "String_Obj.h"

#include "Element.h"

class String_Double_Obj : public Element

{

public:

void Display_The_Distance();

void Init_Double_Val();

void Set_String_Val(char* String_Data);

void Display_The_Way();

void Adjourn_Min(Element* Ref_Min_Distance, Element* Arc_Distance);

bool Is_Lower_Double(Element* Element_Ptr);

void Init_String_Val(Element* Element_Ptr);

void Set_Double_Val(double Double_Data);

void Select_Min(Element * Element_Ptr);

void Set_Val(string String_Data, double Double_Data);

void Save(ofstream& Out_Buffer);

char* Get_String_Val();

double Get_Double_Val();

bool Is_Equal(Element* Element_ptr);

void Display();

String_Double_Obj(string String_Data, double Double_Data);

String_Double_Obj();

virtual ~String_Double_Obj();

protected:

string String_Value;

double Double_Value;

};

String_Double_Obj.cpp

#include <iostream.h>

#include <float.h>

#include "String_Double_Obj.h"

Questa classe è stata implementata al fine di contenere in un unico oggetto il nome della strada e

la sua lunghezza in km

String_Double_Obj::String_Double_Obj()

{

strcpy(My_Class, "String_Double_Obj");

}

String_Double_Obj::String_Double_Obj(string String_Data, double Double_Data)

{

strcpy(My_Class, "String_Double_Obj");

strcpy(String_Value,String_Data);

Double_Value = Double_Data;

}

String_Double_Obj::~String_Double_Obj()

{

}

// Mostra nome e lunghezza della strada

void String_Double_Obj::Display()

{

cout << String_Value << " (";

cout.width(6) ;

cout.setf(ios::right);

if(Double_Value == DBL_MAX)

cout << "Lavori";

else

cout << Double_Value;

cout << ") ";

}

// Mostra la sola lunghezza della strada

void String_Double_Obj::Display_The_Distance()

{

cout << " (";

cout.setf(ios::right);

cout.width(6) ;

if(Double_Value == DBL_MAX)

cout << "Lavori";

else

cout << Double_Value;

cout << ") ";

}

Naturalmente viene poi definito l´oggetto Town_List quale lista contenente tanti Town_Node quante sono le città appartenenti al grafo, nel main questo algoritmo è implementato dalla funzione Best_Way().

Town_List.h

#include "String_Obj.h"

class Town_List

{

friend class Town_Node;

friend class Graph;

protected:

Town_Node *Head;

public:

void Clear();

Gen_Data_Ptr Nearest_Not_Visited_Town(bool & The_End);

void Display_Only_Towns();

Town_Node* Is_Member_Of(Gen_Data_Ptr Town_Name);

void Insert(Gen_Data_Ptr Town_Name);

Town_List();

virtual ~Town_List();

};

Town_List.cpp

#include <iostream.h>

#include "Town_Node.h"

#include "Town_List.h"

Town_List::Town_List()

{

Head = 0;

}

Town_List::~Town_List()

{

}

// Inserisce una città nella lista delle minime distanze

void Town_List::Insert(Gen_Data_Ptr Town_Name)

{

if(Is_Member_Of(Town_Name))

{

cerr << "Questa città è già stata inserita. " << endl;

return;

}

Town_Node *Town_Node_Ptr ;

//Vertex_Node_Ptr punta ad un nuovo Vertex_Node

Town_Node_Ptr = new Town_Node(Town_Name) ;

// pone in testa alla lista il nuovo vertice

if(!Head)

{ // LISTA VUOTA

Head = Town_Node_Ptr;

Town_Node_Ptr->Next_Town = 0;

}

else

{ // LISTA NON VUOTA

Town_Node_Ptr->Next_Town = Head ;

Head = Town_Node_Ptr;

}

// Restituisce un puntatore alla città di cui si chiede se appartiene alla lista, se la città non è trovata, restituisce 0

Town_Node* Town_List::Is_Member_Of(Gen_Data_Ptr Town_Name)

{

Town_Node *Town_Node_Ptr ;

Town_Node_Ptr = Head ;

while((Town_Node_Ptr != 0) &&

!(Town_Name->Is_Equal(Town_Node_Ptr->Destination_Town)))

{

Town_Node_Ptr = Town_Node_Ptr->Next_Town ;

};

return Town_Node_Ptr ;

}

// Visualizza le città appartenenti alla lista delle minime distanze

void Town_List::Display_Only_Towns()

{

if(Head == 0)

{

cout << "No Town to Display " << endl;

}

else

{

Town_Node *Town_Node_Ptr ;

Town_Node_Ptr = Head ;

while(Town_Node_Ptr != 0)

{ // il ciclo è ripetuto sin quando non è NULL

Town_Node_Ptr->Display_Town() ;

Town_Node_Ptr = Town_Node_Ptr->Next_Town ;

}

cout << "\n" ;

}

// Valuta tra le città appartenenti alla lista delle minime distanze quellache non è ancora stata visitata ed è la più vicina alla città di partenza il flag The_End indica che tutte le città sono state visitate.

Gen_Data_Ptr Town_List::Nearest_Not_Visited_Town(bool & The_End)

{

// punta alla città non visitata più vicina

Town_Node *Nearest_Town_Ptr ;

Nearest_Town_Ptr = 0;

Town_Node *Town_Node_Ptr ;

Town_Node_Ptr = Head ;

// ricerco il primo nodo non visitato per inizializzare Nearest_Town_Ptr

while((Town_Node_Ptr != 0)&&(Town_Node_Ptr->Visited == true))

{

Town_Node_Ptr = Town_Node_Ptr->Next_Town ;

}

if(Town_Node_Ptr == 0)

{

The_End = true;

return Head->Destination_Town;

}

Nearest_Town_Ptr = Town_Node_Ptr;

// La ricerca del minimo e l'aggiornamento prosegue sino all'ultimo

while(Town_Node_Ptr != 0)

{ // il ciclo è ripetuto sin quando non è NULL

if( (Town_Node_Ptr->Min_Distance)-> Is_Lower_Double(Nearest_Town_Ptr->Min_Distance)

&& (Town_Node_Ptr->Visited == false) )

{

Nearest_Town_Ptr = Town_Node_Ptr;

}

Town_Node_Ptr = Town_Node_Ptr->Next_Town ;

}

The_End = false ;

return Nearest_Town_Ptr->Destination_Town;

}

// Viene cancellata la lista delle minime distanze con restituzione al sistema operativo della memoria utilizzata

void Town_List::Clear()

{

Town_Node *Town_Node_Ptr ;

while(Head != 0)

{ // il ciclo è ripetuto sin quando non è NULL

Town_Node_Ptr = Head ;

Head = Head->Next_Town ;

delete Town_Node_Ptr ;

}

Il programma principale che utilizza le precedenti classi è pertanto il seguente:

Mainprg.cpp

#include "Graph.h"

#include "Arc_List.h"

#include "Element.h"

#include "Int_Obj.h"

#include "har_Obj.h"

#include "Double_Obj.h"

#include "String_Obj.h"

#include "String_Double_Obj.h"

#include "Town_List.h"

#include <ctype.h>

#include <string.h>

#include <iostream.h>

#include <conio.h>

#include <stdio.h>

#include <stdlib.h> // per atoi ed atof

#include <fstream.h>

void Load_Vertex();

void Load_Graph();

void Save_Graph();

string Source_File, Dest_File ;

// manipolatori del grafo

void Insert();

void Create();

void Display();

void Number_Of_Vertices_In();

void Number_Of_Arcs_In();

void Destroy_Arc();

void Destroy_Vertex();

void Destroy_Graph();

void Best_Way();

// Per il polimorfismo

char Type_Selection(istream& Input_Stream);

bool Set_Element_Name_Pointer(Gen_Data_Ptr & Element_Name_Ptr, istream& Input_Stream);

int Int_Data ;

char Char_Data ;

double Double_Data ;

string String_Data ;

Gen_Data_Ptr Source_Name_Ptr, Dest_Name_Ptr , Arc_Name_Ptr ;

// Istanziazione della classe Graph

Graph *My_Graph ;

void main()

{

cout<<"\n\n";

cout<<" __________________________________________________________ \n";

cout<<" | |\n";

cout<<" | --------- BEST WAY ---------- |\n";

cout<<" |__________________________________________________________|\n";

cout<<" | |\n";

cout<<" | Programmer : |\n";

cout<<" | ------------- |\n";

cout<<" | |\n";

cout<<" | D`OTTAVIO ANTONIO |\n";

cout<<" | |\n";

cout<<" |__________________________________________________________|\n";

char Response ;

bool again ;

My_Graph = new Graph ;

{

cout<<"\nInvio per proseguire";

cin.getline(String_Data, STRING_SIZE) ;

cout << "\n\n\n\n\n\n\n\n\n\n\n\n\n";

cout << " ************************************************************\n";

cout << " * Prego selezionare una delle seguenti opzioni : *\n";

cout << " * C) Caricamento di una mappa *\n";

cout << " * M) Memorizzazione della mappa *\n";

cout << " * 1) Inserzione di una citta' *\n";

cout << " * 2) Creazione di una strada *\n";

cout << " * 3) Visualizzazione della mappa *\n";

cout << " * 4) Determinazione del numero di citta' *\n";

cout << " * 5) Determinazione del numero di strade *\n";

cout << " * 6) Eliminazione di una strada *\n";

cout << " * 7) Eliminazione di una citta' *\n";

cout << " * 8) Eliminazione della mappa *\n";

cout << " * 9) Calcolo delle distanze minime *\n";

cout << " * 0) Fine *\n";

cout << " ************************************************************\n";

cin.getline(String_Data,STRING_SIZE);

Response = toupper(*String_Data);

cout << "\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n" ;

switch(Response)

{

case 'C' :

cout << "\t\t\t**********************************\n";

cout << "\t\t\t* Caricamento del grafo *\n";

cout << "\t\t\t**********************************\n";

My_Graph->Clear();

cout << "Inserire il nome del file sorgente : ";

cin >> Source_File ;

Load_Vertex() ;

Load_Graph() ;

again = true ;

continue ;

case 'M' :

cout << "\t\t\t**********************************\n";

cout << "\t\t\t* Memorizzazione del grafo *\n";

cout << "\t\t\t**********************************\n";

cout << "Inserire il nome del file destinazione : ";

cin >> Dest_File ;

Save_Graph();

again = true ;

continue;

case '1' :

cout << "\t\t\t**********************************\n";

cout << "\t\t\t* Inserzione di un vertice *\n";

cout << "\t\t\t**********************************\n";

Insert() ;

again = true ;

continue ;

case '2' :

cout << "\t\t\t**********************************\n";

cout << "\t\t\t* Inserzione di un arco *\n";

cout << "\t\t\t**********************************\n";

Create();

again = true ;

continue ;

case '3' :

cout << "\t\t\t**********************************\n";

cout << "\t\t\t* Visualizzazione del Grafo *\n";

cout << "\t\t\t**********************************\n";

Display() ;

again = true ;

continue ;

case '4' :

cout << "\t\t\t**********************************\n";

cout << "\t\t\t*Determinazione del n di vertici *\n";

cout << "\t\t\t**********************************\n";

Number_Of_Vertices_In();

again = true ;

continue ;

case '5' :

cout << "\t\t\t**********************************\n";

cout << "\t\t\t* Determinazione del n di archi *\n";

cout << "\t\t\t**********************************\n";

Number_Of_Arcs_In();

again = true ;

continue ;

case '6' :

cout << "\t\t\t**********************************\n";

cout << "\t\t\t* Eliminazione di un arco *\n";

cout << "\t\t\t**********************************\n";

Destroy_Arc();

again = true ;

continue ;

case '7' :

cout << "\t\t\t**********************************\n";

cout << "\t\t\t* Eliminazione di un vertice *\n";

cout << "\t\t\t**********************************\n";

Destroy_Vertex();

again = true ;

continue;

case '8' :

cout << "\t\t\t**********************************\n";

cout << "\t\t\t* Eliminazione del grafo *\n";

cout << "\t\t\t**********************************\n";

Destroy_Graph();

again = true ;

continue;

case '9' :

cout << "\t\t\t**********************************\n";

cout << "\t\t\t* Ricerca del percorso minimo *\n";

cout << "\t\t\t**********************************\n";

Best_Way();

again = true ;

continue;

case '0' :

cout << "\t\t\t**********************************\n";

cout << "\t\t\t* See You....... *\n";

cout << "\t\t\t**********************************\n";

again = false ;

continue;

default :

again = true ;

continue;

} // fine dello switch

} // fine del do

while(again);

My_Graph->Clear();

}

// Procedura per il caricamento da file dei vertici di una mappa.

void Load_Vertex()

{

// memorizzo prima i soli vertici

ifstream In_Buffer(Source_File, ios::in);

while(Set_Element_Name_Pointer(Source_Name_Ptr , In_Buffer))

{

My_Graph->Insert(Source_Name_Ptr);

In_Buffer.getline(String_Data,STRING_SIZE,'\n');

}

In_Buffer.close() ;

}

// Procedura per il caricamento da file di una mappa. Deve essere eseguita soltanto dopo che sono stati caricati i vertici in quanto altrimenti ci sono chiari problemi nella creazione degli archi.

void Load_Graph()

{

// mi riposiziono all'inizio del file per memorizzare ora anche gli archi

ifstream In_Buffer(Source_File, ios::in);

int Number_Of_Arcs_From ;

while(Set_Element_Name_Pointer(Source_Name_Ptr , In_Buffer))

{

// acquisisce il n° di archi uscenti dal vertice

In_Buffer.getline(String_Data, STRING_SIZE,'\t');

Number_Of_Arcs_From = atoi(String_Data);

for( ; Number_Of_Arcs_From != 0 ; --Number_Of_Arcs_From)

{

Set_Element_Name_Pointer(Arc_Name_Ptr , In_Buffer);

Set_Element_Name_Pointer(Dest_Name_Ptr , In_Buffer);

My_Graph->Create_An_Arc(Source_Name_Ptr, Dest_Name_Ptr, Arc_Name_Ptr);

}

// estraggo il carattere di fine linea

In_Buffer.getline(String_Data,STRING_SIZE,'\n');

}

In_Buffer.close() ;

}

// Funzione che permette la selezione del tipo di dato che si vuole inserire.

L'ingresso può avvenire sia da file che da tastiera.

char Type_Selection(istream & Input_Stream)

{

char Data_Type;

if(Input_Stream == cin)

{

cout << "\t***************************************************************\n";

cout << "\t* C) Char D) Double I) Int K) String&Double S) String *\n";

cout << "\t***************************************************************\n";

Input_Stream.getline(String_Data,STRING_SIZE);

Data_Type = toupper(*String_Data); ;

}while(Data_Type != 'C' && Data_Type != 'D' && Data_Type != 'I'

&& Data_Type != 'K' && Data_Type != 'S' );

}

else

{

Input_Stream.getline(String_Data,STRING_SIZE,'\t');

Data_Type = toupper(*String_Data) ;

}

return (Data_Type) ;

}

// Questa funzione consente di settare una qualsiasi delle 3 variabili esterne

// Source_Name_Ptr , Dest_Name_Ptr, Arc_Name_Ptr, sia che l'ingresso avvenga da

// file sia che l'ingresso avvenga da tastiera, la funzione è fondamentale al

// fine di implemetare il polimorfismo sul tipo di dato.

bool Set_Element_Name_Pointer(Gen_Data_Ptr& Element_Name_Ptr, istream& Input_Stream)

{

char Terminator;

if(Input_Stream == cin)

Terminator = '\n';

else

Terminator = '\t';

switch(Type_Selection(Input_Stream))

{

case 'C':

if(Input_Stream == cin)

cout << "Immettere un carattere : ";

Input_Stream.getline(String_Data , STRING_SIZE, Terminator);

Char_Data = *String_Data;

Element_Name_Ptr = new Char_Obj(Char_Data);

break;

case 'I':

if(Input_Stream == cin)

cout << "Immettere un numero intero : ";

Input_Stream.getline(String_Data , STRING_SIZE, Terminator);

Int_Data = atoi(String_Data);

if(Int_Data)

Element_Name_Ptr = new Int_Obj(Int_Data);

else

cout << "Attenzione c’è una incompatibilita' di tipo. Operazione non eseguita.\n\n";

break;

case 'D':

if(Input_Stream == cin)

cout << "Immettere un numero double : ";

Input_Stream.getline(String_Data , STRING_SIZE, Terminator);

Double_Data = atof(String_Data);

if(Double_Data)

Element_Name_Ptr = new Double_Obj(Double_Data);

else

cout << "Attenzione c’è una incompatibilita' di tipo. Operazione non eseguita.\n\n";

break;

case 'K':

if(Input_Stream == cin)

cout << "Strada :\t";

string Temp_String_Data;

// acquisizione e creazione dell'oggetto stringa

Input_Stream.getline(String_Data, STRING_SIZE, Terminator);

// acquisizione e creazione dell'oggetto double

strcpy(Temp_String_Data,String_Data) ;

if(Input_Stream == cin)

cout << "Km :\t";

Input_Stream.getline(String_Data , STRING_SIZE, Terminator);

Double_Data = atof(String_Data);

if(Double_Data)

Element_Name_Ptr = new String_Double_Obj(Temp_String_Data,Double_Data);

else

cout << "Attenzione c’è una incompatibilita' di tipo. Operazione non eseguita.\n\n";

break;

case 'S':

if(Input_Stream == cin)

cout << "Immettere una stringa : ";

Input_Stream.getline(String_Data, STRING_SIZE, Terminator);

Element_Name_Ptr = new String_Obj(String_Data);

break;

default :

return false ; // file vuoto

break;

}

return true;

}

// questa procedura si occupa di salvare un grafo su disco, si richiede che

// sia stata impostata una stringa valida in Dest_File

void Save_Graph()

{

// Vengono ora salvati vertici ed archi nel file il cui nome è contenuto in Dest_File

ofstream Graph_Out_Buffer(Dest_File, ios::out);

My_Graph->Save_Vertex_And_Arcs(Graph_Out_Buffer);

Graph_Out_Buffer << ends;

Graph_Out_Buffer.close();

}

// Questa procedura consente l' inserzione di un vertice nel grafo

void Insert()

{

cout << "\nSelezionare il tipo di dato per il vertice sorgente:\n" ;

Set_Element_Name_Pointer(Source_Name_Ptr,cin);

My_Graph->Insert(Source_Name_Ptr);

}

// Questa procedura consente la creazione di un arco tra 2 città

void Create()

{

cout << "\nSelezionare il tipo di dato per il vertice sorgente :\n";

Set_Element_Name_Pointer(Source_Name_Ptr,cin) ;

cout << "\nSelezionare il tipo di dato per il vertice di destinazione :\n";

Set_Element_Name_Pointer(Dest_Name_Ptr,cin) ;

cout << "\nSelezionare il tipo di dato per l'arco :\n";

Set_Element_Name_Pointer(Arc_Name_Ptr,cin) ;

My_Graph->Create_An_Arc(Source_Name_Ptr, Dest_Name_Ptr, Arc_Name_Ptr) ;

}

// Questa procedura consente la visualizzazione del grafo

void Display()

{

My_Graph->Display_Graph();

}

// Questa procedura consente di valutare il numero di città nel grafo

void Number_Of_Vertices_In()

{

cout << "Nel Grafo sono presenti ";

cout << My_Graph->Number_Of_Vertices_In();

cout << " vertici." << endl;

}

// Questa procedura consente di valutare il numero di strade nel grafo

void Number_Of_Arcs_In()

{

cout << "Nel Grafo sono presenti ";

cout << My_Graph->Number_Of_Arcs_In();

cout << " archi." << endl;

}

// Questa procedura consente di eliminare dal grafo una strada

void Destroy_Arc()

{

cout << "\nSelezionare il tipo di dato per il vertice sorgente :\n" ;

Set_Element_Name_Pointer(Source_Name_Ptr,cin);

cout << "\nSelezionare il tipo di dato per il vertice di destinazione :\n" ;

Set_Element_Name_Pointer(Dest_Name_Ptr,cin);

cout << "\nSelezionare il tipo di dato per l'arco :\n" ;

Set_Element_Name_Pointer(Arc_Name_Ptr,cin);

My_Graph->Remove_Arc(Source_Name_Ptr, Dest_Name_Ptr,Arc_Name_Ptr);

}

// Questa procedura consente di eliminare dal grafo una città

void Destroy_Vertex()

{

cout << "\nSelezionare il tipo di dato per il vertice sorgente :\n" ;

Set_Element_Name_Pointer(Source_Name_Ptr,cin);

My_Graph->Remove_Vertex(Source_Name_Ptr);

}

// Questa procedura consente di eliminare il grafo

void Destroy_Graph()

{

My_Graph->Clear();

}

// Procedura per la ricerca dei percorsi più brevi a partire da una città verso tutte le altre città appartenenti al grafo.

void Best_Way()

{

// Creazione ed inizializzazione della lista dei percorsi minimi

Town_List *Town_List_Ptr ;

Town_List_Ptr = new Town_List;

My_Graph->Copy_Vertex_In(Town_List_Ptr);

// Scelta del vertice rispetto al quale operare i minimi percorsi

{

cout << "\nSelezionare il tipo di dato per il vertice sorgente:\n" ;

Set_Element_Name_Pointer(Source_Name_Ptr,cin);

}

while(!My_Graph->Is_Member_Of(Source_Name_Ptr));

//Inserimento del valore 0 nel campo Min_Distance della città di partenza

// copia dei dati riguardanti il vertice nei rispettivi campi di Town_List

Gen_Data_Ptr Source_Town = Source_Name_Ptr;

My_Graph->Copy_Arcs_Of(Source_Name_Ptr, Town_List_Ptr);

bool The_End;

Source_Name_Ptr = Town_List_Ptr->Nearest_Not_Visited_Town(The_End);

while(The_End == false)

{

My_Graph->Adjourn_Not_Visited_Town(Source_Name_Ptr, Town_List_Ptr);

Source_Name_Ptr = Town_List_Ptr->Nearest_Not_Visited_Town(The_End);

}

cout << "\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n" ;

cout << "Elenco delle distanze minime rispetto a " ;

Source_Town->Display();

cout << "\n";

Town_List_Ptr->Display_Only_Towns();

cout << "\n";

Town_List_Ptr->Clear();

}