C - Libreria Grafo

di
violet_prog
il
49 risposte
V
violet_prog
Utente Attivo
Iscritto da
ott, 2014
Messaggi:
159

C - Libreria Grafo

Ciao a tutti. Sto svolgendo un progetto didattico per la creazione di una libreria che gestisca un grafo. La traccia prevede una serie di funzionalità, tra cui la creazione del grafo a partire dal parsing di un file di testo secondo una codifica data. Tralasciando questo passaggio e la libreria che ho implementato per fare ciò, quel che mi preme è capire bene qual è il modo più efficiente per gestire l'implementazione delle strutture dati (liste di adiacenza e matrici di adiacenza).
La mia idea di partenza (e quella che ho al momento implementato) è la divisione di due librerie, una grafomatrice.h (e grafomatrice.c) in cui gestisco le matrici di adiacenza e le funzionalità annesse, un altra libreria grafolista.h (e grafolista.c) in cui gestisco quel che riguarda le liste di adiacenza. Il problema mi sorge nel momento in cui devo creare delle funzioni che permettano la conversione da una rappresentazione all'altra, in quanto mi tocca creare una nuova libreria ad esempio grafo.h. Ora il mio dubbio è.. Mi conviene creare una terza libreria che veda entrambe le rappresentazioni, o piuttosto creare un'unica e sola libreria grafo.h che contenga entrambe le rappresentazioni e quindi anche le funzioni di conversione? Allego il mio codice, su cui ho comunque dei dubbi(soprattutto per la struttura dati che rappresenta le matrici)

main.c (è chiaramente parziale) 
#include <stdio.h>
#include <stdlib.h>
#include "grafolista.h"
#include "grafomatrice.h"
#include "grafoparser.h"
#include "grafo.h"

int menuIniziale(void);
int menuGrafo(void);
char * scegliFile(void);
char * scriviGrafo(void);

int main()
{
    FILE *file;
    char *nome;
    GrafoAdj G=NULL;
    GrafoMatr M=0;
    int numVertici=0;
    int scelta,tipo,conv;

    printf("\t***************************************************\n");
    printf("\t*                                                 *\n");
    printf("\t*      PROGRAMMA PER LA GESTIONE DI GRAFI         *\n");
    printf("\t*                                                 *\n");
    printf("\t***************************************************\n\n\n");
    printf("Benvenuto nel programma di gestione della struttura dati dinamica: GRAFO\n");
    printf("Prima di iniziare e' necessario costruire ALMENO un Grafo.\n\n");
    system("PAUSE");

    scelta= menuIniziale();

    if (scelta==1) nome = scegliFile();
    else nome= scriviGrafo();

    file = fopen(nome,"r");

    printf("\n>>Scegli il tipo di rappresentazione:\n1)Liste di adiacenza\n2)Matrice di adiacenza\n\n");
    scanf("%d",&tipo);
    printf("\n\nINIZIO TRADUZIONE FILE...\n");
    system("PAUSE"); system("cls");
    printf("Le informazioni estratte sono le seguenti:\n\n");

    if(tipo==1) numVertici=parseGrafo(file,&G,0,tipo);        // Parse grafo
    else if(tipo==2) numVertici=parseGrafo(file,NULL,&M,tipo);

    fclose(file);

    printf("\nIl grafo creato:\n");
    if(G!=NULL) grafo_stampa(G,numVertici);
    else if (M!=NULL) stampaMatr(M,numVertici);
    else
        printf("Grafo vuoto\n");

    system("PAUSE");
    system("cls");

    printf("Converti da un tipo ad un altro:\n1)Da Lista a Matrice\n2)Da Matrice a Lista\n");
    scanf("%d",&conv);
    if(conv==1)
    {
        //CONVERTI DA LISTA A MATRICE
    }
    else
    {
        //CONVERTI DA MATRICE A LISTA
    }


    system("PAUSE");

    // DOPO AGGIUNGO QUESTA FUNZIONE scelta=menuGrafo();

    return 0;
}

int menuIniziale(void)
{
    int x;
    system("cls");
    printf("\t CREAZIONE GRAFO :\n\n");
    printf("1)Leggi il grafo da un file;\n2)Scrivi un nuovo grafo su un file.\n");
    scanf("%d",&x);

    return x;
}

char *scegliFile(void)
{
    char *nome; int x,y;

    printf("\n\nScegli uno dei file esistenti:\n1) Grafo 1\n2) Grafo 2\n3) Grafo 3\n");
    scanf("%d",&x);printf("\n");
    switch(x)
    {
    case 1:
        nome="grafo1.txt";
        break;
    case 2:
        nome="grafo2.txt";
        break;
    case 3:
        nome="grafo3.txt";
        break;
    default:
        printf("::ERRORE:: La scelta non è valida!!\n\n Riprova -> 1\nPremi un tasto qualsiasi per Uscire...\n");
        scanf("%d",&y);
        if(y==1) nome=scegliFile();
        else exit(1);
    }

    return nome;
}

