#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_VERTICI 15

typedef struct Nodo* nodo_pointer;

typedef struct Nodo{
     int valore;
     nodo_pointer link;
}Nodo;

nodo_pointer grafo[MAX_VERTICI];
nodo_pointer testa_coda=NULL;
nodo_pointer fine_coda=NULL;
_Bool marcato[MAX_VERTICI];

nodo_pointer inserisci(nodo_pointer, int, int);
void visualizza_lista_adiacenza(nodo_pointer);
void visualizzaGrafo(int);
void addC(int);
int eliminaC();
_Bool CodaEmpty();
void visita_in_ampiezza(int);
void ampiezza(int);
void visita_in_Profondita(int);
void cancella_lato(int, int);
void componenti_connesse(int);

int main()
{
    int n, i;
    int scelta, opzione;
    int vertice_di_partenza, v1, v2;

    printf("\n\t*** Implementazione struttura dati grafo ***\n\n\n");
    printf("\nQuanti nodi vuoi inserire?");
    scanf("%d", &n);

    for(i=0; i<n; i++){

        printf("\nNodo %d. Ha nodi adiacenti?(1 si, 0 no)", i);
        scanf("%d", &scelta);
        if(scelta==1)
          grafo[i]=inserisci(grafo[i], i, n);
    }
    printf("\nGrafo creato!!\n\n");
    do{
        printf("\nScegli un'opzione:\n\n");
        printf("\t1) Visualizza grafo e liste di adiacenza\n");
        printf("\t2) Visita in ampiezza\n");
        printf("\t3) Visita in profondita'\n");
        printf("\t4) Cancella lato\n");
        printf("\t5) Componenti connesse\n");
        printf("\t6) Esci\n\n");
        scanf("%d", &opzione);


        switch(opzione){
                case 1:
                    visualizzaGrafo(n);
                    break;
                case 2:
                    printf("\nInserisci il vertice dal quale vuoi iniziare la visita:  ");
                    scanf("%d", &vertice_di_partenza);
                    printf("\nSequenza vertici raggiungibili da %d in ampiezza:\n", vertice_di_partenza);
                    visita_in_ampiezza(vertice_di_partenza);
                    break;
                case 3:
                    for(i=0;i<MAX_VERTICI;i++)
                        marcato[i]=false;
                    printf("\nInserisci il vertice dal quale vuoi iniziare la visita:  ");
                    scanf("%d", &vertice_di_partenza);
                    printf("\nSequenza vertici raggiungibili da %d in profondita':\n", vertice_di_partenza);
                    visita_in_Profondita(vertice_di_partenza);
                    break;
                case 4:
                    printf("\nInserisci i due vertici del lato da eliminare:  ");
                    scanf("%d %d", &v1,&v2);
                    cancella_lato(v1, v2);
                    printf("\nLato eliminato! Vuoi stampare il grafo per verifica?(1 si, 0 no)");
                    scanf("%d", &scelta);
                    if(scelta==1)
                        visualizzaGrafo(n);
                    break;
                case 5:
                    componenti_connesse(n);
                    break;
                case 6:
                    return 0;



        }

    }while(opzione!=6);


    return 0;
}

nodo_pointer inserisci(nodo_pointer lista_adiacenza, int i, int nVertici){

     int scelta, numero;

     nodo_pointer temp= NULL;
     nodo_pointer fine_lista=NULL;


     do{
         do{
            printf("\nInserire nodo adiacente:");
            scanf("%d", &numero);
            if(numero==i)
                printf("Il nodo non puo' essere adiacente a se' stesso.\n");
            if(numero<0 || numero>nVertici-1)
                printf("Il nodo adiacente deve essere compreso tra 0 e %d", nVertici-1);
         }while(numero==i || numero<0 || numero>nVertici-1);


         temp=(nodo_pointer)malloc(sizeof(Nodo));
         temp->valore=numero;
         temp->link=NULL;

         if(lista_adiacenza==NULL){
             lista_adiacenza=temp;
             fine_lista=temp;
         }
         else{
             fine_lista->link=temp;
             fine_lista=fine_lista->link;
         }

         printf("\nVuoi inserire un'altro nodo adiacente?(1 si, 0 no)");
         scanf("%d", &scelta);

     }while(scelta!=0);

     return lista_adiacenza;

}

