[C] Creazione e stampa a video di un grafo

[jeremyj]

Salve,
ho realizzato un piccolo programma il cui scopo è quello di realizzare un grafo e stamparlo a video.

[list=1][*]#include <stdio.h>[*]#include <stdlib.h>[*][*]/*LISTA PRIMARIA CONTENENTE I VERTICI DEL GRAFO*/[*]typedef struct vertice_grafo[*]{[*]   int valore;[*]   struct vertice_grafo *vertice_succ_p;  /*PUNTATORE AL VERTICE SUCCESSIVO*/[*]   struct arco_grafo *lista_archi_p;         /*PUNTATORE ALLA LISTA DEGLI ARCHI DEL NODO*/[*]}vertice_grafo_t;[*][*]/*LISTA SECONDARIA CONTENENTE GLI ARCHI DI UN NODO*/[*]typedef struct arco_grafo[*]{[*]   int peso;[*]   struct vertice_grafo *vertice_adiac_p;  /*PUNTATORE AL VERTICE ADIACENTE*/[*]   struct arco_grafo *arco_succ_p;          /*PUNTATORE AD EVENTUALI ALTRI ARCHI DEL NODO*/[*]}arco_grafo_t;[*][*]/*DICHIARAZIONE DELLE FUNZIONI*/[*]vertice_grafo_t *crea_grafo();[*]void stampa_grafo(vertice_grafo_t *G);[*]void aggiungi_arco(vertice_grafo_t *G, int x, int y);[*][*]int main(void)[*]{[*]   vertice_grafo_t *G;[*]   [*]   G = crea_grafo();[*]   aggiungi_arco(G, 2, 3);   /*si vuole creare un arco tra i vertici 2 e 3*/[*]   stampa_grafo(G);[*][*]   return(0);[*]}[*][*]/*DEFINIZIONE FUNZIONE PER LA CREAZIONE DEL GRAFO*/[*]vertice_grafo_t *crea_grafo()[*]{[*]   int i;[*]   vertice_grafo_t *G, *L;[*]   [*]   /*CREAZIONE DI UN GRAFO CON 7 VERTICI CON VALORI DA 0 A 6 PRIVO DI ARCHI*/[*]   G = (vertice_grafo_t *)malloc(sizeof(vertice_grafo_t));[*]   G->valore = 0;[*]   G->vertice_succ_p = NULL;[*]   G->lista_archi_p = NULL;[*]   L = (vertice_grafo_t *)malloc(sizeof(vertice_grafo_t));[*]   L->valore = 1;[*]   L->vertice_succ_p = NULL;[*]   L->lista_archi_p = NULL;[*]   G->vertice_succ_p = L;[*]   for(i = 2; i < 7; i++)[*]   {[*]      L->vertice_succ_p = (vertice_grafo_t *)malloc(sizeof(vertice_grafo_t));[*]      L = L->vertice_succ_p;[*]      L->lista_archi_p = NULL;[*]      L->valore = i;[*]   }[*]   L->vertice_succ_p = NULL;[*][*]   return(G);[*]}[*][*]/*DEFINIZIONE FUNZIONE PER LA STAMPA A VIDEO*/[*]void stampa_grafo(vertice_grafo_t *G)[*]{[*]   arco_grafo_t *arco;[*]   vertice_grafo_t *G_adiacente;   /*raccoglie i vertici adiacenti dalla lista degli archi*/[*][*]   while(G != NULL)[*]   {[*]      printf("\nNodi adiacenti al nodo %d -> ", G->valore);[*]      arco = G->lista_archi_p;[*]      while(arco != NULL)[*]      {[*]         G_adiacente = arco->vertice_adiac_p;[*]         printf("%d", G->adiacente->valore);[*]         arco = arco->arco_succ_p;[*]         if(arco != NULL)[*]            printf(" -> ");[*]      }[*]      G = G->vertice_succ_p;[*]      printf("\n");[*]   }[*]   return;[*]}[*][*]/*DEFINIZIONE FUNZIONE PER AGGIUNGERE ARCO*/[*]void aggiungi_arco(vertice_grafo_t *G, int x, int y)[*]{[*]   arco_grafo_t *arco, *e;[*][*]   arco = (arco_grafo_t *)malloc(sizeof(arco_grafo_t));   /*alloca memoria per un nuovo arco*/[*][*]   while(G != NULL)    /*scorre tutti i vertici del grafo*/[*]   {[*]      if(G->valore == x)   /*se trova un vertice corrispondente al parametro x passato alla funzione*/[*]      {[*]         if(G->lista_archi_p == NULL)   /*se il nodo non ha archi*/[*]         {[*]            while(G != NULL)   /*scorre tutti i vertici del grafo*/[*]            {[*]               if(G->valore == y)[*]               {[*]                  G->lista_archi_p = arco;[*]                  arco->vertice_adiac_p = G;[*]                  arco->arco_succ_p = NULL;[*]               }[*]               G = G->vertice_succ_p;   /*scorre G*/[*]            }[*]         }[*]         else            /*se invece il nodo possiede gia degli archi*/[*]         {[*]            e = G->lista_archi_p;[*]            while(e->arco_succ_p != NULL)[*]               e = e->arco_succ_p;            /*scorre e fino all'ultimo arco gia esistente*/[*]            e->arco_succ_p = arco;          /*faccio puntare il puntatore all'arco successivo dell'ultimo arco al nuovo arco*/[*]            while(G != NULL)  /*visita tutti i vertici*/[*]            {[*]               if(G->valore == y)                /*se trova un vertice il cui valore è quello passato alla funzione*/[*]               {[*]                  e->arco_succ_p = arco;    /*dall'ultimo arco puntiamo alla locazione del nuovo arco*/ [*]                  e->vertice_adiac_p = G;    /*puntatore al vertice corrispondente al parametro y*/ [*]                  e->arco_succ_p = NULL;  [*]               }[*]            }[*]            G = G->vertice_succ_p;[*]         }[*]      }[*]      G = G->vertice_succ_p;[*]   }[*]   return;[*]}[/list=1]