char * scriviGrafo()
{
    system("cls");
    int n,x,y,j,v,i;
    char *nome="grafonew.txt";
    FILE *filenuovo=fopen("grafonew.txt","w");
    printf("\t\t.:POPOLAMENTO GRAFO:.\n\n");
    printf("Quanti vertici deve contenere il grafo? ");
    scanf("%d",&n); printf("\n");
    fprintf(filenuovo,"%c%d%c",'(',n,')');

    for(i=1;i<=n;i++)
    {
        printf("\nVertice %d :\n",i);
        fprintf(filenuovo,"%c%d%s",' ',i,"->");
        printf("\n1)Crea Archi\n2)Passa al vertice successivo\n");
        scanf("%d",&x);
        if(x==2) fprintf(filenuovo,"%s","(-0.0);");
        else
        {
            printf("Quanti archi? ");
            scanf("%d",&y);printf("\n");
            fprintf(filenuovo,"%s%d%s","(+",y,".0)");
            printf("Inserisci vertici incidenti \n");
            for(j=1;j<=y;j++)
            {
                scanf("%d",&v);
                fprintf(filenuovo,"%c%d%c%d",' ',i,'|',v);
                if(j==y) fprintf(filenuovo,"%c ",';');
            }

        }

    }

    fprintf(filenuovo,"%c",'.');
    printf("FILE SCRITTO CON SUCCESSO!!!\n");
    fclose(filenuovo);
    system("PAUSE");

    return nome;
}

int menuGrafo(void)
{
    int scelta;
    printf("\t\t.:: MENU GRAFO ::.\n\n");
    printf("1- Inserisci Vertice\n2- Inserisci Arco\n");
    printf("3- Cancella Vertice\n4- Cancella Arco\n");
    printf("5- Calcola Grafo Trasposto\n6- Visita in Ampiezza\n7- Visita in Profondità\n");
    printf("8- Stampa di un percorso tra due vertci\n9- Verifica Aciclicità del Grafo\n");
    printf("10- Cambia rappresentazione grafo.\n\n");

    scanf("%d",&scelta);


    switch (scelta)
    {
        case 1:break;
        case 2:break;
        case 3:break;
        case 4:break;
        case 5:break;
        case 6:break;
        case 7:break;
        case 8:break;
        case 9:break;
        case 10:break;
    }

    return scelta;
}
grafoparser.h 
#ifndef GRAFOPARSER_H_INCLUDED
#define GRAFOPARSER_H_INCLUDED

typedef enum {PARSX, PARDX, NUM, PUNTO, MENO, PIU, PUNT, PUNTOV, VIRG, PESO, ID} type; // Tipo dei simboli terminali

int parseGrafo (FILE *file, GrafoAdj *G, GrafoMatr *M, int tipo);
void verticiAdj (GrafoAdj G, GrafoMatr M, char nodo, FILE *file);
int confronto(FILE *file, type x);
void sposta (FILE *file, type x);
int traduciNumeroNodi(FILE *file);
int traduciIntero(FILE *file);
float traduciPeso (FILE *file);

#endif // GRAFOPARSER_H_INCLUDED
grafolista.h 
#ifndef GRAFOLISTA_H_INCLUDED
#define GRAFOLISTA_H_INCLUDED

typedef struct grafolista * GrafoAdj;
typedef struct elementoLista * nodoLista;

GrafoAdj creaGrafo(int n); //restituisce un puntatore ad una struttura dati grafo con n liste di adiacenza vuote

GrafoAdj aggiungiVertice (GrafoAdj g, char val, int i);
GrafoAdj aggiungiArco (GrafoAdj G, char curr, char val, float p);
nodoLista aggiungiInLista (nodoLista lista, char val,float p);
void grafo_stampa (GrafoAdj g,int n);
void lista_stampa(nodoLista lista);
int cercaVertice(GrafoAdj G, char nodo, int n);
int verificaArco(GrafoAdj G, int x, int y);
//int verificaAdiacenze(nodoLista lista, char y);


#endif // GRAFOLISTA_H_INCLUDED
grafolista.c 
#include <stdio.h>
#include <stdlib.h>
#include "grafolista.h"
#include <stdbool.h>

typedef struct elementoLista{
char vertice;
float peso;
//char pred; //predecessore
//int dist; //distsnza
struct elementoLista *next;
}elementoLista;

typedef struct grafolista {
int numVertici;
elementoLista ** nodi; //array di liste di adiacenza
}grafolista;

char *colore;

GrafoAdj creaGrafo(int n)
{
    GrafoAdj G; int i;
    G=(grafolista*)malloc(sizeof(grafolista));
    if(G==NULL)printf("Errore allocazione grafo!\n");
    else
    {
        G->nodi=(elementoLista**)malloc(n*sizeof(elementoLista*)); //alloca l'array di liste
        if((G->nodi==NULL)&&(n>0))
        {
            printf("Errore allocazione archi!\n");
            free(G);
            G=NULL;
        }
        else
        {
            G->numVertici=n;
            colore=(char*)malloc(n*sizeof(char));
            for(i=0;i<n;i++)
            {
                G->nodi[i]=NULL;
                colore[i]='b';
            }
       }
   }

   printf("\tGRAFO CREATO!\n\n");
   return G;
}

GrafoAdj aggiungiVertice (GrafoAdj G, char val, int i)
{
    printf("Sono in aggiungi vertice, con i=%d e val=%c\n",i,val);

    if(G->nodi[i]==NULL)
    {
        G->nodi[i]=(elementoLista*)malloc(sizeof(elementoLista));
        G->nodi[i]->vertice=val;
        G->nodi[i]->peso=0.0;
        G->nodi[i]->next=NULL;

        printf("\tAggiunto vertice %c in posizione %d\n",val,i);

        return G;
    }
    else
        return aggiungiVertice(G,val,i+1);


}

