Grafi Orientati

La prima testimonianza di impiego dei grafi risale al 1736 quando Leonhard Eulero li utilizzò per risolvere il classico problema dei ponti di Koenigsberg dove il fiume Pregal scorre attorno all´isola di Kneiphof. Ci sono quattro terre ferme identificate dalle lettere A , B , C , D in Figura 1 , che hanno questo fiume ai loro confini. Sette ponti identificati dalle lettere a-g, collegano le quattro terre ferme. Il problema del ponte di Koenigsberg è il seguente : partendo da una terra ferma , è possibile ritornare alla posizione iniziale dopo aver attraversato ciascun ponte una sola volta?

Un possibile tragitto è il seguente:

· Partire dalla terra ferma B

· Attraversare il ponte a per raggiungere l´isola A

· Usare il ponte e per raggiungere la area D

· Usare il ponte g per raggiungere la area C

· Usare il ponte d per raggiungere la area A

· Usare il ponte b per raggiungere la area B

· Usare il ponte f per raggiungere la area D

Questo percorso non attraversa tutti i ponti né conduce alla posizione di partenza B. Eulero scoprì che la gente di Koenigsberg non può attraversare ciascun ponte una sola volta e ritornare alla posizione di partenza. Eulero risolse il problema utilizzando un grafo (un multigrafo in effetti) in cui le terre ferme erano i vertici ( o nodi ) e i ponti erano i lati ( archi ). La sua soluzione non è soltanto elegante ma si applica a tutti i grafi.

Eulero definì il grado di un vertice come il numero dei lati incidenti su di esso, dimostrò anche che esiste un percorso che parte da un vertice qualsiasi, attraversa una sola volta ciascun lato e termina nel vertice iniziale, se e solo se il grado di ogni vertice è pari. Un percorso simile sarà chiamato percorso di Eulero. Questo percorso non esiste per i ponti di Koenigsberg , in quanto tutti i vertici sono di grado dispari.

Da questa prima applicazione, i grafi sono stati utilizzati in una vasta gamma di applicazioni, come la analisi dei circuiti elettrici , la pianificazione dei progetti, l´identificazione dei composti chimici o la determinazione delle strade più corte.

2) Definizioni

Un grafo è una collezione che comprende due insiemi, uno di vertici e uno di archi, mentre l'insieme degli archi può esser vuoto, l'insieme dei vertici, se il grafo esiste, non può risultare vuoto. Un vertice è anche chiamato nodo e costituisce l' elemento strutturale base del grafo. Un arco è la connessione tra due vertici, se gli archi del grafo sono orientati , allora si parla di grafo orientato altrimenti si parla di grafo non orientato.

A ciascun vertice ed arco possono essere associate delle etichette, se ciò accade si parla di grafo etichettato nei vertici o negli archi, le etichette di due archi, non necessariamente devono essere diverse, è possibile avere due archi con lo stesso attributo. Nel caso in cui le etichette siano costituite da numeri interi o decimali e gli elementi del grafo siano etichettati in modo ordinato, allora si parla di grafo pesato.

All'interno di un grafo orientato, si definisce cammino una sequenza di vertici tali che esiste un arco tra ciascun vertice e quello successivo. La lunghezza del cammino e' pari al numero di archi che collegano i vertici. Un singolo vertice costituirà un cammino di lunghezza zero. Il cammino si dice semplice se, all'interno del cammino, non esistono vertici che compaiono più di una volta, in caso contrario si dice non semplice. In un grafo orientato, un ciclo e' un cammino di lunghezza maggiore o uguale ad uno che inizia e termina sullo stesso vertice. Un grafo si definisce ciclico se in esso ci sono uno o più cicli, in caso contrario, diremo che il grafo è aciclico. Nel caso di grafo orientato, si dice che il nodo Vj è adiacente al nodo Vi se esiste un arco che parte da Vi e giunge in Vj , tale arco viene detto incidente ai nodi Vi e Vj. Nel caso in cui si abbia a che fare con un grafo non orientato, non ha senso parlare di vertici adiacenti in quanto tale definizione è strettamente legata al concetto di arco orientato (arco nel quale e' importante l'ordine dei suoi punti estremi).

Da ogni vertice può dipartirsi un numero imprecisato di archi i quali possono terminare in uno qualsiasi dei vertici del grafo, può accadere che da un vertice si dipartano due archi che terminano entrambi nello stesso vertice, diverso da quello di partenza, in questo caso i vertici di partenza e di arrivo per ciascun arco sono uguali, tali archi vengono detti paralleli, un grafo che non contiene archi paralleli è detto semplice.

Per un vertice si definisce il grado come il numero di archi relativi ad esso, più precisamente, si parla di grado di ingresso, per indicare il numero di archi che terminano nel vertice considerato e grado di uscita per indicare il numero di archi che si dipartono dal vertice considerato. Un vertice che ha un grado nullo è detto isolato e rappresenta un vertice da cui non si dipartono nè giungono archi. Un grafo è detto connesso se vi è un percorso tra ogni coppia di nodi appartenenti al grafo stesso, ovviamente, un grafo che contiene nodi isolati non è connesso.

Un grafo si dice strettamente connesso se per ogni vertice esiste un percorso diretto verso ogni altro vertice. Le figure che seguono, illustrano un grafo etichettato orientato (a sinistra) ed il corrispondente grafo etichettato non orientato ( a destra ).

Dopo aver fornito qualche nozione generale sul tipo di dato astratto GRAFO, occupiamoci ora di definirne ora la rappresentazione .

3) Rappresentazione del dato astratto Grafo

Un modo di rappresentare il dato astratto Grafo è conosciuto con il nome di matrice delle adiacenze, in tal caso, un grafo è rappresentato da una matrice quadrata di ordine N dove N è il numero dei vertici appartenenti al grafo, essi sono in corrispondenza biunivoca con i valori degli indici di riga e di colonna della matrice quadrata. Gli elementi della matrice sono di tipo booleano ed il loro valore viene stabilito dalla seguente regola:

l'elemento nella riga i e colonna j vale True se nel grafo esiste un arco dal vertice i al vertice j, altrimenti vale False.

Un "cappio" sarà rappresentato dal valore True posto nella casella individuata da (i , i) .

Vantaggi : Tale rappresentazione è molto semplice e consente l'accesso diretto alla informazione relativa all'esistenza o meno di un arco che collega due vertici

Svantaggi : Un grafo costituito da N vertici, richiede una matrice NxN, questo è un problema quando il numero di vertici cresce notevolmente poiché aumenta la memoria occupata. Un altro svantaggio di questa rappresentazione consiste nel fatto che non possiamo aumentare il numero di vertici del grafo inoltre non si possono rappresentare grafi in cui compaiono archi paralleli.

Un secondo tipo di rappresentazione consiste nel rappresentare un grafo tramite una lista di sottoliste, tale rappresentazione è nota con il nome di lista delle adiacenze, tutti i vertici del grafo sono inseriti in una lista ed ogni vertice ha, associata a se, una ulteriore lista che conterrà tutti gli archi che si originano da tale vertice.

