#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_non_orienté_matrice(GrapheMatrice* graphe, int sommet1, int sommet2);
void ajoute_arete_orientee_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_non_orienté(GrapheMatrice* graphe);
int nb_aretes_orientee_matrice(GrapheMatrice* graphe);
    
int nb_voisins_matrice(GrapheMatrice* graphe, int sommet);

int nb_successeurs_matrice(GrapheMatrice* graphe, int sommet); 
int nb_predecesseurs_matrice(GrapheMatrice* graphe, int sommet) ;
    
int est_predecesseur(GrapheMatrice* graphe, int sommet1, int sommet2) ;
int est_successeur(GrapheMatrice* graphe, int sommet1, int sommet2) ;
//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
}


// Fonction qui ajoute une arête entre deux sommets non orientés

// La complexité de cette fonction est 2


void ajoute_arete_non_orienté_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é
    
}

// Fonction qui ajoute une arête entre deux sommets pour un graphe orientée

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

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


// Fonction qui compte le nb de sommets du graphe

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



// Fonction qui vérifie  si deux sommets sont voisins


// La complexité est de de 1

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 car sur la matrice d'adjacence on a 1 si les sommets sont connectes 
}


    
// Fonction qui calcule le nombre d'arêtes du graphe

// Puisque ces itérations couvrent la partie supérieure de la matrice d'adjacence sans se chevaucher, le total des itérations  est ,
// ((n(n-1))/2)



int nb_aretes_matrice_non_orienté(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, en effet graphe non oriente donc que la partie supérieure de la matrice 
            
        {
            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
}

    
// Fonction qui calcule le nombre d'aretes dans un graphe orienté

    
int nb_aretes_orientee_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 = 0; j < graphe->nb_sommets; j++) // Parcourt toutes les colonnes
            {
            if (graphe->matrice_adjacence[i][j] == 1) // Si une arête existe entre i et j
            {
                count++;
            }
        }
    }
    return count;
}



    





    
// Fonction qui calcule le nb de voisins 

// Le degré d'un sommet est le nombre d'arêtes dont ce sommet est une extrémité .

// La complexité de cette fonction est n 

int nb_voisins_matrice(GrapheMatrice* graphe, int sommet)


{
    int degre = 0; // Initialisation du degré (nombre de voisins) du sommet à 0.

    
    for (int i = 0; i < graphe->nb_sommets; i++) // Boucle qui parcourt tous les sommets du graphe pour vérifier s'ils sont voisins avec le sommet spécifié.
    
    {
       
        if (graphe->matrice_adjacence[sommet][i] == 1)  // Vérifie si l'élément de la matrice d'adjacence correspondant à [sommet][i] est égal à 1, ce qui signifie que le sommet et le sommet i sont connectés par une arête.
        
        {
            degre++; // Incrémente le degré si une arête est trouvée, indiquant que le sommet a un voisin de plus.
        }
        
    }

    return degre; // Retourne le degré du sommet, qui est égal au nombre total de ses voisins.
}


// Fonction qui compte le nb de successeurs (degres sortant)
// Quand on lit sur les colonnes de la matrice d'adjacence, c'est un successeur 

    
int nb_successeurs_matrice(GrapheMatrice* graphe, int sommet) 
    
    {
    int degreSortant = 0; // Initialise le compteur du nombre de successeurs (voisins sortants) du sommet à 0.
        
    for (int i = 0; i < graphe->nb_sommets; i++) // Parcourt tous les sommets du graphe pour vérifier s'ils sont des successeurs du sommet donné.
        { 
        if (graphe->matrice_adjacence[sommet][i] == 1)// Si une arête existe du sommet donné vers le sommet i (successeur).
        { 
            
            degreSortant++; // Incrémente le compteur des successeurs.
        }
    }
    return degreSortant; // Retourne le nombre total de successeurs du sommet.
}

// Fonction qui compte le nb de predecsseurs(degres sortant)

// Quand on lit sur les lignes de la matrice d'adjacence, c'est un predecesseur 

int nb_predecesseurs_matrice(GrapheMatrice* graphe, int sommet) 
    
    {
    int degreEntrant = 0; // Déclare et initialise le compteur du nombre de prédécesseurs (voisins entrants) à 0.

    
    for (int i = 0; i < graphe->nb_sommets; i++) // Boucle sur tous les sommets du graphe pour identifier les prédécesseurs du sommet donné.
        { 
        if (graphe->matrice_adjacence[i][sommet] == 1) // Vérifie si le sommet donné a une arête entrante depuis le sommet i.
        { 
            degreEntrant++; // Incrémente le compteur si une arête entrante est trouvée, indiquant un prédécesseur supplémentaire.
        }
    }
    return degreEntrant; // Retourne le nombre total de prédécesseurs du sommet spécifié.
}

// Fonction qui vérifie si sommet1 est prédécesseur de sommet2
    
int est_predecesseur(GrapheMatrice* graphe, int sommet1, int sommet2) 
    
{
    return graphe->matrice_adjacence[sommet1][sommet2] == 1; // Retourne 1 (vrai) si une arête va de sommet1 à sommet2, sinon 0 (faux).
}


// Fonction qui vérifie si sommet1 est successeur de sommet2


int est_successeur(GrapheMatrice* graphe, int sommet1, int sommet2) 
    
    {
    return graphe->matrice_adjacence[sommet2][sommet1] == 1; // Retourne 1 (vrai) si une arête va de sommet2 à sommet1, sinon 0 (faux).
    }
    