GrafoAdj aggiungiArco (GrafoAdj G, char curr, char val, float p)
{
    printf("Sono in aggiungiArco con curr=%c e nodo da inserire=%c\n",curr,val);

    int i=cercaVertice(G,curr,G->numVertici); //ritorna l'indice di curr
    printf("NODO CORRENTE G->nodi[%d]= %c\n",i,G->nodi[i]->vertice);

    G->nodi[i]->next=aggiungiInLista(G->nodi[i]->next,val,p);


    printf("\tAGGIUNTO ARCO DA %c A %c\n",curr,val);
    return G;
}

nodoLista aggiungiInLista (nodoLista lista, char val, float p)
{
    if(lista==NULL)
    {
        lista=(elementoLista*)malloc(sizeof(elementoLista));
        lista->vertice=val;
        lista->peso=p; printf("Inserito peso= %.2f\n",lista->peso);
        lista->next=NULL;
    }
    else
        lista->next=aggiungiInLista(lista->next,val,p);

    return lista;
}


int cercaVertice(GrafoAdj G, char nodo, int n)
{
    int i=0;
    while((i<n)&&(G->nodi[i]!=NULL))
    {
        if(G->nodi[i]->vertice==nodo)
            return i;

        i++;
    }

  return 0;
}

void grafo_stampa (GrafoAdj g, int n)
{
    int i;
    if (g==NULL) { printf("\n"); return;}
    else
    {
        for(i=0;i<n;i++)
        {
            printf("%c ",g->nodi[i]->vertice);
            if(g->nodi[i]->next!=NULL)
            {
                    printf(" -> ");
                    lista_stampa(g->nodi[i]->next);
            }
            else printf(" -> NULL \n");


        }
    }
}

void lista_stampa(nodoLista lista) {

    if (lista == NULL) {printf("\n"); return;}
    else
    {
        if(abs(lista->peso) > 0) printf("(%.2f)",lista->peso);
        printf("%c",lista->vertice);
        if(lista->next!=NULL) printf(",");
        lista_stampa(lista->next);
        }
}


int verificaArco(GrafoAdj G,int x,int y)
{
    printf("x=%d y=%d\n",x,y);
    int arco;
    nodoLista DA=G->nodi[x]->next;
    char A=G->nodi[y]->vertice;

    while(DA!=NULL)
    {
        if(DA->vertice==A)
            return 1;
        else
            DA=DA->next;
    }

    return 0;
}
grafomatrice.h 
//grafomatrice.h

#ifndef GRAFOMATRICE_H_INCLUDED
#define GRAFOMATRICE_H_INCLUDED

typedef struct grafomatrice * GrafoMatr;

GrafoMatr creaMatrice(int n);
GrafoMatr aggiungiVerticeMatr (GrafoMatr M, char val, int i, int n);
GrafoMatr aggiungiArcoMatr(GrafoMatr M,char curr, char val, float peso);
int cercaVerticeMatrice(char * arrayVertici, char val,int n);
void stampaMatr (GrafoMatr M, int n);

#endif // GRAFOMATRICE_H_INCLUDED
grafomatrice.c 
#include <stdio.h>
#include <stdlib.h>
#include "grafomatrice.h"

typedef struct grafomatrice {
int numVertici;
char * vertici; //array di vertici
float ** peso; //matrice dei pesi //i pesi non posso metterli al posto dell'1 nella matr adj in quanto nn so come rapp un arco senza peso!
int ** matrice;
}grafomatrice;

GrafoMatr creaMatrice(int n)
{
    int i,j;
    GrafoMatr M=(grafomatrice*)malloc(sizeof(grafomatrice));
    M->numVertici=n;
    M->vertici=(char*)malloc((n)*sizeof(char));
    M->peso=(float**)malloc((n)*sizeof(float*));
    M->matrice=(int**)malloc((n)*sizeof(int*));
    for(i=0;i<n;i++)
    {
        M->vertici[i]=0;
        M->peso[i]=(float*)malloc((n)*sizeof(float));
        M->matrice[i]=(int*)malloc((n)*sizeof(int));
        for(j=0;j<n;j++) M->matrice[i][j]=0;
    }

    return M;
}

GrafoMatr aggiungiVerticeMatr (GrafoMatr M, char val, int i, int n)
{
    if((i<n)&&(M->vertici[i]!=val))
    {
        if(M->vertici[i]==0)
            M->vertici[i]=val;
        else
            return aggiungiVerticeMatr(M,val,i+1,n);
    }

    return M;
}

GrafoMatr aggiungiArcoMatr(GrafoMatr M,char curr, char val, float peso)
{

    int posCurr,posVal;
    int n=M->numVertici;

    posCurr=cercaVerticeMatrice(M->vertici,curr,n); //esiste sicuramente
    posVal=cercaVerticeMatrice(M->vertici,val,n); //potrebbe non esser stato inserito

    if(M->vertici[posVal]==0)
        M=aggiungiVerticeMatr(M,val,0,n);

    M->matrice[posCurr][posVal]=1;
    M->peso[posCurr][posVal]=peso;

    return M;
}

int cercaVerticeMatrice(char * arrayVertici, char val,int n)
{
    int i=0;
    while(i<n)
    {
        if((arrayVertici[i]==val) || (arrayVertici[i]==0))//se arriva ad una casella vuota vuol dire che non ha trovato altro;
            return i;
        else i++;
    }

    return 0;
}

