Home > Listati di programmi C > Elaborazioni con grafi

ELABORAZIONI CON GRAFI

Per rappresentare un grafo ho usato una variante del metodo della lista delle adiacenze.

Queste sono le strutture di dati usate:

struct nodo: memorizza, per ogni nodo, il numero dei nodi adiacenti piu' un puntatore a interi senza segno per collocare gli indici (in v_nodi[]) dei nodi adiacenti;

v_nodi[]: memorizza tutte le struct nodo che rappresentano i nodi del grafo; le struct vengono collocate a partire dal secondo posto, v_nodi[1]; ogni nodo e' quindi identificato col numero di indice della sua posizione in v_nodi[], che va da 1 a n_nodi.

v_cammino[]: memorizza i nodi attraversati durante un cammino;

v_passato[]: associa a ogni nodo, nel corso di un singolo cammino, il valore 0 se il nodo non e' ancora stato attraversato, 1 se il nodo e' stato gia' attraversato; serve per evitare di passare piu' di una volta per lo stesso nodo;

v_cammini_fatti[]: contiene puntatori a interi senza segno, per memorizzare tutti i cammini fatti in precedenza; il primo intero puntato contiene il numero di nodi del cammino, gli altri contengono l'elenco dei nodi percorsi; serve per evitare di ripetere un cammino gia' fatto;

v_soluzioni[]: array di puntatori, memorizza tutti i cammini che collegano il nodo di partenza con quello di arrivo; anche in questo array il primo intero puntato contiene il numero di nodi del cammino relativo;

I programmi possono rappresentare grafi non orientati e orientati. In un grafo non orientato, fra due nodi collegati da un arco ci deve essere la reciprocita' delle adiacenze: se il nodo 1 e' collegato al nodo 2, 2 deve essere incluso negli adiacenti di 1 e viceversa; nei grafi orientati il collegamento e' a senso unico: se l'arco va da 1 a 2, 2 figura fra gli adiacenti di 1, ma 1 non e' adiacente di 2.

Il programma scrivi.c riceve in input i dati che descrivono un grafo (nome, numero di nodi e, per ogni nodo, le sue adiacenze); ogni nodo e' identificato con un numero da 1 in poi, che coincide con l'indice di v_nodi[] che contiene la relativa struct nodo; i dati vengono salvati su due file: uno, con estensione .adc, e' un file di unsigned int che memorizza tutte le adiacenze dei nodi del grafo; l'altro, con estensione .nod, memorizza delle struct (definite come nodo_f) contenenti, per ogni nodo, il numero delle sue adiacenze e la posizione (nel file .adc) dell'indice della prima adiacenza del nodo; gli indici degli adiacenti dello stesso nodo sono salvati in modo consecutivo; le posizioni delle adiacenze sono numerate a partire da 1 fino a lunghezza-file; le struct nodo_f sono scritte nel file .nod con lo stesso ordine in cui si trovano le corrispondenti struct nodo in v_nodi[]; le estensioni .nod e .adc sono attribuite automaticamente dal programma, aggiungendole al nome del grafo.

Il programma leggi.c riceve in input il nome di un grafo (i cui dati sono stati in precedenza salvati con scrivi.c), aggiunge le estensioni .nod e .adc e legge i due file, caricando i dati relativi nell'array v_nodi[]; poi visualizza i dati che descrivono il grafo.

Il programma cammini.c legge i dati che descrivono un grafo, precedentemente salvati con scrivi.c, e cerca tutti i cammini che uniscono due nodi diversi; visualizza tali cammini in ordine crescente di lunghezza; evidenzia con punti esclamativi i cammini che passano per tutti i nodi del grafo.
L'algoritmo si basa su due cicli principali: quello esterno serve per individuare tutti i cammini che partono dal nodo di partenza; quello interno serve per procedere da un nodo all'altro, nel corso di un singolo cammino. La regola usata nel ciclo interno (attraversamento dei nodi durante un singolo cammino) e' "vai avanti finche' puoi, quando non puoi piu' andare avanti memorizza in v_cammini_fatti[] il cammino appena concluso e comincia un nuovo cammino". Il cammino si ferma quando tutti i nodi adiacenti all'ultimo attraversato o sono gia' stati attraversati (si verifica con v_passato[]) o sono tali che, aggiungendoli al cammino in corso, si ottiene un cammino gia' memorizzato in v_cammini_fatti[]; il cammino si ferma anche quando l'ultimo nodo attraversato e' il nodo di arrivo. Il ciclo esterno si ferma quando tutti i cammini che partono dal nodo di partenza sono stati effettuati; questo si verifica quando tutti gli adiacenti del nodo di partenza non sono piu' attraversabili.

cicli.c funziona in modo analogo a cammini.c, pero' cerca i cammini che hanno come punto di partenza e di arrivo lo stesso nodo (cicli o circuiti).

Con scrivi.c e' possibile anche inserire cappi (archi che collegano un nodo con se stesso) e collegamenti multipli (piu' di un arco per collegare due nodi); cammini.c e cicli.c ignorano i cappi e trattano i collegamenti multipli come se fossero un unico collegamento.

Ho previsto il caso particolare di nodi senza adiacenze, cosa che puo' capitare nei grafi orientati (nodo che ha solo archi in entrata).

Ho trattato anche il problema dei grafi pesati; a questo scopo ho definito altri dati e funzioni (file archi_lib.h e archi_lib.c). Con le struct arco e arcof e' possibile creare una lista concatenata e salvare su file (con estensione .pes) i dati che descrivono il peso (float) di ogni arco che unisce due nodi.

Con scrivipes.c e' possibile salvare su file i dati che descrivono un grafo pesato (orientato o no); vengono cosi' creati tre file con estensioni .nod, .adc e .pes. I grafi definiti con scrivipes.c possono essere elaborati anche con cammini.c, e cicli.c, che li trattano come grafi non pesati (leggendo solo i file .nod e .adc).

Con leggipes.c si possono leggere i dati dei tre file.

Con camminipes.c si trovano tutti i cammini che uniscono due nodi non coincidenti; le soluzioni vengono mostrate in ordine crescente di peso.

Non ho previsto la rilevazione dell'insufficienza di memoria delle strutture dati statiche e dinamiche usate.

Per compilare (con gcc) i programmi per grafi non pesati:

gcc -o nome_eseguibile nome_sorgente.c grafi_lib.c

Per compilare (con gcc) i programmi per grafi pesati:

gcc -o nome_eseguibile nome_sorgente.c grafi_lib.c archi_lib.c

File grafi_lib.h

File grafi_lib.c

Inserire i dati che descrivono un grafo non pesato e salvarli su file

Leggere i file che descrivono un grafo non pesato e visualizzare i dati relativi

Dato un grafo non pesato, trovare tutti i cammini che collegano due nodi non coincidenti

Dato un grafo non pesato, trovare tutti i cicli che passano per un nodo

File archi_lib.h

File archi_lib.c

Inserire i dati che descrivono un grafo pesato e salvarli su file

Leggere i file che descrivono un grafo pesato e visualizzare i dati relativi

Dato un grafo pesato, trovare tutti i cammini che collegano due nodi non coincidenti


Home


www.corradodamiano.it a cura di Corrado Damiano

posta@corradodamiano.it