|
Member
Iscritto dal: Nov 2007
Città: Alcamo
Messaggi: 103
|
[C] Grafi - Visite e cammini
Salve, sto studiando i grafi per un esame universitario. Mentalmente sono riuscito a "capire" cosa fare, cioè con un grafo "disegnato" saprei esattamente come l'algoritmo deve procedere passo per passo... il problema sta nell'implementazione... sul libro abbiamo solo spezzoni di pseudocodice che lasciano molto alla fantasia...
E principalmente i miei problemi sono 2:
le visite e i cammini
Ho scritto il seguente codice
| Spoiler: |
Codice:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct nodo{
char nome[32];
double valore;
int mark;
struct nodo* next;
}nodo;
typedef struct arco{
nodo* iniz;
nodo* final;
struct arco* next;
}arco;
typedef struct grafo{
nodo* nodi;
arco* archi;
}grafo;
grafo* G;
void init(){
G->archi=NULL;
G->nodi=NULL;
}
nodo* cercaNodo(nodo *nodi, char* nome);
nodo* aggiungiNodo(nodo* nodi, char* name, double val);
arco* inserisciArco(arco* archi, nodo*part, nodo*arriv);
void stampaNodi();
void stampaNodo(nodo* nodo);
void stampaArchi();
void stampaArco(arco* arco);
arco* eliminaArco(arco* archi, nodo*par, nodo*arr);
nodo* eliminaNodo(arco* archi, nodo* nodi, nodo* canc);
int contaNodi(nodo* nodi);
int contaArchi(arco* archi);
int** matrixAdiac(nodo* nodi, arco* archi);
int sonoAdiacenti(char* name1, char* name2, arco* archi);
int gradoNodo(char* nome, arco*archi, char tipo);
void unmark(nodo* nodi);
nodo* raggiungibili(nodo* nodi, arco* archi, char* nome);
nodo* duplicaNodo(nodo*n);
int verifica_ciclo(nodo* nodi, arco* archi);
nodo* visita_bfs(nodo* nodi, arco* archi, char *nome);
//------------------MAIN------------------
int main(){
G=(grafo*)malloc(sizeof(grafo));
init();
G->nodi=aggiungiNodo(G->nodi, "nino",3);
G->nodi=aggiungiNodo(G->nodi, "peppe",4);
G->nodi=aggiungiNodo(G->nodi, "cicco", 5);
G->nodi=aggiungiNodo(G->nodi, "salvo", 6);
G->nodi=aggiungiNodo(G->nodi, "sergio", 14);
G->nodi=aggiungiNodo(G->nodi, "fede", 8);
G->archi=inserisciArco(G->archi, cercaNodo(G->nodi, "nino"), cercaNodo(G->nodi, "peppe") );
G->archi=inserisciArco(G->archi, cercaNodo(G->nodi, "nino"), cercaNodo(G->nodi, "fede") );
G->archi=inserisciArco(G->archi, cercaNodo(G->nodi, "peppe"), cercaNodo(G->nodi, "salvo") );
G->archi=inserisciArco(G->archi, cercaNodo(G->nodi, "peppe"), cercaNodo(G->nodi, "cicco") );
G->archi=inserisciArco(G->archi, cercaNodo(G->nodi, "salvo"), cercaNodo(G->nodi, "sergio") );
G->archi=inserisciArco(G->archi, cercaNodo(G->nodi, "salvo"), cercaNodo(G->nodi, "cicco") );
G->archi=inserisciArco(G->archi, cercaNodo(G->nodi, "cicco"), cercaNodo(G->nodi, "peppe") );
G->archi=inserisciArco(G->archi, cercaNodo(G->nodi, "cicco"), cercaNodo(G->nodi, "sergio") );
G->archi=inserisciArco(G->archi, cercaNodo(G->nodi, "cicco"), cercaNodo(G->nodi, "nino") );
G->archi=inserisciArco(G->archi, cercaNodo(G->nodi, "sergio"), cercaNodo(G->nodi, "salvo") );
G->archi=inserisciArco(G->archi, cercaNodo(G->nodi, "fede"), cercaNodo(G->nodi, "peppe") );
G->archi=inserisciArco(G->archi, cercaNodo(G->nodi, "fede"), cercaNodo(G->nodi, "salvo") );
stampaNodi();
stampaArchi();
printf("Nodi: %d\tArchi: %d\n", contaNodi(G->nodi), contaArchi(G->archi));
G->archi=eliminaArco(G->archi, cercaNodo(G->nodi, "nino"),cercaNodo(G->nodi, "peppe") );
G->nodi=eliminaNodo(G->archi, G->nodi, cercaNodo(G->nodi, "nino"));
stampaNodi();
stampaArchi();
printf("Nodi: %d\tArchi: %d\n", contaNodi(G->nodi), contaArchi(G->archi));
matrixAdiac(G->nodi, G->archi);
nodo* h=raggiungibili(G->nodi, G->archi, "fede");
while(h!=NULL){
stampaNodo(h);
if(h->next!=NULL) printf(" ---> ");
h=h->next;
}
printf("\n");
printf("C'e' un ciclo? %d\n", verifica_ciclo(G->nodi, G->archi));
h=visita_bfs(G->nodi, G->archi, "fede");
while(h!=NULL){
stampaNodo(h);
if(h->next!=NULL) printf(" ---> ");
h=h->next;
}
printf("\n");
system("Pause");
return 0;
}
//-----------------------------------------------------------//
nodo* cercaNodo(nodo* nodi, char* nome){
while(nodi!=NULL){
if(strcmp(nodi->nome, nome)==0) return nodi;
nodi=nodi->next;
}
return NULL;
}
nodo* aggiungiNodo(nodo* nodi, char* name, double val){
nodo* nuovo;
nuovo=cercaNodo(nodi,name);
if(nuovo!=NULL) {
printf("Nodo già presente\n");
return nodi;
}
nuovo=(nodo*)malloc(sizeof(nodo));
strcpy(nuovo->nome,name);
nuovo->valore=val;
nuovo->next=nodi;
nuovo->mark=0;
return nuovo;
}
arco* inserisciArco(arco* archi, nodo*par, nodo*arr){
if(par==NULL || arr==NULL) {
return archi;
}
arco* nuovo=archi;
while(nuovo!=NULL){
if(nuovo->iniz==par && nuovo->final==arr)
return archi;
nuovo=nuovo->next;
}
nuovo=(arco*)malloc(sizeof(arco));
nuovo->iniz=par;
nuovo->final=arr;
nuovo->next=archi;
return nuovo;
}
void stampaNodo(nodo* nodo){
if(nodo!=NULL){
printf("(%s,%lf)", nodo->nome, nodo->valore);
}
}
void stampaNodi(){
nodo* n=G->nodi;
if(n!=NULL) printf("Nodi presenti:\n");
while(n!=NULL){
stampaNodo(n);
printf("\n");
n=n->next;
}
}
void stampaArco(arco* arco){
if(arco!=NULL){
printf("[ ");
stampaNodo(arco->iniz);
printf(",");
stampaNodo(arco->final);
printf(" ]");
}
}
void stampaArchi(){
arco* a=G->archi;
if(a!=NULL) printf("Archi presenti:\n");
while(a!=NULL){
stampaArco(a);
printf("\n");
a=a->next;
}
}
arco* eliminaArco(arco* archi, nodo*par, nodo*arr){
if(archi==NULL | par==NULL || arr==NULL) return archi;
arco* curr=archi;
arco* prec=archi;
while(curr!=NULL){
if(curr->iniz==par && curr->final==arr)
break;
curr=curr->next;
}
if(curr==NULL) {
return archi;
}
while(prec!=NULL){
if(prec->next==curr)
break;
prec=prec->next;
}
if(prec!=NULL) prec->next=curr->next;
else archi=archi->next;
free(curr);
return archi;
}
nodo* eliminaNodo(arco* archi, nodo* nodi, nodo* canc){
if(nodi==NULL || canc==NULL) return nodi;
nodo* curr=nodi;
nodo* prec=nodi;
while(curr!=NULL){
eliminaArco(archi, curr, canc);
eliminaArco(archi, canc, curr);
curr=curr->next;
}
while(prec!=NULL){
if(prec->next==canc) break;
prec=prec->next;
}
if(prec!=NULL) prec->next=canc->next;
else nodi=nodi->next;
free(canc);
return nodi;
}
int contaNodi(nodo* nodi){
if(nodi==NULL) return 0;
int n=0;
while(nodi!=NULL){
n++;
nodi=nodi->next;
}
return n;
}
int contaArchi(arco* archi){
if(archi==NULL) return 0;
int n=0;
while(archi!=NULL){
n++;
archi=archi->next;
}
return n;
}
int sonoAdiacenti(char* name1, char* name2, arco* archi){
while(archi!=NULL){
if( strcmp(archi->iniz->nome, name1)==0 && strcmp(archi->final->nome, name2)==0 ) return 1;
archi=archi->next;
}
return 0;
}
int** matrixAdiac(nodo* nodi, arco* archi){
int n=contaNodi(nodi);
char v[n][32];
int **m=(int**)calloc(n,sizeof(int*));
int i,j;
for(i=0; i<n; i++){
m[i]=(int*)calloc(n,sizeof(int));
}
nodo* curr=nodi;
for(i=0; i<n; i++){
strcpy(v[i], curr->nome);
curr=curr->next;
printf("\t%s", v[i]);
}
printf("\n");
for(i=0; i<n; i++){
printf("%s\t", v[i]);
for(j=0; j<n; j++){
m[i][j]=sonoAdiacenti(v[i],v[j],archi);
printf("%d\t", m[i][j]);
}
printf("\n", v[i]);
}
printf("\n");
return m;
}
int gradoNodo(char* nome, arco*archi, char tipo){
if(cercaNodo(G->nodi, nome)==NULL) return -1;
int grado_in=0;
int grado_out=0;
while(archi!=NULL){
if(strcmp(archi->iniz->nome, nome)==0) grado_out++;
if(strcmp(archi->final->nome, nome)==0) grado_in++;
archi=archi->next;
}
switch(tipo){
case 'i': return grado_in;
case '0': return grado_out;
default: return grado_in + grado_out;
}
}
void unmark(nodo* nodi){
while(nodi!=NULL){
nodi->mark=0;
nodi=nodi->next;
}
}
nodo* duplicaNodo(nodo*n){
if(n==NULL) return n;
nodo* ret=(nodo*)malloc(sizeof(nodo));
ret->mark=0;
ret->next=NULL;
strcpy(ret->nome, n->nome);
ret->valore=n->valore;
return ret;
}
nodo* raggiungibili(nodo* nodi, arco* archi, char* nome){
if(archi==NULL) return NULL;
unmark(nodi);
nodo* sorgente=cercaNodo(nodi, nome);
if(sorgente==NULL) return NULL;
sorgente->mark=1;
nodo* ret=duplicaNodo(sorgente);
nodo* ret_curr=ret;
nodo* curr;
nodo* tmp;
while(ret_curr!=NULL){
curr=nodi;
while(curr!=NULL){
if(sonoAdiacenti( ret_curr->nome,curr->nome,archi) && curr->mark==0){
curr->mark=1;
tmp=ret_curr->next;
ret_curr->next=duplicaNodo(curr);
ret_curr->next->next=tmp;
}
curr=curr->next;
}
ret_curr=ret_curr->next;
}
return ret;
}
int verifica_ciclo(nodo* nodi, arco* archi){
if(nodi==NULL || archi==NULL) return -1;
int num_nodi=contaNodi(nodi);
int num_archi=contaArchi(archi);
if(num_nodi<3 || num_archi<3) return -1;
int n1=0,n2=0,n3=0,tmp=0;
srand(time(NULL));
while(n1==0){
n1=rand()%num_nodi;
}
while(n2==0 || n2==n1){
n2=rand()%num_nodi;
}
while(n3==0 || n3==n2 || n3==n1){
n3=rand()%num_nodi;
}
nodo *primo, *secondo, *terzo;
while(nodi!=NULL){
if(tmp==n1) primo=nodi;
if(tmp==n2) secondo=nodi;
if(tmp==n3) terzo=nodi;
nodi=nodi->next;
tmp++;
}
printf("\nPrimo:");
stampaNodo(primo);
printf("\nSecondo:");
stampaNodo(secondo);
printf("\nTerzo:");
stampaNodo(terzo);
printf("\n");
if(sonoAdiacenti(primo->nome,secondo->nome, archi)&& sonoAdiacenti(secondo->nome,terzo->nome, archi)&& sonoAdiacenti(terzo->nome,primo->nome, archi))
return 1;
if(sonoAdiacenti(primo->nome,terzo->nome, archi)&& sonoAdiacenti(terzo->nome,secondo->nome, archi)&& sonoAdiacenti(secondo->nome,primo->nome, archi))
return 1;
return 0;
}
nodo* visita_bfs(nodo* nodi, arco* archi, char *nome){
if(nodi==NULL || archi==NULL) return NULL;
unmark(nodi);
nodo *sorgente=cercaNodo(nodi,nome);
if(sorgente==NULL) return NULL;
sorgente->mark=1;
nodo*first=duplicaNodo(sorgente);
nodo*last=first;
nodo*curr=first;
while(curr!=NULL){
nodo* listcurr=nodi;
while(listcurr!=NULL){
if(sonoAdiacenti(curr->nome,listcurr->nome, archi) && listcurr->mark==0){
listcurr->mark=1;
last->next=duplicaNodo(listcurr);
last=last->next;
}
listcurr=listcurr->next;
}
curr=curr->next;
}
return first;
}
|
In particolare sul mio codice (se avete ottimizzazioni da suggerirmi sono ben accette) sono insicuro sulla funzione "raggiungili" e sulla "visita_bfs" (in ampiezza)
Per quanto riguarda la visita, il libro dice che devo creare un albero a partire dal grafo, mentalmente sarei capace, ma a codice non so da dove partire, per cui ho "optato" per una struttura a nodi di tipo "coda"... mentre per raggiungibili non so se ho capito bene quello che dovrebbe fare e in particolare ai miei occhi il risultato della funzione, così come io l'ho implementata, sempre sulla semplificazione vista sulla visita, sembra una visita dfs (in profondità)
Mentre sui cammini sono molto in alto mare...tipicamente chiede questo il professore:
5)Calcolo di tutti i cammini di lunghezza k (k=2,3,...) del grafo
Desideroso di aiuto, tornerò a vedere se qualcuno sa come impostare il problema e risolvere i miei dubbi. Saluti
|
09-09-2013, 16:57