void stampaMatr (GrafoMatr M, int n)
{
    int i,j;
    printf("    ");
    for(i=0;i<n;i++) printf("%c ",M->vertici[i]);
    printf("\n\n");
    for(i=0;i<n;i++)
    {
        printf("  %c ",M->vertici[i]);
        for(j=0;j<n;j++)
        {
            //if(abs(M->peso[i][j]) > 0) printf("(%.2f)",M->peso[i][j]);
            printf("%d ",M->matrice[i][j]);
        }

        printf("\n");
    }
}
grafo.h 
#ifndef GRAFO_H_INCLUDED
#define GRAFO_H_INCLUDED

GrafoMatr convertToMatrice (GrafoAdj G, GrafoMatr M, int n);
GrafoAdj convertToLista (GrafoAdj G, GrafoMatr M, int n);

#endif // GRAFO_H_INCLUDED
grafoparser.c non l'ho scritto in quanto non avendo precisato la grammatica stabilita, mi sembrava inutile. Ed inoltre perchè il programma compila ed esegue, il mio interesse è un consiglio sulle strutture dati e appunto la divisione di esse nelle varie librerie.
Grazie per l'attenzione.

49 Risposte

  • S
    SVNiko
    Molto attivo
    Iscritto da
    set, 2014
    Messaggi:
    535

    Re: C - Libreria Grafo

    Nell'ambito della modularità e riutilizzo di librerie esistenti, la soluzione che hai adottato è valida. Vale a dire ho due librerie belle e pronte e mi serve qualcosa che mi converte nell'una o nell'altra all'occorrenza, quindi una libreria grafo.h (grafo.c) che implementa le due finzioni di conversione.

    Nell'ottica di ristrutturare il codice adeguandolo al caso specifico potresti pensare ad un'unica libreria che gestisce il grafo con le due rappresentazione che ti servono e che inglobano le funzioni di conversione.

    Dal mio punto di vista sono solo scelte progettuali, spesso si ricicla molto del lavoro che si ha pronto per offrire una soluzione immediata, poi in seguito si ristruttura alla bisogna. Attenta a prendere per le molle questo: tutto parte comunque da un progetto iniziale che va comunque impostato, altrimenti in fase di ristrutturazione sarà necessario riprogettare il codice e non ristrutturarlo.

    Per quanto riguarda la rappresentazione a matrice, puoi utilizzare la matrice stessa per rappresentare i pesi, l'arco che non c'è ha peso 0.0 e tutti gli altri hanno il relativo peso.
  • V
    violet_prog
    Utente Attivo
    Iscritto da
    ott, 2014
    Messaggi:
    159

    Re: C - Libreria Grafo

    SVNiko ha scritto:

    Nell'ambito della modularità e riutilizzo di librerie esistenti, la soluzione che hai adottato è valida. Vale a dire ho due librerie belle e pronte e mi serve qualcosa che mi converte nell'una o nell'altra all'occorrenza, quindi una libreria grafo.h (grafo.c) che implementa le due finzioni di conversione.
    Nell'ottica di ristrutturare il codice adeguandolo al caso specifico potresti pensare ad un'unica libreria che gestisce il grafo con le due rappresentazione che ti servono e che inglobano le funzioni di conversione.
    Io come scelta iniziale avevo diviso le tre librerie perchè avevo pensato appunto alla modularità. Ora ho provato ad un unirle in un unica libreria e scrivere il codice mi risulta molto più semplice. Ecco perchè chiedevo consiglio.
    Per quanto riguarda la rappresentazione a matrice, puoi utilizzare la matrice stessa per rappresentare i pesi, l'arco che non c'è ha peso 0.0 e tutti gli altri hanno il relativo peso.
    Da traccia il peso è opzionale, quindi alcuni archi ce l'hanno e altri no, perciò 0.0 non andrebbe bene, ecco perchè ho scritto una matrice apposta per i pesi, ma anzichè implementare due matrici mi piacerebbe trovare una soluzione alternativa.
  • S
    SVNiko
    Molto attivo
    Iscritto da
    set, 2014
    Messaggi:
    535

    Re: C - Libreria Grafo

    violet_prog ha scritto:

    Io come scelta iniziale avevo diviso le tre librerie perchè avevo pensato appunto alla modularità. Ora ho provato ad un unirle in un unica libreria e scrivere il codice mi risulta molto più semplice. Ecco perchè chiedevo consiglio.
    Le librerie in questione mi sembrano due: grafomatrice e grafolista.
    La libreria grafoparser esaurisce la sua funzione nel parsificare i dati in ingresso ed è giusto sia una libreria autonoma.

    Le due librerie che puoi fondere sono grafomatrice e grafolista, quindi se hai voglia di ristrutturare il codice le fondi, se non hai voglia di farlo allora implementi una nuova libreria che fa le conversioni.
    Puoi pure implementare nuove funzioni di conversione nei singoli moduli di grafomatrice e grafolista.

    violet_prog ha scritto:

    Da traccia il peso è opzionale, quindi alcuni archi ce l'hanno e altri no, perciò 0.0 non andrebbe bene, ecco perchè ho scritto una matrice apposta per i pesi, ma anzichè implementare due matrici mi piacerebbe trovare una soluzione alternativa.
    Quando il peso dell'arco non c'è che valore si attribuisce?
  • V
    violet_prog
    Utente Attivo
    Iscritto da
    ott, 2014
    Messaggi:
    159

    Re: C - Libreria Grafo

    SVNiko ha scritto:

    Le due librerie che puoi fondere sono grafomatrice e grafolista, quindi se hai voglia di ristrutturare il codice le fondi, se non hai voglia di farlo allora implementi una nuova libreria che fa le conversioni.
    Puoi pure implementare nuove funzioni di conversione nei singoli moduli di grafomatrice e grafolista.
    Con le "tre librerie" mi riferivo a grafolista grafomatrice e grafo.
    Comunque ho creato un'unica libreria, perchè mi risulta tutto più semplice.

    grafo.h 
    #ifndef GRAFO_H_INCLUDED