int main(void) {
    GrapheMatrice graphe;
    bool grapheCree = false;
    int choix, n, sommet1, sommet2, resultat;

    while (true) {
        printf("\nMenu Principal:\n");
        printf("1. Créer un graphe vide\n");
        printf("2. Ajouter une arête non orientée\n");
        printf("3. Ajouter une arête orientée\n");
        printf("4. Vérifier si deux sommets sont voisins\n");
        printf("5. Afficher le nombre de sommets\n");
        printf("6. Afficher le nombre d'arêtes dans un graphe non orienté\n");
        printf("7. Afficher le nombre d'arêtes dans un graphe orienté\n");
        printf("8. Calculer le nombre de voisins d'un sommet\n");
        printf("9. Calculer le nombre de successeurs d'un sommet\n");
        printf("10. Calculer le nombre de prédécesseurs d'un sommet\n");
        printf("11. Vérifier si un sommet est prédécesseur d'un autre\n");
        printf("12. Vérifier si un sommet est successeur d'un autre\n");
        printf("13. Supprimer le graphe\n");
        printf("14. 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 non orienté (indice basé sur 0): ");
                scanf("%d %d", &sommet1, &sommet2);
                ajoute_arete_non_orienté_matrice(&graphe, sommet1, sommet2);
                printf("Arête non orientée ajoutée entre %d et %d.\n", sommet1, sommet2);
                break;
            case 3:
                if (!grapheCree) {
                    printf("Créez d'abord un graphe.\n");
                    break;
                }
                printf("Entrez les deux sommets à connecter orienté (indice basé sur 0): ");
                scanf("%d %d", &sommet1, &sommet2);
                ajoute_arete_orientee_matrice(&graphe, sommet1, sommet2);
                printf("Arête orientée ajoutée de %d vers %d.\n", sommet1, sommet2);
                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 (indice basé sur 0): ");
                scanf("%d %d", &sommet1, &sommet2);
                resultat = sont_voisins_matrice(&graphe, sommet1, sommet2);
                if (resultat) {
                    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 de sommets : %d\n", nb_sommets_matrice(&graphe));
                break;
            case 6:
                if (!grapheCree) {
                    printf("Créez d'abord un graphe.\n");
                    break;
                }
                printf("Nombre d'arêtes (non orienté) : %d\n", nb_aretes_matrice_non_orienté(&graphe));
                break;
            case 7:
                if (!grapheCree) {
                    printf("Créez d'abord un graphe.\n");
                    break;
                }
                printf("Nombre d'arêtes (orienté) : %d\n", nb_aretes_orientee_matrice(&graphe));
                break;
            case 8:
                if (!grapheCree) {
                    printf("Créez d'abord un graphe.\n");
                    break;
                }
                printf("Entrez le sommet pour calculer le nombre de voisins (indice basé sur 0): ");
                scanf("%d", &sommet);
                printf("Nombre de voisins : %d\n", nb_voisins_matrice(&graphe, sommet));
                break;
            case 9:
                if (!grapheCree) {
                    printf("Créez d'abord un graphe.\n");
                    break;
                }
                printf("Entrez le sommet pour calculer le nombre de successeurs (indice basé sur 0): ");
                scanf("%d", &sommet);
                printf("Nombre de successeurs : %d\n", nb_successeurs_matrice(&graphe, sommet));
                break;
            case 10:
                if (!grapheCree) {
                    printf("Créez d'abord un graphe.\n");
                    break;
                }
                printf("Entrez le sommet pour calculer le nombre de prédécesseurs (indice basé sur 0): ");
                scanf("%d", &sommet);
                printf("Nombre de prédécesseurs : %d\n", nb_predecesseurs_matrice(&graphe, sommet));
                break;
            case 11:
                if (!grapheCree) {
                    printf("Créez d'abord un graphe.\n");
                    break;
                }
                printf("Entrez les deux sommets pour vérifier si le premier est prédécesseur du second (indice basé sur 0): ");
                scanf("%d %d", &sommet1, &sommet2);
                resultat = est_predecesseur(&graphe, sommet1, sommet2);
                if (resultat) {
                    printf("%d est prédécesseur de %d.\n", sommet1, sommet2);
                } else {
                    printf("%d n'est pas prédécesseur de %d.\n", sommet1, sommet2);
                }
                break;
            case 12:
                if (!grapheCree) {
                    printf("Créez d'abord un graphe.\n");
                    break;
                }
                printf("Entrez les deux sommets pour vérifier si le premier est successeur du second (indice basé sur 0): ");
                scanf("%d %d", &sommet1, &sommet2);
                resultat = est_successeur(&graphe, sommet1, sommet2);
                if (resultat) {
                    printf("%d est successeur de %d.\n", sommet1, sommet2);
                } else {
                    printf("%d n'est pas successeur de %d.\n", sommet1, sommet2);
                }
                break;
            case 13:
                if (grapheCree) {
                    supprime_graphe_matrice(&graphe);
                    grapheCree = false;
                    printf("Graphe supprimé.\n");
                } else {
                    printf("Aucun graphe à supprimer.\n");
                }
                break;
            case 14:
                printf("Quitter le programme.\n");
                if (grapheCree) {
                    supprime_graphe_matrice(&graphe);
                }
                return 0;
            default:
                printf("Choix invalide.\n");
        }
    }

    return 0;
}