void visualizza_lista_adiacenza(nodo_pointer lista){
    if(lista!=NULL){
        printf("%d\t", lista->valore);
        visualizza_lista_adiacenza(lista->link);
    }
}

void visualizzaGrafo(int n){
    int i;
    printf("\n\n\tVisualizzazione grafo e liste di adiacenza:\n\n");
    for(i=0;i<n;i++){
        printf("\nNodo %d.", i);
        printf("\nRelativi nodi adiacenti:\t");
        visualizza_lista_adiacenza(grafo[i]);
    }
}


//Esercizio 10_2

void addC(int item){

    nodo_pointer tmp=(nodo_pointer)malloc(sizeof(Nodo));

    tmp->valore=item;
    tmp->link=NULL;

    if(CodaEmpty()){
        testa_coda=tmp;
        fine_coda=tmp;
    }
    else{
        fine_coda->link=tmp;
        fine_coda=fine_coda->link;
    }
}

int eliminaC(){

    if(CodaEmpty())
        return -1;
    nodo_pointer tmp=testa_coda;
    testa_coda=testa_coda->link;

    return tmp->valore;

}

_Bool CodaEmpty(){

    if(testa_coda==NULL)
        return true;
    else
        return false;
}

void visita_in_ampiezza(int vIniziale){

     int i=0;

     for(i=0;i<MAX_VERTICI;i++)
        marcato[i]=false;

     ampiezza(vIniziale);
}

void ampiezza(int vertice){

    nodo_pointer w;
    int el_delete;
    marcato[vertice]=true;
    printf("%d \t", vertice);
    addC(vertice);

    while(CodaEmpty()==false){
        el_delete=eliminaC();

        for(w=grafo[el_delete]; w!=NULL; w=w->link){

            if(marcato[w->valore]==false){
                printf("%d\t", w->valore);
                marcato[w->valore]=true;
                addC(w->valore);
            }
        }
     }
}

void visita_in_Profondita(int vIniziale){

    nodo_pointer nodo=NULL;
    nodo=(nodo_pointer)malloc(sizeof(Nodo));
    nodo->valore=vIniziale;

    printf("%d\t", nodo->valore);
    marcato[nodo->valore]=true;

    for(nodo=grafo[nodo->valore];nodo!=NULL;nodo=nodo->link){
        if(marcato[nodo->valore]==false)
            visita_in_Profondita(nodo->valore);
    }
}

void cancella_lato(int vertice1,int vertice2){

    nodo_pointer tmp=NULL;
    nodo_pointer prec=NULL;

    for(tmp=grafo[vertice1];tmp!=NULL;tmp=tmp->link){

        if(tmp->valore==vertice2){

            if(prec==NULL){
                grafo[vertice1]=tmp->link;
            }
            else
            {
                prec->link=tmp->link;
                free(tmp);
                break;
            }

        }
        else
            prec=tmp;
    }

    prec = NULL;

    for(tmp=grafo[vertice2];tmp!=NULL;tmp=tmp->link){

        if(tmp->valore==vertice1){

            if(prec==NULL){
                grafo[vertice2]=tmp->link;
            }
            else
            {
                prec->link=tmp->link;
                free(tmp);
                break;
            }

        }
        else
            prec=tmp;
    }
}

void componenti_connesse(int nVertici)
{
    int i,cont=1;

    for(i=0;i<nVertici;i++)
        marcato[i]=false;

    for(i=0;i<nVertici;i++)
    {
        if(marcato[i]==false)
        {
            printf("\nComponente connessa %d.\n",cont);
            visita_in_Profondita(i);
            cont++;
        }
    }
}