La compilazione va a buon fine senza segnalare ne errori ne warning, però quando vado a lanciare il programma mi restituisce "Errore di segmentazione".
Sono giorni che rigiro il programma sottosopra ma non riesco a venirne a capo, spero che qualcuno possa darmi una mano a trovare l'errore.
Grazie

[YuYevon]

Considerando la funzione aggiungi_arco(), se la condizione "G->lista_archi_p == NULL" risulta vera, entri in un ciclo che termina nel momento in cui G risulta NULL, ma a quel punto il controllo del programma passa all'istruzione immediatamente dopo l'else che è "G = G->vertice_succ_p", ma se G è NULL questa istruzione non è lecita in quanto stai accedendo ad un puntatore nullo. Brutalmente puoi correggere aggiungendo un semplice controllo prima di questa istruzione tipo if(G). In questo modo il programma non crasha (btw, c'è un punto nel codice in cui hai scritto G->adiacente anziché G_adiacente, quindi c'è anche un errore in compilazione); per il resto non ho controllato l'output, a te l'onere.

[jeremyj]

ciao yuyeveon, per quanto riguarda G->adiacente chiedo scusa ma è solo una mia svista quando ho postato il codice (quello "originale" è corretto).
Ho provato ad aggiungere il controllo if(G) come mi hai suggerito ma ritorna sempre "errore di segmentazione".
In quel punto non dovrebbe essere tutto G ad essere null ma solo la lista degli archi (lista_archi_p), infatti con la funzione crea_grafo() viene creata la lista primaria contenente tutti i vertici e il puntatore ad ogni vertice successivo nella lista, perciò G->valore e G->vertice_succ_p non sono null pertanto quando faccio G = G->vertice_succ_p dovrei semplicemente accedere al vertice successivo e non a un puntatore null.

[YuYevon]

Originariamente inviato da jeremyj
Ho provato ad aggiungere il controllo if(G) come mi hai suggerito ma ritorna sempre "errore di segmentazione".

Per intenderci, compilando ed eseguendo esattamente il tuo stesso codice con solo la modifica (minimale) in rosso, non ottengo alcun errore di segmentazione