Vantaggi : L'occupazione di memoria viene a dipendere solo dal numero effettivo di vertici ed archi che costituiscono il grafo, inoltre, la rappresentazione è dinamica

Svantaggi : L'accesso ad un elemento del grafo non è diretto , ma necessita la scansione della lista

Nel nostro caso , per realizzare il grafo , prenderemo in considerazione la rappresentazione mediante lista delle adiacenze, del grafo considereremo una rappresentazione limitata dalla sola disponibilità di memoria del sistema che la implementa (Unbounded Form), inoltre, la rappresentazione da noi presa in considerazione gestirà lo spazio di memoria che si crea per eventuali cancellazioni.

La complessità della algoritmo che implementa i grafi orientati ha portato a rivedere la approccio al problema in termini di sottoproblemi di complessità inferiore che sono stati ottimizzati singolarmente e successivamente coordinati. Questo stesso percorso logico sarà seguito nella trattazione che pertanto risulta articolata nei seguenti punti:

a) Individuazione degli oggetti base in cui scomporre il problema

b) Descrizione ed implementazione del polimorfismo

c) Sviluppo di un applicativo basato sulla classe GRAPH

a) Individuazione oggetti base

Una delle possibili rappresentazioni informatiche dei grafi è quella delle liste di adiacenza che, come precedentemente esposto, si basa su di una lista contenente tutti i vertici facenti parte del grafo da ognuno dei quali si origina la lista degli archi uscenti dal vertice stesso.

In questa ottica risulta abbastanza intuitivo individuare quale oggetto primitivo ossia non utilizzante altri oggetti l´ARC_NODE, successivamente si individua l´oggetto ARC_LIST ossia la lista che riunisce tutti gli ARC_NODE, proseguendo nello sviluppo logico si ha il VERTEX_NODE da cui si dipana la ARC_LIST ed infine si ha la VERTEX_LIST che da un punto di vista logico coincide con l´oggetto GRAFO.

Passiamo ora alla analisi dei singoli oggetti nell´ordine sovraesposto:

ARC_NODE

// Arc_Node.h: interface for the Arc_Node class.

//////////////////////////////////////////////////////////////////////

#if !defined(AFX_ARC_NODE_H__4D70C386_7844_11D1_BECF_444553540000__INCLUDED_)

#define AFX_ARC_NODE_H__4D70C386_7844_11D1_BECF_444553540000__INCLUDED_

#if _MSC_VER >= 1000

#pragma once

#endif // _MSC_VER >= 1000

#include "Element.h"

class Arc_Node

{

friend class Arc_List ;

protected:

Gen_Data_Ptr Arc_Destination ;

Gen_Data_Ptr Arc_Attribute ;

Arc_Node *Next_Arc ;

public:

void Display_An_Arc();

Arc_Node(Gen_Data_Ptr The_Attribute, Gen_Data_Ptr The_Destination);

virtual ~Arc_Node();

};

#endif // !defined(AFX_ARC_NODE_H__4D70C386_7844_11D1_BECF_444553540000__INCLUDED_)

Come si vede è dichiarata friend la Arc_List che quindi potrà accedere ai dati descritti nella parte privata ossia 2 puntatori di tipo Gen_Data_Ptr il quale nella classe ELEMENT viene definito come un puntatore ad un oggetto di tipo ELEMENT. Questi 2 puntatori consentono quindi di non vincolare il tipo nè della attributo della arco ne della attributo del vertice di destinazione. Si ha poi un puntatore al nodo successivo nella lista degli archi inerenti un dato vertice.

Le operazioni definite su ogni oggetto di tipo ARC_NODE sono la sua creazione e contemporanea inizializzazione, la distruzione e la visualizzazione secondo la seguente dichiarazione:

// Arc_Node.cpp: implementation of the Arc_Node class.

//////////////////////////////////////////////////////////////////////

#include "Arc_Node.h"

#include <iostream.h>

//////////////////////////////////////////////////////////////////////

// Construction/Destruction

//////////////////////////////////////////////////////////////////////

Arc_Node::Arc_Node(Gen_Data_Ptr The_Attribute, Gen_Data_Ptr The_Destination)

{

Arc_Attribute = The_Attribute ;

Arc_Destination = The_Destination ;

}

Arc_Node::~Arc_Node()

{

}

//////////////////////////////////////////////////////////////////////

// Display

//////////////////////////////////////////////////////////////////////

void Arc_Node::Display_An_Arc()

{

Arc_Attribute->Display() ;

cout << " --> " ;

Arc_Destination->Display();

cout << "\t" ;

}

La Display_An_Arc non fa altro che applicare il metodo Display definito per la classe ELEMENT e per le sue classi derivate ad Arc_Attribute ed Arc_Destination che sono puntatori a questa classe, ottenendo quindi la visualizzazione della attributo della arco e del vertice di destinazione.

ARC_LIST

// Arc_List.h: interface for the Arc_List class.

//////////////////////////////////////////////////////////////////////

#if !defined(AFX_ARC_LIST_H__4D70C384_7844_11D1_BECF_444553540000__INCLUDED_)

#define AFX_ARC_LIST_H__4D70C384_7844_11D1_BECF_444553540000__INCLUDED_

#if _MSC_VER >= 1000

#pragma once

#endif // _MSC_VER >= 1000

#include "Arc_Node.h"

class Arc_List

{

protected:

Arc_Node *Arc_List_Head ;

public:

Arc_Node* Is_Member_Of(Gen_Data_Ptr The_Arc, Gen_Data_Ptr The_Destination);

void Clear();

int Number_Of_Arcs_In();

bool Remove(Gen_Data_Ptr The_Arc, Gen_Data_Ptr The_Destination);

void Display_Arcs();

void Insert(Gen_Data_Ptr The_Attribute, Gen_Data_Ptr The_Destination);

Arc_List();

virtual ~Arc_List();

};

#endif // !defined(AFX_ARC_LIST_H__4D70C384_7844_11D1_BECF_444553540000__INCLUDED_)

L´unico dato protetto di questa classe è un puntatore ad un ARC_NODE il quale sarà il primo della lista degli archi uscenti dal dato vertice per cui la classe viene istanziata. Nella parte Public vi è la definizione delle operazioni standard eseguibili su di una lista , la loro dichiarazione è la seguente:

// Arc_List.cpp: implementation of the Arc_List class.

//////////////////////////////////////////////////////////////////////

#include <iostream.h>

#include "Arc_List.h"

//////////////////////////////////////////////////////////////////////

// Construction/Destruction

//////////////////////////////////////////////////////////////////////

Arc_List::Arc_List()

{

Arc_List_Head = 0 ;

}

Arc_List::~Arc_List()

{

}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//Inserzione di un elemento in testa alla lista degli archi, si ricordi che nella rappresentazione da noi introdotta non ha

