C++ grafi Progetto help

[kalo]

Salve a tutti
sono nuovo...vi scrive perchè mi servirebbe una mano!!!
dovrei presentare un progetto per un esame
questo è il testo:
Dato un grafo G=(V,L) non orientato, chiamiamo triangolo un insieme di tre nodi distinti
di G che formano una clique({a,b,c} tale che a!=b b!=c a!=c e i lati ab bc e ac appartengono ad L
a) sia G = (V,L) un grafo non orientato e completo ovvero ab E L , per ogni coppia di nodi distinti. se n è il numero di nodi di G
qual'è il numero dei suoi triangoli?
b) progettare un algoritmo che ricevendo in input un grafo non orientato G calcoli il numero
dei suoi triangoli. Si assuma G rappresentato mediante matrice di adiacenza

per chi non è al corrente una matrice di adiacenza è una matrice simmetrica dove la diagonale è posta a 0.

mi manca la parte b e non so come cavarne piede. c'è qualcuno per caso che mi può dare una mano?

quel che ho fatto io è questo ma non creo una matrice tramite l'inserimento di un grafo. bensi calcolo il numero dei triangoli sapendo il numero dei vertici del grafo
programma con c++

main()
{
int n_triang=0,i=1,c=0, j, V,Grafo[MAX][MAX],sum=0;
int n;
        
        printf("\nInserire il numero dei vertici del grafo :\n");
        scanf("%d",&V);
      
       if (V==0 || V==1 || V==2)
         printf("il grafo non ha triangoli");
         else
             { 
                    creagrafo(Grafo,V);
                    stampagrafo (Grafo,V);
                    
                 for (j=3; j<=V; j++)
                 {
                      n_triang= n_triang+i;
                      n+=n_triang;
                     
                 i++;
             
                 }
                    printf("\n il numero dei triangoli in un grafo di %d vertici e' %d ", V, n);
             }
         infotriang (Grafo,V); 
         
fflush(stdin);
getchar();
}

void creagrafo(int mat[MAX][MAX], int nodo)
{
     int i,j;
    
     for (i=0;i<nodo;i++)
         for (j=0;j<nodo;j++)
           mat[i][j] = 1;
           
for(i=0;i<nodo;i++)
   mat[i][i] = 0;

}
     
void stampagrafo (int mat[MAX][MAX],int nodo)
{
     int i,j,k;
     char a='A';
     char b='A';
     printf("  ");
for (k=0;k<nodo;k++)
    printf(" %c", b++);
     
 for(i=0;i<nodo;i++){
printf("\n %c ",a++);
for(j=0;j<nodo;j++)
printf("%d ",mat[i][j]);
}
}

[kalo]

non c'è nessuno che mi sappia dire qualcosa?

[YuYevon]

Direi che c'è un po' di confusione... l'esercizio richiede in input un grafo rappresentato con una matrice di adiacenza, ma la matrice che costruisci tu ha 1 ovunque e 0 sulla diagonale principale. Su quest'ultimo punto siamo d'accordo ("nessun grafo ha un arco che lo collega a sé stesso"), ma perché mai ci sono 1 in tutte le altre posizioni? E' come se per ogni coppia di vertici a-b esistesse un arco che li congiunga... in poche parole, i vertici sono tutti connessi tra loro e il grafo è completamente connesso. Forse non sai come costruire una matrice di adiacenza per un grafo?

Inoltre, cos'è quella procedura infotriang? Che fa?

[kalo]

io ho semplicemente realizzato il punto a cioè calcolato i triangoli di un grafo non orientato e connesso (dove tutti i nodi sono collegati) ma non so come creare il grafo del punto b e rappresentarlo come matrice.

come calcolare i triangoli sulla matrice lo so...sarebbe quell infotriang che non ho pubblicato e che funziona perchè l'ho provato sulla matrice di adiacenza.

praticamente mi serve una mano per :
progettare un algoritmo che ricevendo in input un grafo non orientato G

[kalo]

void infotriang (int mat[MAX][MAX] , int nodo)
{
     /*nel caso il grafo non fosse completo*/
     
int i,j,k;
int triang=0;
int n;

for(i=0 ; i<=nodo-2 ;i++ )
       {
        for(j=i+1 ;j<=nodo-1;j++)
            {  
            if(mat[i][j]==1)
               {
                for(k=j+1 ; k<=nodo ;k++)
                     { 
                      if ( mat[i][k]==1 && mat[j][k]==1)
                          triang = triang +1;
                      }
                }
            }
            }
            printf("\n -> numero triangoli %d ",triang);      

}

