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




// Definition des structures


// On définit la structure d'un graphe grâce à la matrice d'adjacence 

typedef struct {

    int nb_sommets;  // On donne le  nb de sommets du graphe 

    int** matrice_adjacence; // On cree un tableau à 2 dimensions pour la matrice d'adjacence 

} GrapheMatrice;




// Déclaration de fonction



GrapheMatrice cree_graphe_vide_matrice(int n);
void supprime_graphe_matrice(GrapheMatrice* graphe);
void ajoute_arete_matrice(GrapheMatrice* graphe, int sommet1, int sommet2);
int nb_sommets_matrice(GrapheMatrice* graphe);
int sont_voisins_matrice(GrapheMatrice* graphe, int sommet1, int sommet2);
int nb_aretes_matrice(GrapheMatrice* graphe);



//Fonctions






// Fonction qui crée un graphe vide avec n sommets pour une matrice d'adjacence



GrapheMatrice cree_graphe_vide_matrice(int n) 

{
    GrapheMatrice graphe; // Crée une variable de type GrapheMatrice
    
    graphe.nb_sommets = n; // Initialise le nombre de sommets dans le graphe

    // Allocation de la matrice d'adjacence
    
    graphe.matrice_adjacence = (int**)malloc(n * sizeof(int*)); // Allocation de la première dimension de la matrice d'adjacence
    
    for (int i = 0; i < n; i++) 
    {
        graphe.matrice_adjacence[i] = (int*)malloc(n * sizeof(int)); // Allocation de la deuxième dimension de la matrice pour chaque sommet
        
        for (int j = 0; j < n; j++) 
        {
            graphe.matrice_adjacence[i][j] = 0; // Initialisation de chaque élément de la matrice à 0 pour indiquer l'absence d'arêtes
        }
    }

    return graphe; // Retourne le graphe initialisé
}




// Fonction qui supprime un graphe et libère l'espace mémoire occupé par le graphe



void supprime_graphe_matrice(GrapheMatrice* graphe) 

{
    for (int i = 0; i < graphe->nb_sommets; i++) // Parcourt chaque ligne de la matrice
    
    { 
        free(graphe->matrice_adjacence[i]); // Libère la mémoire allouée pour chaque ligne de la matrice d'adjacence
    }
    
    free(graphe->matrice_adjacence); // Libère la mémoire allouée pour la stucture du graphe total
}


// Ajoute une arête entre deux sommets

// La complexité de cette fonction est 2


void ajoute_arete_matrice(GrapheMatrice* graphe, int sommet1, int sommet2)


{
   graphe->matrice_adjacence[sommet1][sommet2] = 1; // Marque l'existence d'une arête de sommet1 à sommet2

   graphe->matrice_adjacence[sommet2][sommet1] = 1; // Marque l'existence d'une arête de sommet2 à sommet1 pour un graphe non orienté
    
}



// Retourne le nombre de sommets du graphe

int nb_sommets_matrice(GrapheMatrice* graphe)
{
    return graphe->nb_sommets; // Retourne le champ nb_sommets du graphe
}

// Teste si deux sommets sont voisins

int sont_voisins_matrice(GrapheMatrice* graphe, int sommet1, int sommet2) 

{
    return graphe->matrice_adjacence[sommet1][sommet2] == 1; // Retourne 1 si les sommets sont voisins (connectés), sinon 0
}

// Calcule le nombre d'arêtes du graphe
int nb_aretes_matrice(GrapheMatrice* graphe) {
    int count = 0; // Initialise le compteur d'arêtes
    for (int i = 0; i < graphe->nb_sommets; i++) { // Parcourt les lignes de la matrice
        for (int j = i + 1; j < graphe->nb_sommets; j++) { // Parcourt les colonnes pour éviter de compter deux fois la même arête
            if (graphe->matrice_adjacence[i][j] == 1) { // Si une arête existe entre i et j
                count++; // Incrémente le compteur d'arêtes
            }
        }
    }
    return count; // Retourne le nombre total d'arêtes
}







int main (void)

{

  
    GrapheMatrice graphe;
    int choix, n, sommet1, sommet2;
    bool grapheCree = false;

    while (true) {
        printf("\nMenu:\n");
        printf("1. Créer un graphe vide\n");
        printf("2. Ajouter une arête\n");
        printf("3. Nombre de sommets\n");
        printf("4. Sont-ils voisins?\n");
        printf("5. Nombre d'arêtes\n");
        printf("6. Supprimer le graphe et quitter\n");
        printf("Choix : ");
        scanf("%d", &choix);

        switch (choix) {
            case 1:
                if (grapheCree) {
                    supprime_graphe_matrice(&graphe);
                }
                printf("Nombre de sommets : ");
                scanf("%d", &n);
                graphe = cree_graphe_vide_matrice(n);
                grapheCree = true;
                printf("Graphe vide créé avec %d sommets.\n", n);
                break;
            case 2:
                if (!grapheCree) {
                    printf("Créez d'abord un graphe.\n");
                    break;
                }
                printf("Entrez les deux sommets à connecter : ");
                scanf("%d %d", &sommet1, &sommet2);
                ajoute_arete_matrice(&graphe, sommet1, sommet2);
                printf("Arête ajoutée entre %d et %d.\n", sommet1, sommet2);
                break;
            case 3:
                if (!grapheCree) {
                    printf("Créez d'abord un graphe.\n");
                    break;
                }
                printf("Nombre de sommets : %d\n", nb_sommets_matrice(&graphe));
                break;
            case 4:
                if (!grapheCree) {
                    printf("Créez d'abord un graphe.\n");
                    break;
                }
                printf("Entrez les deux sommets pour vérifier s'ils sont voisins : ");
                scanf("%d %d", &sommet1, &sommet2);
                if (sont_voisins_matrice(&graphe, sommet1, sommet2)) {
                    printf("Les sommets %d et %d sont voisins.\n", sommet1, sommet2);
                } else {
                    printf("Les sommets %d et %d ne sont pas voisins.\n", sommet1, sommet2);
                }
                break;
            case 5:
                if (!grapheCree) {
                    printf("Créez d'abord un graphe.\n");
                    break;
                }
                printf("Nombre d'arêtes : %d\n", nb_aretes_matrice(&graphe));
                break;
            case 6:
                if (grapheCree) {
                    supprime_graphe_matrice(&graphe);
                    grapheCree = false;
                }
                printf("Graphe supprimé, fin du programme.\n");
                return 0;
            default:
                printf("Choix invalide.\n");
                break;
        }
   
    }

    
return 0;
}