void aggiungi_arco(vertice_grafo_t * G, int x, int y)
{
    arco_grafo_t *arco, *e;
    arco = (arco_grafo_t *) malloc(sizeof(arco_grafo_t));	/*alloca memoria per un nuovo arco */
    while (G != NULL) {		/*scorre tutti i vertici del grafo */
	if (G->valore == x) {	/*se trova un vertice corrispondente al parametro x passato alla funzione */
	    if (G->lista_archi_p == NULL) {	/*se il nodo non ha archi */
		while (G != NULL) {	/*scorre tutti i vertici del grafo */
		    if (G->valore == y) {
			G->lista_archi_p = arco;
			arco->vertice_adiac_p = G;
			arco->arco_succ_p = NULL;
		    }
		    G = G->vertice_succ_p;	/*scorre G */
		}
	    } else {		/*se invece il nodo possiede gia degli archi */

		e = G->lista_archi_p;
		while (e->arco_succ_p != NULL)
		    e = e->arco_succ_p;	/*scorre e fino all'ultimo arco gia esistente */
		e->arco_succ_p = arco;	/*faccio puntare il puntatore all'arco successivo dell'ultimo arco al nuovo arco */
		while (G != NULL) {	/*visita tutti i vertici */
		    if (G->valore == y) {	/*se trova un vertice il cui valore è quello passato alla funzione */
			e->arco_succ_p = arco;	/*dall'ultimo arco puntiamo alla locazione del nuovo arco */
			e->vertice_adiac_p = G;	/*puntatore al vertice corrispondente al parametro y */
			e->arco_succ_p = NULL;
		    }
		}
		G = G->vertice_succ_p;
	    }
	}
	if (G)
	G = G->vertice_succ_p;
    }
    return;
}

e ho questo output (che comunque non ho controllato)

Nodi adiacenti al nodo 0 -> 

Nodi adiacenti al nodo 1 -> 

Nodi adiacenti al nodo 2 -> 

Nodi adiacenti al nodo 3 -> 3
                                                                                                                                                                       
Nodi adiacenti al nodo 4 ->                                                                                                                                            
                                                                                                                                                                       
Nodi adiacenti al nodo 5 ->                                                                                                                                            
                                                                                                                                                                       
Nodi adiacenti al nodo 6 ->

il fatto che G diventi NULL ad un certo punto e che questo ti faccia crashare il programma lo puoi verificare con delle semplicissime stampe del valore del puntatore.

EDIT: rileggendo ti ho indicato male la riga dell'errore nel mio primo messaggio. Intendevo dire l'istruzione "G = G->vertice_succ_p" dopo l'if principale, non dopo l'else. Ho notato solo ora che ce ne sono due uguali.

[jeremyj]

ciao yuyevon,
scusami per il ritardo ma questo weekend ho sempre lavorato e non ho avuto tempo di dedicarmi al c. Ho provato come mi hai suggerito te e così non va in errore di segmentazione. Ora mi resta soltanto da capire perchè viene creato l'arco tra 3 e 3, e non tra 2 e 3 come dovrebbe. Domani provo a gurdarci e correggerlo...se intanto qualcuno avesse qualche suggerimento è ben accetto.
grazie

[B3rto92]

Ciao a tutti,
anche io sono alle prese con un grafo, ed ho anche io lo stesso problema nella creazione degl'archi, quando lo vado a stampare mi stampa, come raffigurato sopra, un collegamento con lo stesso elemento.
Qualcuno ha qualche dritta?
Il codice per la creazione degl'archi è il seguente:

arco_t *arc,
*a;
/*int i=1;*/
arc = (arco_t *) malloc (sizeof(arco_t));
a = (arco_t *) malloc (sizeof(arco_t));

while(p != NULL)
{

if(strcmp(p->nome,nome2)==0)
{
printf("Trovata anche la citta d'arrivo: %s\n", nome2);
arco = p->lista_archi_p
arco->vertice_adiac_p = p;
arco->costo = euri;
arco -> durata = ore;
arco->arco_succ_p = NULL;
printf("creazione arco eseguita\n");
}

printf("%s\n", p->nome);
p = p->vertice_succ_p;

}

è una funzione che prende in input la testa della lista primaria (p), i pesi dell'arco e le 2 città da collegare.
La prima cosa che comunque non ho scritto perchè irrilevante è un ciclo che scorre tutti i vertici fino a quando non trova la città di partenza, mentre ho scritto la seconda parte, ovvero il programma cerca la città di destinazione e una volta trovata crea l'arco.
Attendo e spero in una vostra risposta.
Grazie!

[Who am I]

Crea un threrad apposito per questo problema (e usa i tag code, indenta il codice).

[B3rto92]

Originariamente inviato da Who am I
Crea un threrad apposito per questo problema (e usa i tag code, indenta il codice).

Ok, chiedo scusa, apro un nuovo thread.