#define GRAFO_H_INCLUDED

//RAPPRESENTAZIONE MATRICI DI ADIACENZE
typedef struct grafomatrice * GrafoMatr;
GrafoMatr creaGrafoMatr(int n);
GrafoMatr aggiungiVerticeMatr (GrafoMatr M, char val, int i, int n);
GrafoMatr aggiungiArcoMatr(GrafoMatr M,char curr, char val, float peso);
int cercaVerticeMatr(char * arrayVertici, char val,int n);
void stampaGrafoMatr (GrafoMatr M, int n);


//RAPPRESENTAZIONE LISTE DI ADIACENZA
typedef struct grafolista * GrafoAdj;
typedef struct elementoLista * nodoLista;
GrafoAdj creaGrafoLista(int n); //restituisce un puntatore ad una struttura dati grafo con n liste di adiacenza vuote
GrafoAdj aggiungiVerticeLista (GrafoAdj g, char val, int i);
GrafoAdj aggiungiArcoLista (GrafoAdj G, char curr, char val, float p);
nodoLista aggiungiInLista (nodoLista lista, char val,float p);
void stampaGrafoLista (GrafoAdj g,int n);
void stampaLista(nodoLista lista);
int cercaVerticeLista(GrafoAdj G, char nodo, int n);
int verificaArcoLista(GrafoAdj G, int x, int y);
//int verificaAdiacenze(nodoLista lista, char y);


//FUNZIONI DI CONVERSIONE TRA LE RAPPRESENTAZIONI
GrafoMatr convertToMatrice (GrafoAdj G, GrafoMatr M, int n);
GrafoAdj convertToLista (GrafoAdj G, GrafoMatr M, int n);

#endif // GRAFO_H_INCLUDED
    Va bene così? O era meglio la divisione?

    SVNiko ha scritto:

    Quando il peso dell'arco non c'è che valore si attribuisce?
    Solitamente io attribuisco 0 se non esiste l'arco, 1 se esiste. Nel caso dei pesi al posto dell'1 si poteva mettere il peso stesso, ma siccome nella traccia il peso è opzionale, poi non ho modo di rappresentare la non esistenza dell'arco, e l'esistenza dell'arco ma senza peso. Anche perchè il peso è un numero reale con segno, può essere anche negativo, quindi da escludere la possibilità anche di rappresentare la non esistenza dell'arco con num negativo. Ecco perchè ho creato una matrice dei pesi.
  • S
    SVNiko
    Molto attivo
    Iscritto da
    set, 2014
    Messaggi:
    535

    Re: C - Libreria Grafo

    Se devi ristrutturare la libreria grafo in un'unica libreria, non puoi fare un copia incolla delle due librerie costruendo un unico .h e .c; dovresti strutturare la libreria ad esempio così:

    .h 
    
typedef struct grafo * GRAFO;

GRAFO creaGrafoMatr(int n);
GRAFO creaGrafoList(int n);
... ecc
    .c 
    
typedef struct grafo {
int numVertici;
elementoLista ** nodi; //array di liste di adiacenza
int ** matrice; //matrice delle adiacenze
float ** peso;
}Grafo;

/* Tutte le implementazioni dove:
   1) se sono con lista implementi l'array 
   2) se matrice implementi la matrice

  Quando devi passare da una rappresentazione all'altra avrai una funzione che metterà a NULL il puntatore che non serve più e costruirà la nuova rappresentazione del grafo.
*/
    Diversamente lascia le due liste così come sono e implementa all'interno di ciascuna le funzioni che data una rappresentazione costruiscono l'altra.

    violet_prog ha scritto:

    Solitamente io attribuisco 0 se non esiste l'arco, 1 se esiste. Nel caso dei pesi al posto dell'1 si poteva mettere il peso stesso, ma siccome nella traccia il peso è opzionale, poi non ho modo di rappresentare la non esistenza dell'arco, e l'esistenza dell'arco ma senza peso. Anche perchè il peso è un numero reale con segno, può essere anche negativo, quindi da escludere la possibilità anche di rappresentare la non esistenza dell'arco con num negativo. Ecco perchè ho creato una matrice dei pesi.
    Il problema dei pesi, negativi o float che siano, si risolve costruendo una matrice di float dove il valore 0.0 (oppure un qualsiasi valore sentinella) rappresenta la non esistenza dell'arco e il valore x negativo o positivo che sia indica sia l'esistenza dell'arco che il suo peso.
  • V
    violet_prog
    Utente Attivo
    Iscritto da
    ott, 2014
    Messaggi:
    159

    Re: C - Libreria Grafo

    SVNiko ha scritto:

    Il problema dei pesi, negativi o float che siano, si risolve costruendo una matrice di float dove il valore 0.0 (oppure un qualsiasi valore sentinella) rappresenta la non esistenza dell'arco e il valore x negativo o positivo che sia indica sia l'esistenza dell'arco che il suo peso.
    Esatto. Ed è questo il motivo per cui in questo caso devo implementare per forza una matrice per i pesi. Faccio un esempio, come da traccia.

    A->B, (-2.5)C
    B->C
    C->NULL

    A B C
    A 0 1 1
    B 0 0 1
    C 0 0 0

    In questo caso se mettessi i pesi al posto di 0,1 perderei l'arco B->C, perchè il peso è 0.0 ma l'arco esiste.

    Per quanto riguarda la struttura, premettendo che non posso fare come mi hai consigliato perchè devo tenere distinte le due rappresentazioni utilizzando due struct diverse, come mai non va bene una cosa del genere?
    grafo.h 
    #ifndef GRAFO_H_INCLUDED