//alcun senso prevedere un inserzione ordinata degli archi appunto per la natura eterogenea dei dati trattati.

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void Arc_List::Insert(Gen_Data_Ptr The_Attribute, Gen_Data_Ptr The_Destination)

{

Arc_Node *Arc_Node_Ptr ;

//Vertex_Node_Ptr punta ad un nuovo Vertex_Node

Arc_Node_Ptr = new Arc_Node(The_Attribute, The_Destination) ;

// pone in testa alla lista il nuovo vertice

if(Arc_List_Head == 0)

{ // LISTA VUOTA

Arc_List_Head = Arc_Node_Ptr;

Arc_Node_Ptr->Next_Arc = 0;

}

else

{ // LISTA NON VUOTA

Arc_Node_Ptr->Next_Arc = Arc_List_Head ;

Arc_List_Head = Arc_Node_Ptr;

}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// visualizzazione di tutti gli archi appartenenti alla lista

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void Arc_List::Display_Arcs()

{

if(Arc_List_Head == 0)

{

cout << "\tNo Arcs leave from this Vertex " << endl;

}

else

{

Arc_Node *Arc_Node_Ptr ;

Arc_Node_Ptr = Arc_List_Head ;

while(Arc_Node_Ptr != 0)

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

Arc_Node_Ptr->Display_An_Arc() ;

Arc_Node_Ptr = Arc_Node_Ptr->Next_Arc ;

}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// Eliminazione di un arco dalla lista

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

bool Arc_List::Remove(Gen_Data_Ptr The_Arc, Gen_Data_Ptr The_Destination)

{

// Punto un puntatore alla testa della lista

Arc_Node *Arc_Node_Ptr_1 ;

Arc_Node *Arc_Node_Ptr_2 ;

Arc_Node_Ptr_1 = Arc_List_Head ;

Arc_Node_Ptr_2 = Arc_List_Head ;

// ricerca del nodo da rimuovere

while((Arc_Node_Ptr_1 != 0) &&

( (!(The_Arc->Is_Equal(Arc_Node_Ptr_1->Arc_Attribute))) ||

(!(The_Destination->Is_Equal(Arc_Node_Ptr_1->Arc_Destination))) ) )

{

Arc_Node_Ptr_2 = Arc_Node_Ptr_1 ;

Arc_Node_Ptr_1 = Arc_Node_Ptr_1->Next_Arc;

}

if(Arc_Node_Ptr_1 != 0)

{ // HO TROVATO L'ELEMENTO DA RIMUOVERE

if(Arc_Node_Ptr_1 != Arc_List_Head)

Arc_Node_Ptr_2->Next_Arc = Arc_Node_Ptr_1->Next_Arc;

else // L'ARCO DA RIMUOVERE È IL PRIMO DELLA LISTA

Arc_List_Head = Arc_List_Head->Next_Arc;

// eliminazione dell'arco

delete Arc_Node_Ptr_1;

return true;

}

else

{ // ELEMENTO NON TROVATO

return false;

}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// restituisce il numero di archi uscenti da un vertice

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

int Arc_List::Number_Of_Arcs_In()

{

int N_Arcs = 0 ;

Arc_Node *Arc_Node_Ptr ;

Arc_Node_Ptr = Arc_List_Head ;

while(Arc_Node_Ptr != 0)

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

N_Arcs++ ;

Arc_Node_Ptr = Arc_Node_Ptr->Next_Arc ;

}

return N_Arcs ;

}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// Questa member function si occupa di cancellare tutti gli archi presenti nella lista

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void Arc_List::Clear()

{

Arc_Node *Arc_Node_Ptr ;

Arc_Node_Ptr = Arc_List_Head ;

while(Arc_Node_Ptr != 0)

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

Remove(Arc_Node_Ptr->Arc_Attribute,Arc_Node_Ptr->Arc_Destination);

Arc_Node_Ptr = Arc_List_Head ;

}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//Questa funzione si occupa di stabilire se un dato arco fa già parte della lista attuale e nel caso la arco viene

//individuato ne restituisce un puntatore ad esso altrimenti viene restituito il puntatore di fine lista ossia 0 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

Arc_Node* Arc_List::Is_Member_Of(Gen_Data_Ptr The_Arc, Gen_Data_Ptr The_Dest)

{

Arc_Node *Arc_Node_Ptr ;

Arc_Node_Ptr = Arc_List_Head ;

while((Arc_Node_Ptr != 0) &&

(!(The_Arc->Is_Equal(Arc_Node_Ptr->Arc_Attribute))) &&

(!(The_Dest->Is_Equal(Arc_Node_Ptr->Arc_Destination))) )

{

Arc_Node_Ptr = Arc_Node_Ptr->Next_Arc ;

}

return Arc_Node_Ptr ;

}

Si noti nella REMOVE e nella IS_MEMBER_OF l´utilizzo del metodo IS_EQUAL definito sul tipo ELEMENT e derivati, il quale consente di stabilire l´uguaglianza dei dati puntati da 2 puntatori previa conversione mediante Type_Casting da puntatore ad un oggetto ELEMENT a puntatore a FLOAT_OBJ o CHAR_OBJ o INT_OBJ .

VERTEX_NODE

// Vertex_Node.h: interface for the Vertex_Node class.

//////////////////////////////////////////////////////////////////////

#if !defined(AFX_VERTEX_NODE_H__4D70C387_7844_11D1_BECF_444553540000__INCLUDED_)

#define AFX_VERTEX_NODE_H__4D70C387_7844_11D1_BECF_444553540000__INCLUDED_

#if _MSC_VER >= 1000

#pragma once

#endif // _MSC_VER >= 1000

#include "Graph.h"

#include "Arc_List.h"

class Vertex_Node

{

friend class Graph ;

protected:

Gen_Data_Ptr Vertex_Attribute ;

unsigned int Reference_Count ;

Arc_List *Arc_List_Ptr ;

Vertex_Node *Next_Vertex ;

public:

void Display_Vertex_And_Arcs();

void Display_Vertex();

Vertex_Node(Gen_Data_Ptr The_Attribute);

virtual ~Vertex_Node();

};

#endif // !defined(AFX_VERTEX_NODE_H__4D70C387_7844_11D1_BECF_444553540000__INCLUDED_)

Anche in questo caso viene definita come friend la classe GRAPH (che ricordiamo equivalente alla VERTEX_LIST) in quanto dovrà avere libero accesso ai campi del singolo Vertex_Node di cui si compone. Nel segmento protected compaiono le informazioni di cui si compone ogni Vertex_Node ossia un attributo il cui tipo non viene vincolato a priori secondo quanto già descritto per il Vertex_Node, un intero positivo indicante il numero degli archi entranti nel vertice, informazione di primaria importanza allorchè si dovrà decidere se il vertice sia eliminabile o meno, vi è poi un puntatore ad un tipo ARC_LIST quindi ogni vertice conosce dove inizia la lista dei suoi archi uscenti. Infine vi è un puntatore al prossimo VERTEX_NODE nella VERTEX_LIST.

Passiamo ora alla dichiarazione delle member function :

// Vertex_Node.cpp: implementation of the Vertex_Node class.

//////////////////////////////////////////////////////////////////////

#include <iostream.h>

#include "Vertex_Node.h"

//////////////////////////////////////////////////////////////////////

// Construction/Destruction

//////////////////////////////////////////////////////////////////////

Vertex_Node::Vertex_Node(Gen_Data_Ptr The_Attribute)

{

Arc_List_Ptr = new Arc_List ;

Next_Vertex = 0 ;

Reference_Count = 0 ;

Vertex_Attribute = The_Attribute ;

}

Vertex_Node::~Vertex_Node()

{

}

//////////////////////////////////////////////////////////////////////

// Visualizzazione del solo nome del vertice

//////////////////////////////////////////////////////////////////////

void Vertex_Node::Display_Vertex()

{

Vertex_Attribute->Display() ;

if(Next_Vertex != 0)

cout << " , ";

else

cout << endl ;

}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//Visualizzazione del nome del vertice degli archi da esso uscenti e dei loro vertici di destinazione

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void Vertex_Node::Display_Vertex_And_Arcs()

{

cout << "\nVertice " ;

Vertex_Attribute->Display();

cout << "\n\tArchi entranti : " << Reference_Count;

cout << "\n\tArchi uscenti : ";

Arc_List_Ptr->Display_Arcs();

}

Per quanto riguarda il costruttore si noti che secondo quanto richiesto dal VISUAL C++ 5.0 i puntatori vengono direttamente inizializzati a 0 e non a NULL come avviene in altri linguaggi o in versioni precedenti. Inoltre l´inizializzazione del campo ARC_LIST_PTR avviene direttamente richiedendo al sistema operativo memoria per un oggetto di tipo ARC_LIST che sarà appunto puntato da ARC_LIST_PTR.

Vi sono due diverse funzioni di visualizzazione definite su di un VERTEX_NODE, la prima visualizza solo il vertice richiamando il metodo Display della classe ELEMENT e sue derivate mentre la seconda visualizza anche gli archi uscenti utilizzando il metodo Display_Arcs definito sul tipo ARC_LIST.

GRAPH (Vertex_List)

// Graph.h: interface for the Graph class.

//////////////////////////////////////////////////////////////////////

#if !defined(AFX_Graph_H__4D70C385_7844_11D1_BECF_444553540000__INCLUDED_)

#define AFX_Graph_H__4D70C385_7844_11D1_BECF_444553540000__INCLUDED_

#if _MSC_VER >= 1000

#pragma once

#endif // _MSC_VER >= 1000

#include "Arc_List.h"

#include "Arc_Node.h"

class Graph // classe che implementa la lista dei vertici

{

friend class Vertex_Node ;

protected:

Vertex_Node *Head ; // punta sempre alla testa della lista

public:

int Number_Of_Arcs_In();

void Clear();

bool Remove_Arc(Gen_Data_Ptr Source_Vertex, Gen_Data_Ptr Dest_Vertex, Gen_Data_Ptr The_Arc);

void Display_Graph();

bool Create_An_Arc(Gen_Data_Ptr Source_Vertex, Gen_Data_Ptr Dest_Vertex,

Gen_Data_Ptr The_Attribute);

Vertex_Node* Is_Member_Of(Gen_Data_Ptr The_Attribute);

int Number_Of_Vertices_In();

bool Remove_Vertex(Gen_Data_Ptr The_Source);

void Display_Only_Vertex();

void Insert(Gen_Data_Ptr The_Attribute);

Graph();

virtual ~Graph();

};

#endif // !defined(AFX_Graph_H__4D70C385_7844_11D1_BECF_444553540000__INCLUDED_)

Anche in questo caso così come era avvenuto per la ARC_LIST l´unico dato privato è il puntatore al primo VERTEX_NODE appartenente alla lista e nella parte Public compaiono le operazioni standard eseguibili su di una lista.

// Graph.cpp: implementation of the Graph class.

//////////////////////////////////////////////////////////////////////

#include <iostream.h>

#include "Graph.h"

#include "Vertex_Node.h"

//////////////////////////////////////////////////////////////////////

// Construction/Destruction

//////////////////////////////////////////////////////////////////////

Graph::Graph()

{

Head = 0 ;

}

Graph::~Graph()

{

}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//Inserisce un vertice in testa alla lista dei vertici controllando che esso non sia già presente nel qual caso non avviene duplicazione.

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void Graph::Insert(Gen_Data_Ptr The_Attribute)

{

if(Is_Member_Of(The_Attribute))

{

cerr << "Il vertice è già presente nel grafo." << endl;

return;

}

Vertex_Node *Vertex_Node_Ptr ;

//Vertex_Node_Ptr punta ad un nuovo Vertex_Node

Vertex_Node_Ptr = new Vertex_Node(The_Attribute) ;

// pone in testa alla lista il nuovo vertice

if(!Head)

{ // LISTA VUOTA

Head = Vertex_Node_Ptr;

Vertex_Node_Ptr->Next_Vertex = 0;

}

else

{ // LISTA NON VUOTA

Vertex_Node_Ptr->Next_Vertex = Head ;

Head = Vertex_Node_Ptr;

}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// Visualizza i soli attributi dei vertici.

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void Graph::Display_Only_Vertex()

{

if(Head == 0)

{

cout << "No Vertex in this Graph " << endl;

}

else

{

Vertex_Node *Vertex_Node_Ptr ;

Vertex_Node_Ptr = Head ;

while(Vertex_Node_Ptr != 0)

{

// il ciclo è ripetuto sin quando non è NULL

Vertex_Node_Ptr->Display_Vertex() ;

Vertex_Node_Ptr = Vertex_Node_Ptr->Next_Vertex ;

}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//Rimozione di un solo vertice e dei suoi archi da un grafo previo controllo che il vertice non sia destinazione di alcun arco.

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

bool Graph::Remove_Vertex(Gen_Data_Ptr Vertex_To_Remove)

{ // Punto un puntatore alla testa della lista

Vertex_Node *Vertex_Node_Ptr_1 ;

Vertex_Node *Vertex_Node_Ptr_2 ;

Vertex_Node_Ptr_1 = Head ;

Vertex_Node_Ptr_2 = Head ;

// ricerca del nodo da rimuovere

while((Vertex_Node_Ptr_1 != 0) &&

(!(Vertex_To_Remove->Is_Equal(Vertex_Node_Ptr_1->Vertex_Attribute))))

{

Vertex_Node_Ptr_2 = Vertex_Node_Ptr_1 ;

Vertex_Node_Ptr_1 = Vertex_Node_Ptr_1->Next_Vertex;

}

// controllo che il vertice esista e che non sia puntato da alcun arco

if( (Vertex_Node_Ptr_1 != 0)&&

( (Vertex_Node_Ptr_1->Reference_Count == 0) ||

( (Vertex_Node_Ptr_1->Reference_Count!=0) &&

(!(Vertex_To_Remove->Is_Equal(Vertex_Node_Ptr_1->Vertex_Attribute))) )))

{

// cancello tutti gli archi uscenti dal vertice

Arc_Node *Arc_Node_Ptr ;

Arc_Node_Ptr = Vertex_Node_Ptr_1->Arc_List_Ptr->Arc_List_Head;

while(Arc_Node_Ptr != 0)

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

Remove_Arc(Vertex_To_Remove, Arc_Node_Ptr->Arc_Destination,

Arc_Node_Ptr->Arc_Attribute);

Arc_Node_Ptr = Vertex_Node_Ptr_1->Arc_List_Ptr->Arc_List_Head;

}

// HO TROVATO L'ELEMENTO DA RIMUOVERE

if(Vertex_Node_Ptr_1 != Head)

Vertex_Node_Ptr_2->Next_Vertex = Vertex_Node_Ptr_1->Next_Vertex;

else // L'ARCO DA RIMUOVERE È IL PRIMO DELLA LISTA

Head = Head->Next_Vertex;

// elimino il vertice

delete Vertex_Node_Ptr_1;

return true;

};

if(Vertex_Node_Ptr_1 == 0)

{

cerr << "Il vertice da eliminare non è stato trovato" << endl;

}

else

{

cerr << "Il vertice non è eliminabile in quanto destinazione di ";

cerr << Vertex_Node_Ptr_1->Reference_Count << "Archi." << endl;

}

return false;

}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// determinazione del numero di vertici di cui si compone il grafo.

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

int Graph::Number_Of_Vertices_In()

{

int N_Vertex = 0 ;

Vertex_Node *Vertex_Node_Ptr ;

Vertex_Node_Ptr = Head ;

while(Vertex_Node_Ptr != 0)

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

N_Vertex++ ;

Vertex_Node_Ptr = Vertex_Node_Ptr->Next_Vertex ;

}

return N_Vertex ;

}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// Determinazione se il vertice appartiene o meno al grafo con restituzione del puntatore al vertice stesso nel caso

// venga individuato, altrimenti viene restituito il puntatore che chiude la lista cioè 0 e quindi la funzione restituisce

// FALSE se il vertice non viene individuato.

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

Vertex_Node* Graph::Is_Member_Of(Gen_Data_Ptr The_Attribute)

{

Vertex_Node *Vertex_Node_Ptr ;

Vertex_Node_Ptr = Head ;

while((Vertex_Node_Ptr != 0) &&

!(The_Attribute->Is_Equal(Vertex_Node_Ptr->Vertex_Attribute)))

{

Vertex_Node_Ptr = Vertex_Node_Ptr->Next_Vertex ;

}

return Vertex_Node_Ptr ;

}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//Questa member function esegue la creazione di un arco previo controllo della esistenza del vertice sorgente e destinazione

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

bool Graph::Create_An_Arc(Gen_Data_Ptr Source_Vertex, Gen_Data_Ptr Dest_Vertex, Gen_Data_Ptr The_Attribute)

{

Vertex_Node *Source_Vertex_Ptr ;

Source_Vertex_Ptr = Is_Member_Of(Source_Vertex);

if(Source_Vertex_Ptr == 0)

{

cerr << "Il vertice sorgente è inesistente\n";

return false;

}

Vertex_Node *Dest_Vertex_Ptr ;

Dest_Vertex_Ptr = Is_Member_Of(Dest_Vertex);

if(Dest_Vertex_Ptr == 0)

{

cerr << "Il vertice di destinazione è inesistente\n";

return false;

}

// Incremento il reference count dell'arco di destinazione

Dest_Vertex_Ptr->Reference_Count++ ;

// Creazione dell'arco

Source_Vertex_Ptr->Arc_List_Ptr->Insert(The_Attribute,Dest_Vertex);

return true;

}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//Visualizzazione di tutti i nodi e di tutti gli archi appartenenti al grafo.

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void Graph::Display_Graph()

{

if(Head == 0)

{

cout << "No Vertex in this Graph " << endl << endl;

}

else

{

Vertex_Node *Vertex_Node_Ptr ;

Vertex_Node_Ptr = Head ;

while(Vertex_Node_Ptr != 0)

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

Vertex_Node_Ptr->Display_Vertex_And_Arcs() ;

Vertex_Node_Ptr = Vertex_Node_Ptr->Next_Vertex ;

}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//Rimozione di un dato arco previo controllo della esistenza dello stesso. La funzione esegue anche

// il decremento del REFERENCE_COUNT del vertice di destinazione della arco.

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

bool Graph::Remove_Arc(Gen_Data_Ptr Source_Vertex, Gen_Data_Ptr Dest_Vertex, Gen_Data_Ptr The_Arc)

{

// controllo che il vertice sorgente esista

Vertex_Node *Source_Vertex_Ptr ;

Source_Vertex_Ptr = Is_Member_Of(Source_Vertex);

if(Source_Vertex_Ptr == 0)

{

cerr << "\nIl vertice sorgente è inesistente";

// mostro la lista dei vertici

Display_Only_Vertex();

return false;

}

Vertex_Node *Dest_Vertex_Ptr ;

Dest_Vertex_Ptr = Is_Member_Of(Dest_Vertex);

if(Dest_Vertex_Ptr == 0)

{

cerr << "\nIl vertice di destinazione è inesistente";

Source_Vertex_Ptr->Display_Vertex_And_Arcs();

return false;

}

Arc_Node *Arc_Node_Ptr ;

Arc_Node_Ptr = Source_Vertex_Ptr->Arc_List_Ptr->Is_Member_Of(The_Arc,Dest_Vertex);

if(Arc_Node_Ptr ==0)

{

cerr << "\nL'arco da eliminare è inesistente";

Source_Vertex_Ptr->Display_Vertex_And_Arcs();

return false;

}

else

{

Source_Vertex_Ptr->Arc_List_Ptr->Remove(The_Arc,Dest_Vertex);

Dest_Vertex_Ptr->Reference_Count--;

return true;

}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//Eliminazione di tutti gli archi e di tutti i vertici appartenenti al grafo, questa per compatibilità col controllo del

//Reference_Count avviene eliminando prima da ogni vertice gli archi uscenti e poi eliminando tutti i vertici.

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void Graph::Clear()

{

Vertex_Node *Vertex_Node_Ptr ;

Vertex_Node_Ptr = Head ;

// Rimozione degli archi da tutti i vertici

while(Vertex_Node_Ptr != 0)

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

Vertex_Node_Ptr->Arc_List_Ptr->Clear();

Vertex_Node_Ptr->Reference_Count = 0 ;

Vertex_Node_Ptr = Vertex_Node_Ptr->Next_Vertex;

}

// Rimozione dei vertici

Vertex_Node_Ptr = Head ;

while(Vertex_Node_Ptr != 0)

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

Remove_Vertex(Vertex_Node_Ptr->Vertex_Attribute);

Vertex_Node_Ptr = Head ;

}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// Calcolo del numero degli archi presenti nel grafo ottenuto applicando ad ogni vertice la omonima

// funzione definita per l´ARC_LIST .

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

int Graph::Number_Of_Arcs_In()

{

int N_Arcs = 0 ;

Vertex_Node *Vertex_Node_Ptr ;

Vertex_Node_Ptr = Head ;

while(Vertex_Node_Ptr != 0)

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

N_Arcs = N_Arcs + (Vertex_Node_Ptr->Arc_List_Ptr->Number_Of_Arcs_In()) ;

Vertex_Node_Ptr = Vertex_Node_Ptr->Next_Vertex ;

}

return N_Arcs ;

}

b) Descrizione ed implementazione del polimorfismo

Col termine polimorfismo intendiamo la capacità di una classe base di definire delle funzioni le quali vengono ridefinite dalle classi derivate, e la possibilità del compilatore di eseguire un late binding che richiami il metodo per la giusta classe derivata mediante un controllo sull´oggetto richiamante la funzione. In tale contesto forse la applicazione più significativa è proprio questa da noi implementata ossia la possibilità di evitare di scrivere per ogni funzione altre n funzioni per implementare n possibili tipi di dato.

La soluzione consiste nell´impostare una classe astratta ELEMENT dalla quale derivano n classi reali relative ad n diversi tipi di dato, nel nostro caso sono state implementate FLOAT_OBJ , INT_OBJ e CHAR_OBJ , ognuna delle quali ridefinisce il costruttore, la funzione Display e la funzione IS_EQUAL successivamente descritta.

ELEMENT

// Element.h: interface for the Element class.

//////////////////////////////////////////////////////////////////////

#if !defined(AFX_ELEMENT_H__25FF6141_7852_11D1_BECF_444553540000__INCLUDED_)

#define AFX_ELEMENT_H__25FF6141_7852_11D1_BECF_444553540000__INCLUDED_

#if _MSC_VER >= 1000

#pragma once

#endif // _MSC_VER >= 1000

typedef char Class_Name[20];

#include <string.h>

class Element

{

public:

virtual bool Is_Equal(Element* Element_Ptr);

virtual void Display();

char* Get_Class();

Element();

virtual ~Element();

protected:

Class_Name My_Class;

};

typedef Element *Gen_Data_Ptr ; // definisce un puntatore alla classe Element

#endif // !defined(AFX_ELEMENT_H__25FF6141_7852_11D1_BECF_444553540000__INCLUDED_)

Questa classe ha come unico dato protected e quindi ereditabile dalle classi derivate il nome della classe, informazione che sarà utile laddove di un dato oggetto si dovrà determinare a quale classe derivata appartiene e se esso è puntato da un puntatore alla classe madre ELEMENT.

Viene inoltre definito un puntatore a questa classe che sarà poi utilizzato in tutte le funzioni che importeranno ELEMENT.H per individuare un puntatore ad un tipo di dato generico.

La dichiarazione delle funzioni public è la seguente :

// Element.cpp: implementation of the Element class.

//////////////////////////////////////////////////////////////////////

#include "Element.h"

//////////////////////////////////////////////////////////////////////

// Construction/Destruction

//////////////////////////////////////////////////////////////////////

Element::Element()

{

strcpy(My_Class, "Elemento");

}

Element::~Element()

{

}

///////////////////////////////////////////////////////////////////////

//Restituisce il nome della classe

///////////////////////////////////////////////////////////////////////

char* Element::Get_Class()

{

return My_Class;

}

///////////////////////////////////////////////////////////////////////

//Questa funzione è ridefinita dalle classi derivate.

///////////////////////////////////////////////////////////////////////

void Element::Display()

{

}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//Questa funzione è virtual e quindi ridefinita dalle classi derivate, essa si occupa di stabilire l´uguaglianza dei dati

//della classe cui viene applicato il metodo con la classe puntata dal puntatore che si riceve in ingresso.

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

bool Element::Is_Equal(Element * Element_Ptr)

{

return false;

}

Vediamo ora come le classi derivate ridefiniscono le funzioni virtual della classe ELEMENT :

INT_OBJ

// Int_Obj.h: interface for the Int_Obj class.

//////////////////////////////////////////////////////////////////////

#if !defined(AFX_INT_OBJ_H__25FF6142_7852_11D1_BECF_444553540000__INCLUDED_)

#define AFX_INT_OBJ_H__25FF6142_7852_11D1_BECF_444553540000__INCLUDED_

#if _MSC_VER >= 1000

#pragma once

#endif // _MSC_VER >= 1000

#include "Element.h"

class Int_Obj : public Element

{

public:

void Display();

bool Is_Equal(Element* Element_Ptr);

int Get_Val();

Int_Obj();

Int_Obj(int Int_Data);

virtual ~Int_Obj();

protected:

int Value;

};

#endif // !defined(AFX_INT_OBJ_H__25FF6142_7852_11D1_BECF_444553540000__INCLUDED_)

In questo caso l´unico dato protected è Value il quale è accessibile solo dalla classe Int_Obj e non dalla classe madre il che impone che anche se il codice della Display è uguale per tutte e 3 le classi derivate, tale codice non è implementabile nella classe base.

La corrispondente dichiarazione è la seguente:

// Int_Obj.cpp: implementation of the Int_Obj class.

//////////////////////////////////////////////////////////////////////

#include <iostream.h>

#include "Int_Obj.h"

//////////////////////////////////////////////////////////////////////

// Construction/Destruction

//////////////////////////////////////////////////////////////////////

Int_Obj::Int_Obj()

{

strcpy(My_Class, "Int_Obj");

}

Int_Obj::~Int_Obj()

{

}

///////////////////////////////////////////////////////////////////////

// Costruttore inizializzatore

///////////////////////////////////////////////////////////////////////

Int_Obj::Int_Obj(int Int_Data)

{

strcpy(My_Class, "Int_Obj");

Value = Int_Data ;

}

///////////////////////////////////////////////////////////////////////

// Get_Val

///////////////////////////////////////////////////////////////////////

Int_Obj::Get_Val()

{

return Value;

}

///////////////////////////////////////////////////////////////////////

// Display

///////////////////////////////////////////////////////////////////////

void Int_Obj::Display()

{

cout << Value ;

}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// IS_EQUAL

//Questa funzione consente di verificare se il Value della oggetto per il quale è richiamata è uguale al Value

//della oggetto di tipo ELEMENT che riceve in ingresso. Ciò avviene previa conversione del puntatore ad

// ELEMENT in un puntatore a INT_OBJ.

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

bool Int_Obj::Is_Equal(Element* Element_Ptr)

{

// la strcmp restituisce 0 se le 2 stringhe sono uguali

if(strcmp(Element_Ptr->Get_Class(),"Int_Obj"))

return false;

else

{

// converto il puntatore generico in un puntatore ad interi

Int_Obj *Int_Obj_Ptr = (Int_Obj *)Element_Ptr;

// confronto i dati puntati dai 2 puntatori

return(Get_Val()==(Int_Obj_Ptr->Get_Val()));

}

CHAR_OBJ

//Char_Obj.h: interface for the Char_Obj class.

//////////////////////////////////////////////////////////////////////

#if !defined(AFX_HAR_OBJ_H__882EFA81_7A44_11D1_BECF_444553540000__INCLUDED_)

#define AFX_HAR_OBJ_H__882EFA81_7A44_11D1_BECF_444553540000__INCLUDED_

#if _MSC_VER >= 1000

#pragma once

#endif // _MSC_VER >= 1000

#include "Element.h"

class Char_Obj : public Element

{

protected:

char Value;

public:

Char_Obj();

Char_Obj(char Char_Data);

virtual ~Char_Obj();

void Display();

bool Is_Equal(Element* Element_Ptr);

char Get_Val();

};

#endif // !defined(AFX_HAR_OBJ_H__882EFA81_7A44_11D1_BECF_444553540000__INCLUDED_)

La corrispondente dichiarazione è la seguente:

// Char_Obj.cpp: implementation of the Char_Obj class.

//////////////////////////////////////////////////////////////////////

#include "har_Obj.h"

#include <iostream.h>

//////////////////////////////////////////////////////////////////////

// Construction/Destruction

//////////////////////////////////////////////////////////////////////

Char_Obj::Char_Obj()

{

strcpy(My_Class, "Char_Obj");

}

///////////////////////////////////////////////////////////////////////

// Costruttore inizializzatore

///////////////////////////////////////////////////////////////////////

Char_Obj::Char_Obj(char Char_Data)

{

strcpy(My_Class, "Char_Obj");

Value = Char_Data ;

}

Char_Obj::~Char_Obj()

{

}

///////////////////////////////////////////////////////////////////////

// GET_VAL

///////////////////////////////////////////////////////////////////////

char Char_Obj::Get_Val()

{

return Value;

}

bool Char_Obj::Is_Equal(Element* Element_Ptr)

{

// la strcmp restituisce 0 se le 2 stringhe sono uguali

if(strcmp(Element_Ptr->Get_Class(),"Char_Obj"))

return false;

else

{

// converto il puntatore generico in un puntatore

// ad interi

Char_Obj *Char_Obj_Ptr = (Char_Obj *)Element_Ptr;

// confronto i dati puntati dai 2 puntatori

return(Get_Val()==(Char_Obj_Ptr->Get_Val()));

}

///////////////////////////////////////////////////////////////////////

// Display

///////////////////////////////////////////////////////////////////////

void Char_Obj::Display()

{

cout << Value ;

}

FLOAT_OBJ

// Float_Obj.h: interface for the Float_Obj class.

//////////////////////////////////////////////////////////////////////

#if !defined(AFX_FLOAT_OBJ_H__882EFA82_7A44_11D1_BECF_444553540000__INCLUDED_)

#define AFX_FLOAT_OBJ_H__882EFA82_7A44_11D1_BECF_444553540000__INCLUDED_

#if _MSC_VER >= 1000

#pragma once

#endif // _MSC_VER >= 1000

#include "Element.h"

class Float_Obj : public Element

{

public:

Float_Obj();

Float_Obj(float Float_Data);

virtual ~Float_Obj();

void Display();

bool Is_Equal(Element* Element_Ptr);

float Get_Val();

protected:

float Value;

};

#endif // !defined(AFX_FLOAT_OBJ_H__882EFA82_7A44_11D1_BECF_444553540000__INCLUDED_)

La dichiarazione della classe FLOAT_OBJ è la seguente:

// Float_Obj.cpp: implementation of the Float_Obj class.

//////////////////////////////////////////////////////////////////////

#include <iostream.h>

#include "Float_Obj.h"

//////////////////////////////////////////////////////////////////////

// Construction/Destruction

//////////////////////////////////////////////////////////////////////

Float_Obj::Float_Obj()

{

strcpy(My_Class, "Float_Obj");

}

Float_Obj::~Float_Obj()

{

}

///////////////////////////////////////////////////////////////////////

// Costruttore inizializzatore

///////////////////////////////////////////////////////////////////////

Float_Obj::Float_Obj(float Float_Data)

{

strcpy(My_Class, "Float_Obj");

Value = Float_Data ;

}

///////////////////////////////////////////////////////////////////////

// GET_VAL

///////////////////////////////////////////////////////////////////////

float Float_Obj::Get_Val()

{

return Value;

}

///////////////////////////////////////////////////////////////////////

// IS_EQUAL

///////////////////////////////////////////////////////////////////////

bool Float_Obj::Is_Equal(Element* Element_Ptr)

{

// la strcmp restituisce 0 se le 2 stringhe sono uguali

if(strcmp(Element_Ptr->Get_Class(),"Float_Obj"))

return false;

else

{

// converto il puntatore generico in un puntatore a Float_Obj

Float_Obj *Float_Obj_Ptr = (Float_Obj *)Element_Ptr;

// confronto i dati puntati dai 2 puntatori

return(Get_Val()==(Float_Obj_Ptr->Get_Val()));

}

///////////////////////////////////////////////////////////////////////

// DISPLAY

///////////////////////////////////////////////////////////////////////

void Float_Obj::Display()

{

cout << Value ;

}

Come queste classi possano essere utilizzate per implementare un grafo con archi e vertici aventi attributi di qualsiasi genere tra questi ora definiti è illustrato nel seguente paragrafo.

c) Sviluppo applicativo basato sulla classe GRAPH

Il seguente applicativo nasce dall´esigenza di veder lavorare le member function definite per la classe Graph pertanto si limita ad impostare un menu delle operazioni eseguibili sulla stessa, ad ognuna delle quali è associata una funzione che, laddove necessario, provvede a richiedere all´utente dei dati di ingresso quali ad eempio gli attributi per la arco o per il vertice di destinazione o per il vertice sorgente. È inoltre presente la funzione Type_Selection che per ognuno dei casi sopra accennati consente all´utente di inserire la tipologia del dato che si intende inserire, tale funzione non farà altro che andare a istanziare il giusto oggetto tra FLOAT_OBJ, CHAR_OBJ e INT_OBJ e farlo puntare da uno dei puntatori alla classe ELEMENT aventi visibilità generale ossia Source_Name_Ptr , Dest_Name_Ptr ed Arc_Name_Ptr .

#include "Graph.h"

#include "Arc_List.h"

#include "Element.h"

#include "Int_Obj.h"

#include "har_Obj.h"

#include "Float_Obj.h"

#include <ctype.h>

#include <string.h>

#include <iostream.h>

#include <conio.h>

// 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();

//PER IL POLIMORFISMO

char Type_Selection();

void Set_Arc_Name();

void Set_Source_Vertex_Name();

void Set_Dest_Vertex_Name();

Element *Source_Name_Ptr, *Dest_Name_Ptr , *Arc_Name_Ptr ;

Graph *My_Graph ;

void main()

{

cout<<"\n\n";

cout<<" ____________________________________________________________\n";

cout<<" | |\n";

cout<<" | - PROGRAMMA DI GESTIONE DI UN GRAFO ORIENTATO - |\n";

cout<<" |____________________________________________________________ |\n";

cout<<" | * Version 1.0 * |\n";

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

cout<<" | |\n";

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

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

cout<<" | |\n";

cout<<" | IANNONE ALESSIO GRILLI GIANLUCA D`OTTAVIO ANTONIO |\n";

cout<<" | |\n";

cout<<" |__________________________________________________________ __|\n";

char response ;

cin >> response ;

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

bool again ;

My_Graph = new Graph ;

{

cout<<"\n";

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

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

cout << " * 1) Inserzione di un vertice *\n";

cout << " * 2) Inserzione di un arco *\n";

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

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

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

cout << " * 6) Eliminazione di un arco *\n";

cout << " * 7) Eliminazione di un vertice *\n";

cout << " * 8) Eliminazione di un grafo *\n";

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

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

cin >> response ;

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

switch(response)

{

case '1' :

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

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

cout << "\t\t\t**********************************\n\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\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\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\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\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\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\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\n";

Destroy_Graph();

again = true ;

continue;

case '0' :

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

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

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

again = false ;

continue;

default :

again = true ;

continue;

} // fine dello switch

} // fine del do

while(again);

}

//////////////////////////////////////////////////////////////////

//Inserzione di un vertice nel grafo

//////////////////////////////////////////////////////////////////

void Insert()

{

Set_Source_Vertex_Name();

My_Graph->Insert(Source_Name_Ptr);

}

//////////////////////////////////////////////////////////////////

//Creazione di un arco

//////////////////////////////////////////////////////////////////

void Create()

{

Set_Source_Vertex_Name();

Set_Dest_Vertex_Name();

Set_Arc_Name();

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

}

//////////////////////////////////////////////////////////////////

//Visualizzazione del grafo

//////////////////////////////////////////////////////////////////

void Display()

{

My_Graph->Display_Graph();

}

//////////////////////////////////////////////////////////////////

//Visualizzazione del numero di vertici presenti nel grafo

//////////////////////////////////////////////////////////////////

void Number_Of_Vertices_In()

{

cout << "Nel Grafo sono presenti ";

cout << My_Graph->Number_Of_Vertices_In();

cout << " vertici." << endl;

}

//////////////////////////////////////////////////////////////////

//Visualizzazione del numero di archi presenti nel grafo

//////////////////////////////////////////////////////////////////

void Number_Of_Arcs_In()

{

cout << "Nel Grafo sono presenti ";

cout << My_Graph->Number_Of_Arcs_In();

cout << " archi." << endl;

}

//////////////////////////////////////////////////////////////////

//Eliminazione di un arco dal grafo

//////////////////////////////////////////////////////////////////

void Destroy_Arc()

{

Set_Source_Vertex_Name();

Set_Dest_Vertex_Name();

Set_Arc_Name();

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

}

//////////////////////////////////////////////////////////////////

//Eliminazione di un vertice dal grafo

//////////////////////////////////////////////////////////////////

void Destroy_Vertex()

{

Set_Source_Vertex_Name();

My_Graph->Remove_Vertex(Source_Name_Ptr);

}

//////////////////////////////////////////////////////////////////

//Eliminazione del grafo

//////////////////////////////////////////////////////////////////

void Destroy_Graph()

{

My_Graph->Clear();

}

//////////////////////////////////////////////////////////////////

//Visualizzazione della schermata di selezione del tipo di dato

//////////////////////////////////////////////////////////////////

char Type_Selection()

{

char Data_Type;

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

cout << "\t* C) Char -128 to 127 *\n";

cout << "\t* F) Float 3.4*(10**-38) to 3.4*(10**+38) *\n";

cout << "\t* I) Int -2,147,483,648 to 2,147,483,647 *\n";

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

cin >> Data_Type ;

return (toupper(Data_Type)) ;

}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//Questa procedura punta Source_Name_Ptr all´indirizzo della oggetto che si istanzia dipendente

// quest´ultimo dal tipo di dato selezionato

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void Set_Source_Vertex_Name()

{

bool again;

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

{

switch(Type_Selection())

{

case 'C':

char Char_Data;

cout << "Immettere l'attributo (Char) : ";

cin >> Char_Data;

Source_Name_Ptr = new Char_Obj(Char_Data);

again = false;

continue;

case 'I':

int Int_Data;

cout << "Immettere l'attributo (Long Int) : ";

cin >> Int_Data;

Source_Name_Ptr = new Int_Obj(Int_Data);

again = false;

continue;

case 'F':

float Float_Data;

cout << "Immettere l'attributo (Float) : ";

cin >> Float_Data;

Source_Name_Ptr = new Float_Obj(Float_Data);

again = false;

continue;

default :

again = true;

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

continue;

}

}while(again == true);

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

}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//Questa procedura punta Dest_Name_Ptr all´indirizzo della oggetto che si istanzia dipendente

// quest´ultimo dal tipo di dato selezionato

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void Set_Dest_Vertex_Name()

{

bool again;

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

{

switch(Type_Selection())

{

case 'C':

char Char_Data;

cout << "Immettere l'attributo (Char) : ";

cin >> Char_Data;

Dest_Name_Ptr = new Char_Obj(Char_Data);

again = false;

continue;

case 'I':

int Int_Data;

cout << "Immettere l'attributo (Long Int) : ";

cin >> Int_Data;

Dest_Name_Ptr = new Int_Obj(Int_Data);

again = false;

continue;

case 'F':

float Float_Data;

cout << "Immettere l'attributo (Float) : ";

cin >> Float_Data;

Dest_Name_Ptr = new Float_Obj(Float_Data);

again = false;

continue;

default :

again = true;

continue;

}

}while(again == true);

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

}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//Questa procedura punta Arc_Name_Ptr all´indirizzo della oggetto che si istanzia dipendente

// quest´ultimo dal tipo di dato selezionato

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void Set_Arc_Name()

{

bool again;

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

{

switch(Type_Selection())

{

case 'C':

char Char_Data;

cout << "Immettere l'attributo (Char) : ";

cin >> Char_Data;

Arc_Name_Ptr = new Char_Obj(Char_Data);

again = false;

continue;

case 'I':

int Int_Data;

cout << "Immettere l'attributo (Long Int) : ";

cin >> Int_Data;

Arc_Name_Ptr = new Int_Obj(Int_Data);

again = false;

continue;

case 'F':

float Float_Data;

cout << "Immettere l'attributo (Float) : ";

cin >> Float_Data;

Arc_Name_Ptr = new Float_Obj(Float_Data);

again = false;

continue;

default :

again = true;

continue;

}

}while(again == true);

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

}