Ciao a tutti
Ho fatto un programma per un progetto di algoritmi in C di nome "max cliques".
Vorrei solamente un chiarimento per cui funziona solamente sotto alcuni SO, usando io solamente librerie standard...
Windows XP: Compilo in devc++, e funziona sempre. Tira fuori il risultato migliore per tutti i grafici che gli do in ingresso
Windows 7 64b: Compilo in Visual studio 10 express c++. Dentro il compilatore, ci sono dei problemi con l'heap, ma continuo a mettere "continua" invece di "interrompi", e mi da il risultato corretto a console. Se invece lo tiro fuori e lancio l'eseguibile da windows, non funziona
Ubuntu 10: Compilo con gcc, nessun errore. Segmentation fault al momento dell'esecuzione
L'unica cosa che devo fare adesso è farlo partire con ubuntu. idee?
#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>
#include <string.h>
int *cqmax=NULL;
int maxclique=0;
struct intnew
{
int* vettore;
int grandezza;
} ;
//BuildAdiacenza crea la matrice di adiacenza da un vettore dinamico di numeri e dalla sua grandezza
int** BuildAdiacenza(int *lista,int size,int numnodi)
{
int i=0,**matriceadiacenza=NULL;
matriceadiacenza=(int**)malloc(numnodi*sizeof(int));
//Crea la matrice di adiacenza e inizializza a 0 tutti gli elementi
for(i=0;i<numnodi;i++)
{
matriceadiacenza[i]=(int*)calloc(size+1,sizeof(int));
}
//Inserisci gli elementi 1 nella matrice di adiacenza
for(i=0;i<size-1;i++)
{
matriceadiacenza[lista[i]-1][lista[i+1]-1]=1;
matriceadiacenza[lista[i+1]-1][lista[i]-1]=1;
i++;
}
return matriceadiacenza;
};
//Rimuove un elemento da un vettore di int P e restituisce un nuovo P senza quell'elemento
struct intnew Remove(struct intnew P,int a)
{
int i=0,u=0;
struct intnew RET2;
RET2.grandezza=0;
RET2.vettore=NULL;
if(P.grandezza==0)
return RET2;
for(i=0;P.vettore!=NULL && i<P.grandezza;i++)
{
if(P.vettore[i]==a && i+1<=P.grandezza)
{
for(u=i+1;u<P.grandezza;u++)
P.vettore[u-1]=P.vettore[u];
P.grandezza--;
break;
}
//Si suppone che non ci siano elementi uguali
}
//Se è stato trovato l'elemento all'interno del vettore puntato, allora rialloca e stringi il vettore
if(u!=0)
{
if(u-1==0){
P.vettore=NULL;
P.grandezza=0;
}else
{
if(P.vettore!=NULL)
P.vettore=(int*)realloc(P.vettore,sizeof(int)*(u-1));
else
P.vettore=(int*)malloc(sizeof(int)*(u-1));
P.grandezza=u-1;
}
}
return P;
}
//Inserisce l'elemento a nel vettore puntato P
struct intnew Add(struct intnew P,int a)
{
int i=0,u=0;
struct intnew K;
K.vettore=NULL;
K.grandezza=0;
if(P.grandezza==0)
{
K.vettore=(int*)malloc(sizeof(int));
K.vettore[0]=a;
K.grandezza=1;
}
else
{
K.vettore=(int*)malloc(sizeof(int)*P.grandezza);
for(i=0;i<P.grandezza;i++){
K.vettore[i]=P.vettore[i];
K.grandezza++;
}
//Parti dall'ultimo elemento ed inserisci quando a è maggiore di quello preso in considerazione
for(i=P.grandezza-1;i>=0;i--)
{
if(a>K.vettore[i])
{
//Se è stato trovato l'elemento all'interno del vettore puntato, allora rialloca e stringi il vettore
P.grandezza++;
if(K.vettore!=NULL)
K.vettore=(int*)realloc(K.vettore,P.grandezza*sizeof(int));
else
K.vettore=(int*)malloc(sizeof(int)*P.grandezza);
K.grandezza=P.grandezza;
for(u=P.grandezza-1;u>i;u--)
K.vettore[u]=K.vettore[u-1];
K.vettore[i+1]=a;
break;
}
//Altrimenti inserisci come primo
else
if(i==0)
{
if(P.vettore!=NULL)
P.vettore=(int*)realloc(K.vettore,sizeof(int)*(++P.grandezza));
else
P.vettore=(int*)malloc(sizeof(int)*(++P.grandezza));
for(u=P.grandezza-1;u>i;u--)
K.vettore[u]=K.vettore[u-1];
K.vettore[u]=a;
}
}
}
return K;
}
//Restituisce un vettore RET con elementi pari a quelli uguali tra i due vettori P ed U
struct intnew Interseca(struct intnew P,struct intnew U)
{
struct intnew RET;
struct intnew RET2;
int i=0,u=0,h=1;
RET.grandezza=0;
RET.vettore=NULL;
RET2.grandezza=0;
RET2.vettore=NULL;
if(P.vettore==NULL || U.vettore==NULL)
{
return RET2;
}
RET.vettore=NULL;
RET.grandezza=0;
for(i=0;i<U.grandezza;i++)
for(u=0;u<P.grandezza;u++)
if(U.vettore[i]==P.vettore[u])
{
if(RET.vettore!=NULL)
RET.vettore=(int*)realloc(RET.vettore,sizeof(int)*h);
else
RET.vettore=(int*)malloc(sizeof(int)+h);
RET.grandezza++;
RET.vettore[h-1]=U.vettore[i];
h++;
}
h--;
if(h>0)
return RET;
else
return RET2;
}
//Restituisce un vettore contenente i vicini di un vertice v
struct intnew Neighborhood(int v,int** matriceadiacenza,int numnodi)
{
struct intnew RET;
int i=0,u=0;
RET.vettore=NULL;
RET.grandezza=0;
for(i=0;i<numnodi-1;i++){
if(matriceadiacenza[v-1][i]==1){
u++;
RET.grandezza++;
if(RET.vettore!=NULL)
RET.vettore=(int*)realloc(RET.vettore,sizeof(int)*u);
else
RET.vettore=(int*)malloc(sizeof(int)*u);
RET.vettore[u-1]=i+1;
}
}
return RET;
}
//Setta il valore maxclique e cqmax i quali sono rispettivamente la lunghezza e la clique massima stessa
void BronKerbosch1(struct intnew R,struct intnew P,struct intnew X,int** matriceadiacenza,int numnodi)
{
int v=0,i=0;
struct intnew nbh,interz1,interz2,added;
nbh.vettore=(int*)malloc(sizeof(int));
interz1.vettore=(int*)malloc(sizeof(int));
interz2.vettore=(int*)malloc(sizeof(int));
added.vettore=(int*)malloc(sizeof(int));
nbh.grandezza=0;
interz1.grandezza=0;
interz2.grandezza=0;
added.grandezza=0;
if (P.vettore==NULL && X.vettore==NULL)
{
if(maxclique<R.grandezza){
if(maxclique==0)
{
cqmax=(int*)malloc(sizeof(int));
}
if(cqmax!=NULL)
cqmax=(int*)realloc(cqmax,sizeof(int)*R.grandezza);
else
cqmax=(int*)malloc(sizeof(int)*R.grandezza);
for(i=0;i<R.grandezza;i++){
cqmax[i]=R.vettore[i];
}
maxclique=R.grandezza;
}
}
for (i=0;i<P.grandezza;i++)
{
v=P.vettore[i];
added=Add(R,v); //In added mettere il cambio di grandezza anche
nbh=Neighborhood(v,matriceadiacenza,numnodi);//in neighborhood cambiare il tipo di uscita
interz1=Interseca(P,nbh); //in interseca cambiare i tipi di ingresso
interz2=Interseca(X,nbh);
BronKerbosch1(added,interz1,interz2,matriceadiacenza,numnodi);
P = Remove(P,v);
X = Add(X,v);
}
}
int main(int argc, char *argv[])
{
struct intnew listanodi,lista;
int numero=0,scan = 0,**matriceadiacenza,i=0,size=0,u=0,numnodi=0,sizestringa=0;
struct intnew Rstart,Xstart;
FILE *f;
Rstart.grandezza=0;
Rstart.vettore=NULL;
Xstart.grandezza=0;
Xstart.vettore=NULL;
listanodi.grandezza=0;
lista.grandezza=0;
lista.vettore=NULL;
listanodi.vettore=NULL;
if(argc==2)
{
sizestringa=strlen(argv[1]);
f = fopen(argv[1], "r");
}
else
{
f = fopen("Test.txt", "r");
}
lista.vettore=(int*)malloc(sizeof(int));
lista.grandezza=1;
//Il primo elemento del file è il numero totale di nodi della matrice di adiacenza
scan=fscanf(f, "%d\t", &numnodi);
//Carica fino a che non finisce il file
while(scan!=EOF)
{
scan=fscanf(f, "%d", &numero);
size++;
//Controlla di non essere alla fine del file e che il vertice che si sta prendendo in considerazione non sia
//con un numero identificativo maggiore del numero dei nodi
if (scan!=EOF)
{
if(lista.vettore!=NULL)
lista.vettore=(int*)realloc(lista.vettore,size*sizeof(int));
else
lista.vettore=(int*)malloc(sizeof(int)*size);
lista.vettore[size-1]=numero;
lista.grandezza=size-1;
}
}
//Controlla che il numero di vertici all'interno del file sia pari ed elimina l'ultimo in caso non sia così
if(size%2!=0){
if(lista.vettore!=NULL)
lista.vettore=(int*)realloc(lista.vettore,sizeof(int)*(size-1));
else
lista.vettore=(int*)malloc(sizeof(int)*(size-1));
lista.grandezza=size-1;
}
fclose(f);
listanodi.vettore=(int*)malloc(sizeof(int)*numnodi);
listanodi.grandezza=numnodi;
for(u=1;u<=numnodi;u++)
listanodi.vettore[u-1]=u;
//La matrice poteva essere inserita come variabile globale, ma la funzione potrebbe servire in futuro
matriceadiacenza= BuildAdiacenza(lista.vettore,size,numnodi);
BronKerbosch1(Rstart,listanodi,Xstart,matriceadiacenza,numnodi);
//Visualizza la matrice di adiacenza
printf("\n");
if(maxclique>0)
for(i=0;i<maxclique;i++)
printf(" %d ",cqmax[i]);
else
printf("Non esistono Clique\n");
printf("\n");
system("pause");
return 0;
}