#define GRAFO_H_INCLUDED

//RAPPRESENTAZIONE MATRICI DI ADIACENZE
typedef struct grafomatrice * GrafoMatr;
GrafoMatr creaGrafoMatr(int n);
GrafoMatr aggiungiVerticeMatr (GrafoMatr M, char val, int i, int n);
GrafoMatr aggiungiArcoMatr(GrafoMatr M,char curr, char val, float peso);
int cercaVerticeMatr(char * arrayVertici, char val,int n);
void stampaGrafoMatr (GrafoMatr M, int n);


//RAPPRESENTAZIONE LISTE DI ADIACENZA
typedef struct grafolista * GrafoAdj;
typedef struct elementoLista * nodoLista;
GrafoAdj creaGrafoLista(int n); //restituisce un puntatore ad una struttura dati grafo con n liste di adiacenza vuote
GrafoAdj aggiungiVerticeLista (GrafoAdj g, char val, int i);
GrafoAdj aggiungiArcoLista (GrafoAdj G, char curr, char val, float p);
nodoLista aggiungiInLista (nodoLista lista, char val,float p);
void stampaGrafoLista (GrafoAdj g,int n);
void stampaLista(nodoLista lista);
int cercaVerticeLista(GrafoAdj G, char nodo, int n);
int verificaArcoLista(GrafoAdj G, int x, int y);
//int verificaAdiacenze(nodoLista lista, char y);


//FUNZIONI DI CONVERSIONE TRA LE RAPPRESENTAZIONI
GrafoMatr convertToMatrice (GrafoAdj G, int n);
GrafoAdj convertToLista (GrafoMatr M, int n);

#endif // GRAFO_H_INCLUDED
    grafo.c 
    #include <stdio.h>
#include <stdlib.h>
#include "grafo.h"

// RAPPRESENTAZIONE MATRICE DI ADIACENZA
typedef struct grafomatrice {
int numVertici;
char * vertici; //array di vertici
float ** peso; //matrice dei pesi //i pesi non posso metterli al posto dell'1 nella matr adj in quanto nn so come rapp un arco senza peso!
int ** matrice;
}grafomatrice;


GrafoMatr creaGrafoMatr(int n)
{
    int i,j;
    GrafoMatr M=(grafomatrice*)malloc(sizeof(grafomatrice));
    M->numVertici=n;
    M->vertici=(char*)malloc((n)*sizeof(char));
    M->peso=(float**)malloc((n)*sizeof(float*));
    M->matrice=(int**)malloc((n)*sizeof(int*));
    for(i=0;i<n;i++)
    {
        M->vertici[i]=0;
        M->peso[i]=(float*)malloc((n)*sizeof(float));
        M->matrice[i]=(int*)malloc((n)*sizeof(int));
        for(j=0;j<n;j++) M->matrice[i][j]=0;
    }

    return M;
}

GrafoMatr aggiungiVerticeMatr (GrafoMatr M, char val, int i, int n)
{
    if((i<n)&&(M->vertici[i]!=val))
    {
        if(M->vertici[i]==0)
            M->vertici[i]=val;
        else
            return aggiungiVerticeMatr(M,val,i+1,n);
    }

    return M;
}

GrafoMatr aggiungiArcoMatr(GrafoMatr M,char curr, char val, float peso)
{

    int posCurr,posVal;
    int n=M->numVertici;

    posCurr=cercaVerticeMatr(M->vertici,curr,n); //esiste sicuramente
    posVal=cercaVerticeMatr(M->vertici,val,n); //potrebbe non esser stato inserito

    if(M->vertici[posVal]==0)
        M=aggiungiVerticeMatr(M,val,0,n);

    M->matrice[posCurr][posVal]=1;
    M->peso[posCurr][posVal]=peso;

    return M;
}

int cercaVerticeMatr(char * arrayVertici, char val,int n)
{
    int i=0;
    while(i<n)
    {
        if((arrayVertici[i]==val) || (arrayVertici[i]==0))//se arriva ad una casella vuota vuol dire che non ha trovato altro;
            return i;
        else i++;
    }

    return 0;
}

void stampaGrafoMatr (GrafoMatr M, int n)
{
    int i,j;
    printf("\n    ");
    for(i=0;i<n;i++) printf("%c ",M->vertici[i]);
    printf("\n\n");
    for(i=0;i<n;i++)
    {
        printf("  %c ",M->vertici[i]);
        for(j=0;j<n;j++)
        {
            //if(abs(M->peso[i][j]) > 0) printf("(%.2f)",M->peso[i][j]);
            printf("%d ",M->matrice[i][j]);
        }

        printf("\n");
    }
}


// RAPPRESENTAZIONE LISTA DI ADIACENZA

typedef struct elementoLista{
char vertice;
float peso;
//char pred; //predecessore
//int dist; //distsnza
struct elementoLista *next;
}elementoLista;

typedef struct grafolista {
int numVertici;
elementoLista ** nodi; //array di liste di adiacenza
}grafolista;

char *colore;


