/*
ESERCIZIO 51 [LIV. 1]
Scrivere una function C per la costruzione di un grafo non orientato mediante matrice di
adiacenze: in input per ogni nodo sono specificati quelli adiacenti. Scegliendo in input un
nodo, scrivere una function C che restituisca il suo grado.
*/

#include <stdio.h>
#include <stdlib.h>

#define size 100

void costruisci_grafo(int [][size],int);
void stampa_matrice_adiacenze(int [][size], int);
int grado_nodo(int [][size], int, int);

void main ()
{
    int matrice_adiacenze[size][size];
    int i, j, n, risp, nodo;

    printf("Inserire numero vertici del grafo: "); scanf("%d",&n);

    /*stampa vertici*/
    printf("\nVertici: ");
    for (i=0; i<n; i++)
        printf("%d ",i);

    printf("\n\n");

    /*inizializzazione matrice*/
    for (i=0; i<n; i++)
        for (j=0; j<n; j++)
            matrice_adiacenze[i][j] = 0;

    /*chiamata alle function*/
    costruisci_grafo(matrice_adiacenze, n);
    stampa_matrice_adiacenze(matrice_adiacenze, n);

    risp=0;
    while (risp==0)
    {
        printf("\nInserire nodo di cui si vuole conoscere il grado (-1 per terminare): ");
        scanf("%d",&nodo);

        if ((nodo!=-1) && (nodo<n)) //se non si e' inserito il tasto di uscita e il nodo esiste
            /*richiama la function che calcola il grado di un nodo dato in input*/
            printf("Il grado del nodo %d e': %d",nodo,grado_nodo(matrice_adiacenze,n,nodo));
        else /*altrimenti*/
            if (nodo == -1)
                risp=1; //se si e' inserito il tasto di uscita aggiorna la variabile di uscita
            else
                printf("\n\nNodo inserito non esistente nel grafo!\n\n");
    }
}

/*Function che costruisce il grafo */
void costruisci_grafo(int matrice_adiacenze[size][size], int num_nodi)
{
    int i, j, adiacenze=-2;

    for (i=0; i<num_nodi; i++) /*per i che va da 0 a quanti sono i nodi*/
    {
        printf("\nInserire i nodi adiacenti al vertice %d",i);
        printf("(premere -1 per terminare l'inserimento):\n");

        //il numero di nodi adiacenti e' al massimo uguale al numero di nodi presenti nel grafo
        for (j=0; j<num_nodi; j++)
        {
            while (adiacenze == -2) /*mentre adiacenze = -2*/
            {
                scanf("%d",&adiacenze); /*leggi il nodo adiacente*/

                /*se il nodo adiacente inserito non esiste*/
				if (adiacenze>num_nodi-1 || adiacenze < -1)
                {
                    printf("Nodo inesistente!");
                    printf("\nReinserire: ");
                    adiacenze=-2;
                    /*reimposta adiacenze al valore -2 per soddisfare la condizione del while*/
                }
            }

            /*se si e' inserito -1 termina l'inserimento dei nodi adiacenti per il nodo i-esimo*/
            if (adiacenze == -1)
            {
                adiacenze=-2; /*reimposta il valore di adiacenze*/
                break;
            }
            else
            {
				/*dovrebbero essere modificate la riga e la colonna perche stiamo trattando di
				un grafo non orientato e quindi la matrice che andremo a costruire e' una
				matrice simmetrica cioe il triangolo superiore e' simmetrico rispetto al
				triangolo inferiore. Sapendo che essa e' simmetrica, si puo dimezzarne
				l'occupazione di memoria rappresentando solo il triangolo super. o infer. */

				/*inserisce nella matrice (alla riga i-sima (corrispondente al nodo di cui si
                stanno inserendo le adiacenze), colonna uguale al nodo con cui e' adiacente)
                un 1*/
				matrice_adiacenze[i][adiacenze] = 1;
            }
            adiacenze=-2;/*reimposta il valore di adiacenze*/
        }
        printf("\n");
    }
}

/*Function che stampa la matrice di adiacenze */
void stampa_matrice_adiacenze(int matrice_adiacenze[size][size], int num_nodi)
{
	int i, j;

    printf("\n\n");
    printf("Matrice di adiacenze del grafo non orientato creato:\n\n");

    printf("Vertici:   ");
        for(i=0; i<num_nodi; i++)
            printf("%d  ",i);
        for(i=0; i<num_nodi; i++)
        {
            printf("\n\t%d| ",i);
                for(j=0;j<num_nodi;j++)
                    printf("%d  ",matrice_adiacenze[i][j]);
        }
    printf("\n\n");
}

/*Function che sceglie in input un nodo e restituisce il suo grado (numero di archi) */
int grado_nodo(int matrice_adiacenze[size][size], int num_nodi, int nodo)
{
    int i=0, grado=0;

    /*il numero di confronti e' pari al numero dei nodi (la matrice e' nxn)*/
    while (i<num_nodi) /*mentre la riga che si sta scorrendo non e' terminata*/
    {
        /*se la componente nodo i-sima della matrice presenta un 1 (la riga corrisponde al
        nodo di cui vogliamo l'informazione) */

        if (matrice_adiacenze[nodo][i]==1)
            grado++; /*incrementa il contatore dei gradi*/

        i++; /*incrementa il contatore che scorre la riga*/
    }
    return grado; /*ritorna il grado del nodo*/
}