[YuYevon]

Il fatto che l'algoritmo debba ricevere un input un grafo non orientato significa appunto che deve avere in input la matrice di adiacenza che lo rappresenta (esistono anche altre rappresentazioni come la lista di adiacenza, ma il testo richiede esplicitamente una matrice...). Quello che ancora non ho capito è: sai costruire o no una matrice di adiacenza? Me lo chiedo perché hai detto che il primo punto lo hai già fatto

come calcolare i triangoli sulla matrice lo so...sarebbe quell infotriang che non ho pubblicato e che funziona perchè l'ho provato sulla matrice di adiacenza.

quindi significa che sai come crearla questa matrice... e se è così, non vedo il problema quale sia nel "dare in input all'algoritmo una matrice di adiacenza che rappresenti il grafo".

[kalo]

non so come creare la matrice

perchè io ho creato una lista di adiacenza di un grafo completo non orientato . so che sono tutti uno tranne la diagonale
void creagrafo(int mat[MAX][MAX], int nodo)
{
int i,j;

for (i=0;i<nodo;i++)
for (j=0;j<nodo;j++)
mat[i][j] = 1;

for(i=0;i<nodo;i++)
mat[i][i] = 0;

}
ed è questo..

dovrei per ogni nodo chiedere se è connesso e mettere un uno se lo è?
0
10
010
1110
00110
101010
o posso farlo anche in random

cioè quello che mi manca è solo costruire una matrice dove posso mettere in random uno o zero?
o devo fare qualcos'altro?

[kalo]

sarà che è un progetto per dare un esame e mi sembrava troppo semplice come soluzione?? :P

[YuYevon]

perchè io ho creato una lista di adiacenza di un grafo completo non orientato . so che sono tutti uno tranne la diagonale

Ok ora torna il discorso, in pratica tu hai realizzato una matrice di adiacenza per un grafo completo, cioè tale che ogni vertice sia connesso con tutti gli altri... e ora si spiega il codice che hai postato all'inizio :)

Sicuramente però dovresti generalizzare la creazione della matrice, perché l'esercizio chiede in input "un grafo non orientato", non necessariamente completo.

Puoi fare in due modi: o progetti il programma in maniera tale che legga la matrice da un file, oppure crei un programma interattivo che chieda all'utente, nell'ordine:

1) il numero N dei vertici del grafo, con N >= 1 (con allocazione quindi di una matrice NxN);
2) per ciascun vertice, il numero M dei vertici ad esso connessi, con 0 <= M < N;
3) il numero (o la lettera identificativa) di questi M vertici.

Ogni riga corrisponde ad un vertice, quindi se dico che il vertice 0 è connesso ai vertici 3 e 4 (supponendo che in totale siano 5) la prima riga sarà

0 0 0 1 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

e così via per tutti i vertici. Poni attenzione ad un fatto: il grafo non è orientato. Questo significa che gli archi ab e ba, con b!=a, sono equivalenti. In poche parole, se per il vertice 0 dici che è connesso al vertice 3, allora di sicuro anche 3 sarà connesso a 0... stessa cosa per il 4, quindi dopo l'immissione della prima riga la matrice dovrebbe essere in realtà così

0 0 0 1 1
0 0 0 0 0
0 0 0 0 0
1 0 0 0 0
1 0 0 0 0

cioè appunto i vertici 3 e 4 devono risultare connessi a 0. Alla fine ti ritroverai con una matrice simmetrica rispetto alla diagonale principale, come del resto già quest'ultima risulta essere. La diagonale poi ha tutti 0 perché ovviamente nessun vertice ha un arco che lo collega a sé stesso.

EDIT: volendo puoi anche farlo in maniera random, ma devi stare attento alla questione della simmetria... per intenderci, una matrice come questa

0 1 1 0 0
0 0 0 1 1
1 0 0 1 0
0 0 1 0 0
1 1 1 1 0

tutto può rappresentare tranne che un grafo non orientato :)

[kalo]

e invece guarda qua
basta mandare in random termini 1 e 0 e poi copiare la parte [i][j] con [j][i] per farla simmetrica e tutto torna grafo non orientato

void creagrafo2(int mat[MAX][MAX], int nodo)
{
int i,j;

for (i=0;i<nodo;i++)
for (j=0;j<nodo;j++)
mat[i][j] =rand()%2;

for(i=0;i<nodo;i++)
for (j=0;j<nodo;j++)
mat[j][i] = mat[i][j];

for(i=0;i<nodo;i++)
mat[i][i] = 0;

}

yuuuuuuuuu