GrafoAdj creaGrafoLista(int n)
{
    GrafoAdj G; int i;
    G=(grafolista*)malloc(sizeof(grafolista));
    if(G==NULL)printf("Errore allocazione grafo!\n");
    else
    {
        G->nodi=(elementoLista**)malloc(n*sizeof(elementoLista*)); //alloca l'array di liste
        if((G->nodi==NULL)&&(n>0))
        {
            printf("Errore allocazione archi!\n");
            free(G);
            G=NULL;
        }
        else
        {
            G->numVertici=n;
            colore=(char*)malloc(n*sizeof(char));
            for(i=0;i<n;i++)
            {
                G->nodi[i]=NULL;
                colore[i]='b';
            }
       }
   }

   printf("\tGRAFO CREATO!\n\n");
   return G;
}

GrafoAdj aggiungiVerticeLista (GrafoAdj G, char val, int i)
{
    if(G->nodi[i]==NULL)
    {
        G->nodi[i]=(elementoLista*)malloc(sizeof(elementoLista));
        G->nodi[i]->vertice=val;
        G->nodi[i]->peso=0.0;
        G->nodi[i]->next=NULL;

        return G;
    }
    else
        return aggiungiVerticeLista(G,val,i+1);


}

GrafoAdj aggiungiArcoLista (GrafoAdj G, char curr, char val, float p)
{
    int i=cercaVerticeLista(G,curr,G->numVertici); //ritorna l'indice di curr
    G->nodi[i]->next=aggiungiInLista(G->nodi[i]->next,val,p);

    return G;
}

nodoLista aggiungiInLista (nodoLista lista, char val, float p)
{
    if(lista==NULL)
    {
        lista=(elementoLista*)malloc(sizeof(elementoLista));
        lista->vertice=val;
        lista->peso=p;
        lista->next=NULL;
    }
    else
        lista->next=aggiungiInLista(lista->next,val,p);

    return lista;
}


int cercaVerticeLista(GrafoAdj G, char nodo, int n)
{
    int i=0;
    while((i<n)&&(G->nodi[i]!=NULL))
    {
        if(G->nodi[i]->vertice==nodo)
            return i;

        i++;
    }

  return 0;
}

void stampaGrafoLista (GrafoAdj g, int n)
{
    int i;
    if (g==NULL) { printf("\n"); return;}
    else
    {
        for(i=0;i<n;i++)
        {
            printf("%c ",g->nodi[i]->vertice);
            if(g->nodi[i]->next!=NULL)
            {
                    printf(" -> ");
                    stampaLista(g->nodi[i]->next);
            }
            else printf(" -> NULL \n");


        }
    }
}

void stampaLista(nodoLista lista) {

    if (lista == NULL) {printf("\n"); return;}
    else
    {
        if(abs(lista->peso) > 0) printf("(%.2f)",lista->peso);
        printf("%c",lista->vertice);
        if(lista->next!=NULL) printf(",");
        stampaLista(lista->next);
        }
}


int verificaArcoLista(GrafoAdj G,int x,int y)
{
    nodoLista DA=G->nodi[x]->next;
    char A=G->nodi[y]->vertice;

    while(DA!=NULL)
    {
        if(DA->vertice==A)
            return 1;
        else
            DA=DA->next;
    }

    return 0;
}

/*int verificaAdiacenze(ListaAdj lista, char y)
{
    int arco;
    if(lista==NULL) arco=0;
    else
    {
        if (compare(lista->vertice,y)==0) arco=1;
        else arco=verificaAdiacenze(lista->next,y,compare);
    }

    return arco;
}

*/



// CONVERSIONE RAPPRESENTAZIONI

GrafoMatr convertToMatrice (GrafoAdj G, int n)
{
    int i,j;
    GrafoMatr M=NULL; nodoLista temp;

    M=creaGrafoMatr(n);
    for(i=0;i<n;i++)
        M->vertici[i]=G->nodi[i]->vertice;

    i=0;
    while(i<n)
    {
        temp=G->nodi[i]->next;
        while(temp!=NULL)
        {
            j=cercaVerticeMatr(M->vertici,temp->vertice,n);
            M->matrice[i][j]=1;
            if(abs(temp->peso>0)) M->peso[i][j]=temp->peso;

            temp=temp->next;
        }
        i++;
    }

    return M;

}


