SVNiko ha scritto:
Dobbiamo prima chiarire il problema!
Io ho inteso che tu voglia passare da una rappresentazione a matrice ad una rappresentazione a lista e viceversa. Il problema è questo?
Il problema è come strutturare la libreria in modo da poter fare anche questo, ma non solo.
Inizialmente avevo creato due librerie grafolista e grafomatrice, e volevo implementare la funzione di conversione in una terza libreria grafo, ma siccome le informazioni che devono contenere i grafi sono molte, ho pensato di creare un'unica e sola libreria grafo in cui implemento le due rappresentazioni, ma tu mi hai sconsigliato. E quindi stavo cercando di capire in che modo ovviare a questa cosa. Ti riscrivo il mio attuale e funzionante codice.
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);
GrafoAdj DFS_Lista (GrafoAdj G);
GrafoAdj DFS_Visita_Lista (GrafoAdj G,nodoLista lista,int i,int n);
//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
char * colore;
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->colore=(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->colore[i]='b';
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;
//int dist; //distanza
struct elementoLista *next;
}elementoLista;
typedef struct grafolista {
int numVertici;
char * colore;
char * pred;
elementoLista ** nodi; //array di liste di adiacenza
}grafolista;
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;
G->colore=(char*)malloc((n)*sizeof(char));
G->pred=(char*)malloc((n)*sizeof(char));
for(i=0;i<n;i++)
{
G->nodi[i]=NULL;
G->colore[i]='b';
G->pred[i]=0;
}
}
}
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;
}
GrafoAdj DFS_Lista (GrafoAdj G)
{
int i;
int n=G->numVertici;
//inizializza grafo
for(i=0;i<n;i++)
{
G->colore[i]='b';
G->pred[i]=0;
}
for(i=0;i<n;i++)
{
if(G->colore[i]=='b')
G=DFS_Visita_Lista(G,G->nodi[i],i,n);
}
printf("ritorno!\n");
return G;
}
GrafoAdj DFS_Visita_Lista (GrafoAdj G,nodoLista lista,int i,int n)
{
G->colore[i]='g';
while(lista->next!=NULL)
{
lista=lista->next;
i=cercaVerticeLista(G,lista->vertice,n);
if(G->colore[i]=='b')
{
G->pred[i]=lista->vertice;
G=DFS_Visita_Lista(G,lista,i,n);
}
}
G->colore[i]='n';
return G;
}
// 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;
}