GrafoAdj convertToLista (GrafoMatr M, int n)
{
    int i,j;
    GrafoAdj G=NULL;

    G=creaGrafoLista(n);
    for(i=0;i<n;i++)
    {
        G=aggiungiVerticeLista(G,M->vertici[i],i);
        for(j=0;j<n;j++)
        {
            if((i!=j)&&(M->matrice[i][j]))
                G=aggiungiArcoLista(G,M->vertici[i],M->vertici[j],M->peso[i][j]);
        }
    }

    return G;
}

    Chiarito questo dubbio, ti posto dopo la mia seconda domanda riferita all'eventuale divisione delle due librerie.
  • S
    SVNiko
    Molto attivo
    Iscritto da
    set, 2014
    Messaggi:
    535

    Re: C - Libreria Grafo

    Sicuramente se ben fatta funzionerà la soluzione da te proposta, però se, utilizzi due struct distinte con due distinti handler ti riferisci a due distinte librerie, quindi le tieni separate che è più logica e pulita come soluzione; inoltre, è più manutenibile.
  • V
    violet_prog
    Utente Attivo
    Iscritto da
    ott, 2014
    Messaggi:
    159

    Re: C - Libreria Grafo

    SVNiko ha scritto:

    Sicuramente se ben fatta funzionerà la soluzione da te proposta, però se, utilizzi due struct distinte con due distinti handler ti riferisci a due distinte librerie, quindi le tieni separate che è più logica e pulita come soluzione; inoltre, è più manutenibile.
    Il codice che ti ho scritto nell'ultimo messaggio funziona, anche le funzioni di conversione.
    Io inizialmente ero partita dividendo la libreria grafolista da quella matrice, nel momento in cui dovevo implementare le funzioni di conversione, mi è sorto il problema, in quanto creando una libreria grafo che vedesse grafolista.h e grafomatrice.h non riuscivo ad implementare le funzioni di conversione perchè grafo non vedeva le strutture dati. Ecco perchè poi ho unito il tutto chiedendo appunto però se non fosse una scelta sbagliata.
  • S
    SVNiko
    Molto attivo
    Iscritto da
    set, 2014
    Messaggi:
    535

    Re: C - Libreria Grafo

    Allora se tu hai un grafo implementato come lista delle adiacenze e vuoi trasformarlo in matrice delle adiacenze puoi all'interno della libreria grafoLista implementare una funzione con questo prototipo:

    int ** convertoListtoMatrix(Grafolista G, int *V);

    avrai ritornato una matrice e a quel punto puoi prenderla in carico con una funzione nella libreria grafomatrice che converte in grafo la matrice avuta, ad esempio con un prototipo come questo:

    GrafoMatrice convertoMatrixtoList(int **Matrix, int *V);

    Stessa cosa fai per la grafoMatrice.
  • V
    violet_prog
    Utente Attivo
    Iscritto da
    ott, 2014
    Messaggi:
    159

    Re: C - Libreria Grafo

    SVNiko ha scritto:

    Allora se tu hai un grafo implementato come lista delle adiacenze e vuoi trasformarlo in matrice delle adiacenze puoi all'interno della libreria grafoLista implementare una funzione con questo prototipo:

    int ** convertoListtoMatrix(Grafolista G, int *V);

    avrai ritornato una matrice e a quel punto puoi prenderla in carico con una funzione nella libreria grafomatrice che converte in grafo la matrice avuta, ad esempio con un prototipo come questo:

    GrafoMatrice convertoMatrixtoList(int **Matrix, int *V);

    Stessa cosa fai per la grafoMatrice.

    E come faccio con le altre informazioni della struttura? Tipo il peso? Oppure altre che devo aggiungere per implementare le visite in ampiezza e profondità.
  • S
    SVNiko
    Molto attivo
    Iscritto da
    set, 2014
    Messaggi:
    535

    Re: C - Libreria Grafo

    Aspetta stiamo facendo confusione o non ho capito il problema.

    Se hai un grafo implementato come lista sei d'accordo che puoi prendere i dati e ritornare una matrice? Adesso se ti si dà una matrice puoi costruire un grafo con implementazione matrice? Penso di sì.

    Se hai un grafo implementato come matrice puoi creare una funzione che ritorni solo la matrice? Adesso se ti si da una matrice puoi costruire un grafo con implementazione lista? Penso di sì.

    Da questo punto in poi puoi tutte le volte che vuoi trasformare un'implementazione in un'altra, distruggendo quella che non ti serve più per liberare memoria. Le visite varie le fai sul grafo che in quel momento hai in memoria.

    Violet_prog ha scritto:

    E come faccio con le altre informazioni della struttura? Tipo il peso?
    La storia degli archi non dichiarati e archi che non hanno peso è strana, comunque puoi sempre farti ritornare una matrice per i pesi, modificando leggermente i prototipi delle funzioni che ti ho scritto prima.
  • V
    violet_prog
    Utente Attivo
    Iscritto da
    ott, 2014
    Messaggi:
    159

    Re: C - Libreria Grafo

    SVNiko ha scritto:

    La storia degli archi non dichiarati e archi che non hanno peso è strana
    Ma non è che ci sono archi non dichiarati, è che non tutti gli archi hanno un peso.

    SVNiko ha scritto:

    comunque puoi sempre farti ritornare una matrice per i pesi, modificando leggermente i prototipi delle funzioni che ti ho scritto prima.
    E se oltre al peso, inserisco altre informazioni nella struttura? Mica posso creare una funzione per ogni informazione?! Mi sembra troppo laborioso..
  • S
    SVNiko
    Molto attivo
    Iscritto da
    set, 2014
    Messaggi:
    535

    Re: C - Libreria Grafo

    violet_prog ha scritto:

    Ma non è che ci sono archi non dichiarati, è che non tutti gli archi hanno un peso.
    Di solito quando non ci sono pesi si attribuisce peso zero. Comunque se le specifiche sono altre atteniamoci a quelle.

    violet_prog ha scritto:

    E se oltre al peso, inserisco altre informazioni nella struttura? Mica posso creare una funzione per ogni informazione?! Mi sembra troppo laborioso..
    Non hai necessità di scrivere tante funzioni, puoi sempre utilizzare i puntatori o se vuoi, puoi utilizzare una struttura che impacca tutto, che ti farai ritornare. Ad esempio: 
    
struct valoriRitornati{
       float **pesi;
       int **matrice;
}

struct valoriRitornati convertoMatrixtoList(Grafolista G, int *V);
    Oppure 
    
void convertoMatrixtoList(Grafolista G, int *V, int ***matrice, int ***pesi);
  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    6073

    Re: C - Libreria Grafo

    @SVNiko: NON peso 0, ma 1!
Devi accedere o registrarti per scrivere nel forum
49 risposte