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

// Definition des structures 


// Définition d'une structure pour un nœud dans la liste des successeurs.

typedef struct _noeud
{
    int id;               // Identifiant du nœud de destination.
    int poids;            // Poids de l'arc menant à ce nœud.
    struct _noeud* successeur; // Pointeur vers le prochain nœud successeur dans la liste.
} Noeud;

// Définition d'une structure pour représenter un graphe.


typedef struct
{
    int nb_noeuds;        // Nombre total de nœuds dans le graphe.
    Noeud** liste_successeurs; // Tableau de pointeurs vers les listes de successeurs de chaque nœud.
} Graphe;


// Décalration des fonctions 

Graphe cree_graphe_vide_liste(int n) ; 
void supprime_graphe_liste(Graphe* graphe) ;

void ajoute_arete_non_oriente_liste(Graphe* graphe, int sommet1, int sommet2) ;
void ajoute_arete_oriente_liste(Graphe* graphe, int sommet1, int sommet2);

int nb_sommets_liste(Graphe* graphe) ;  
int sont_successeurs_liste(Graphe* graphe, int sommet1, int sommet2) ;
int sont_predecesseurs_liste(Graphe* graphe, int sommet1, int sommet2) ;

int nb_successeurs_liste(Graphe* graphe);
int nb_predecesseurs_liste(Graphe* graphe, int sommet);
int nb_voisins_liste(Graphe* graphe, int sommet) ;

int nb_aretes_non_oriente_liste(Graphe* graphe);
int nb_aretes_liste_non_oriente(Graphe* graphe);

void affiche_graphe_non_oriente_liste(Graphe* graphe);
void affiche_graphe_oriente_liste(Graphe* graphe;
int sont_voisins(Graphe* graphe, int sommet1, int sommet2);

// Fonctions

// Fonction qui cree un graphe vide 

Graphe cree_graphe_vide_liste(int n) 
{ 
    Graphe graphe; // Déclare une variable de type Graphe.
    
    graphe.nb_noeuds = n; // Affecte le nombre de nœuds spécifié par 'n' au graphe.
    
    graphe.liste_successeurs = (Noeud**)malloc(n * sizeof(Noeud*)); // Alloue de la mémoire pour le tableau contenant les listes de successeurs.
    for (int i = 0; i < n; i++) { // Boucle pour initialiser chaque liste de successeurs.
        graphe.liste_successeurs[i] = NULL; // Initialise chaque liste de successeurs à NULL pour indiquer qu'il n'y a pas encore de successeurs.
    }
    return graphe; // Retourne le graphe nouvellement créé et initialisé.
}


// Fonction pour supprimer un graphe et libérer toute la mémoire allouée.


void supprime_graphe_liste(Graphe* graphe) 

{
    for (int i = 0; i < graphe->nb_noeuds; i++)  // Parcourt chaque liste de successeurs dans le graphe.
    { 
        Noeud* courant = graphe->liste_successeurs[i]; // Pointe sur le premier nœud de la liste i.
        
        while (courant != NULL)  // Tant que la fin de la liste n'est pas atteinte.
            {
            Noeud* suivant = courant->successeur; // Sauvegarde le pointeur vers le nœud suivant.
            free(courant); // Libère la mémoire allouée pour le nœud courant.
            courant = suivant; // Passe au nœud suivant dans la liste.
        }
    }
    free(graphe->liste_successeurs); // Libère la mémoire allouée pour le tableau des listes de successeurs.
}


    
// Fonction pour ajouter une arête entre deux sommets dans un graphe non orienté.


void ajoute_arete_non_oriente_liste(Graphe* graphe, int sommet1, int sommet2) // Crée un nouveau nœud pour l'arête de sommet1 à sommet2.
    
    {

        
    Noeud* nouveauNoeud = (Noeud*)malloc(sizeof(Noeud)); // Alloue de la mémoire pour le nouveau nœud.   
        
    nouveauNoeud->id = sommet2 ; // Assigne sommet2 comme l'ID du nœud de destination.       
    nouveauNoeud->successeur = graphe->liste_successeurs[sommet1] ; // Le nouveau nœud pointe vers le successeur actuel de sommet1.
    graphe->liste_successeurs[sommet1] = nouveauNoeud ; // Fait du nouveau nœud le premier successeur de sommet1.

    // Répète le processus pour ajouter un nœud de sommet2 à sommet1 pour maintenir la non orientation du graphe.
        
    nouveauNoeud = (Noeud*)malloc(sizeof(Noeud)); // Alloue de la mémoire pour un autre nouveau nœud.
        
    nouveauNoeud->id = sommet1; // Assigne sommet1 comme l'ID du nœud de destination.
        
    nouveauNoeud->successeur = graphe->liste_successeurs[sommet2]; // Le nouveau nœud pointe vers le successeur actuel de sommet2.
        
    graphe->liste_successeurs[sommet2] = nouveauNoeud; // Fait du nouveau nœud le premier successeur de sommet2.

        
    }

// Fonction pour ajouter une arête orientée de sommet1 vers sommet2 dans un graphe orienté.

void ajoute_arete_oriente_liste(Graphe* graphe, int sommet1, int sommet2)
{
    // Crée un nouveau nœud pour l'arête de sommet1 à sommet2.
    Noeud* nouveauNoeud = (Noeud*)malloc(sizeof(Noeud)); // Alloue de la mémoire pour le nouveau nœud.
    
    nouveauNoeud->id = sommet2; // Assigne sommet2 comme l'ID du nœud de destination.
    
    nouveauNoeud->successeur = graphe->liste_successeurs[sommet1]; // Fait pointer le nouveau nœud vers le successeur actuel de sommet1.
    
    graphe->liste_successeurs[sommet1] = nouveauNoeud; // Fait du nouveau nœud le premier successeur de sommet1.
}


// Fonction pour obtenir le nombre total de sommets dans le graphe.
    
int nb_sommets_liste(Graphe* graphe) 
    
    {
        
    return graphe->nb_noeuds; // Retourne directement le nombre de nœuds dans le graphe.
        
    }



// Fonction pour vérifier si deux sommets sont voisins dans un graphe non orienté.


int sont_voisins(Graphe* graphe, int sommet1, int sommet2) 

{
    
    Noeud* courant = graphe->liste_successeurs[sommet1];// Parcourt la liste des successeurs de sommet1 pour voir si sommet2 est l'un d'entre eux.
    while (courant != NULL) // Continue tant qu'il reste des successeurs.
    { 
        if (courant->id == sommet2)// Vérifie si l'ID du nœud courant est égal à sommet2.
        { 
            return 1; // Si oui, retourne 1 pour indiquer que sommet2 est un voisin de sommet1.
        }
        courant = courant->successeur; // Passe au successeur suivant dans la liste.
    }

    // (Optionnel) Parcourt la liste des successeurs de sommet2 pour voir si sommet1 est l'un d'entre eux.
    // Cette étape est facultative dans un graphe non orienté si la liste des successeurs est bien maintenue des deux côtés pour chaque arête.
    courant = graphe->liste_successeurs[sommet2];
    while (courant != NULL)
        {
        if (courant->id == sommet1)
        {
            return 1; // Si sommet1 est trouvé dans la liste des successeurs de sommet2, ils sont également voisins.
        }
        courant = courant->successeur;
    }

    return 0; // Si sommet2 n'est pas trouvé dans la liste des successeurs de sommet1, retourne 0 pour indiquer qu'ils ne sont pas voisins.
}

// Fonction pour vérifier si un sommet est voisin d'un autre dans un graphe orienté.

    
int sont_successeurs_liste(Graphe* graphe, int sommet1, int sommet2) 
    
    {
    Noeud* courant = graphe->liste_successeurs[sommet1]; // Commence à parcourir la liste des successeurs de sommet1.
        
    while (courant != NULL) // Tant qu'il y a des nœuds dans la liste.
        { 
        if (courant->id == sommet2) // Vérifie si l'ID du nœud courant est égal à sommet2.
        { 
            return 1; // Si oui, sommet2 est un successeur de sommet1, donc ils sont voisins.
        }
        courant = courant->successeur; // Passe au nœud suivant dans la liste.
    }
    return 0; // Si la liste est parcourue sans trouver sommet2, ils ne sont pas voisins.
}

// Fonction pour vérifier si `sommet1` est prédecesseur de `sommet2` dans un graphe orienté.

int sont_predecesseurs_liste(Graphe* graphe, int sommet1, int sommet2) 
{
    for (int i = 0; i < graphe->nb_noeuds; i++)// Parcourt tous les nœuds du graphe.
        { 
        Noeud* courant = graphe->liste_successeurs[i]; // Accède à la liste des successeurs du nœud courant.
        while (courant != NULL) // Tant que la liste n'est pas vide.
        { 
            if (courant->id == sommet2 && i == sommet1) // Vérifie si le nœud courant est un successeur de `sommet2` et si i est `sommet1`.
            { 
                return 1; // Retourne 1 si `sommet1` est trouvé comme prédecesseur de `sommet2`.
            }
            courant = courant->successeur; // Passe au successeur suivant dans la liste.
        }
    }
    return 0; // Retourne 0 si `sommet1` n'est pas un prédecesseur de `sommet2`.
}


// Fonction pour calculer le nombre total d'arêtes dans un graphe non orienté.

int nb_aretes_liste_non_oriente(Graphe* graphe) 

{
    int compteur = 0; // Initialise un compteur d'arêtes à 0.
    
    for (int i = 0; i < graphe->nb_noeuds; i++) // Parcourt chaque liste de successeurs pour chaque nœud du graphe.
    
    { 
        Noeud* courant = graphe->liste_successeurs[i]; // Commence par le premier nœud de la liste i.
        
        while (courant != NULL) // Tant que la fin de la liste n'est pas atteinte.
        
        
        { 
            compteur++; // Incrémente le compteur pour chaque nœud rencontré.
            courant = courant->successeur ; // Passe au nœud successeur suivant dans la liste.
        }
    }
    
    return compteur / 2 ; // Divise le compteur par 2 car chaque arête est comptée deux fois dans un graphe non orienté.
}

// Fonction pour calculer le nombre de voisins (degré) d'un nœud spécifié dans le graphe.


int nb_voisins_liste(Graphe* graphe, int sommet) 

{
    int degre = 0; // Initialise le degré (nombre de voisins) du nœud à 0.
    
    Noeud* courant = graphe->liste_successeurs[sommet]; // Commence par le premier nœud de la liste du sommet.
    while (courant != NULL)// Tant que la fin de la liste n'est pas atteinte.
        { 
        degre++; // Incrémente le degré pour chaque nœud successeur rencontré.
        courant = courant->successeur; // Passe au nœud successeur suivant dans la liste.
    }
    return degre; // Retourne le degré du nœud, c'est-à-dire son nombre de voisins.
}



// Fonction pour compter le nombre de sucesseurs dans un graphe orienté.


int nb_successeurs_liste(Graphe* graphe) 

{
    int compteur = 0; // Initialise le compteur d'arêtes à 0.
    
    for (int i = 0; i < graphe->nb_noeuds; i++) // Parcourt chaque liste de successeurs pour chaque nœud.
    { 
        Noeud* courant = graphe->liste_successeurs[i]; // Commence à parcourir la liste des successeurs du nœud courant.
        
        while (courant != NULL)// Continue tant qu'il reste des successeurs.
            
        { 
            compteur++; // Incrémente le compteur pour chaque successeur trouvé.
            
            courant = courant->successeur; // Passe au successeur suivant dans la liste.
        }
    }
    return compteur; // Retourne le compteur total d'arêtes dans le graphe orienté.
}


// Fonction pour calculer le nombre de prédécesseurs d'un nœud spécifié dans un graphe orienté.

int nb_predecesseurs_liste(Graphe* graphe, int sommet)
{
    int compteur = 0; // Initialise le compteur de prédécesseurs à 0.
   
    for (int i = 0; i < graphe->nb_noeuds; i++) // Parcourt tous les nœuds du graphe pour vérifier leurs successeurs.
        {
        Noeud* courant = graphe->liste_successeurs[i]; // Accède à la liste des successeurs du nœud courant.
        
        while (courant != NULL) // Parcourt la liste des successeurs du nœud courant.
        {
            
            if (courant->id == sommet)  // Vérifie si le nœud courant dans la liste des successeurs est le nœud cible.
            {
                compteur++; // Si oui, incrémente le compteur de prédécesseurs.
            }
            courant = courant->successeur; // Passe au successeur suivant dans la liste.
        }
    }
    return compteur; // Retourne le nombre total de prédécesseurs du nœud spécifié.
}

// Fonction pour calculer le nombre total d'arêtes dans un graphe non orienté.
int nb_aretes_non_oriente_liste(Graphe* graphe)
{
    int compteur = 0; // Initialise le compteur d'arêtes à 0.
    for (int i = 0; i < graphe->nb_noeuds; i++)// Parcourt chaque liste de successeurs pour chaque nœud.
        { 
        Noeud* courant = graphe->liste_successeurs[i]; // Commence à parcourir la liste des successeurs du nœud courant.
        while (courant != NULL)// Continue tant qu'il reste des successeurs.
            { 
            // Dans un graphe non orienté, chaque arête est comptée une fois pour chaque paire de nœuds.
            if (i < courant->id) // Évite de compter deux fois la même arête.
            { 
                compteur++; // Incrémente le compteur pour chaque arête unique trouvée.
            }
            courant = courant->successeur; // Passe au successeur suivant dans la liste.
        }
    }
    return compteur; // Retourne le compteur total d'arêtes dans le graphe non orienté.
}


// Fonction pour afficher la matrice d'adjacence d'un graphe non orienté.
void affiche_graphe_non_oriente_liste(Graphe* graphe)
{
    printf("Matrice d'adjacence du graphe :\n"); // Affiche un en-tête pour la matrice d'adjacence.
    
    for (int i = 0; i < graphe->nb_noeuds; i++)// Parcourt tous les nœuds du graphe comme lignes de la matrice.
        
    { 
        for (int j = 0; j < graphe->nb_noeuds; j++) // Parcourt tous les nœuds comme colonnes de la matrice pour chaque ligne.
        { 
            if (sont_successeurs_liste(graphe, i, j))// Vérifie si les nœuds i et j sont voisins (connectés).
            
            { 
                printf("1 "); // Affiche '1' si les nœuds sont connectés.
            } else 
            
            {
                printf("0 "); // Affiche '0' si les nœuds ne sont pas connectés.
            }
        }
        printf("\n"); // Passe à la ligne suivante après avoir traité une ligne de la matrice.
    }
}

// Fonction pour afficher la matrice d'adjacence d'un graphe orienté.

void affiche_graphe_oriente_liste(Graphe* graphe)
{
    printf("Matrice d'adjacence du graphe orienté :\n"); // Affiche un en-tête pour la matrice d'adjacence.
    for (int i = 0; i < graphe->nb_noeuds; i++)// Parcourt tous les nœuds du graphe comme lignes de la matrice.
        
    { 
        for (int j = 0; j < graphe->nb_noeuds; j++)// Parcourt tous les nœuds comme colonnes de la matrice pour chaque ligne.
            { 
           
            if (sont_successeurs_liste(graphe, i, j)) // Utilise sont_successeurs_liste pour vérifier si une arête orientée existe de i vers j.
            {
                printf("1 "); // Affiche '1' si une arête orientée de i vers j existe.
            } else 
            
            {
                printf("0 "); // Affiche '0' si aucune arête orientée de i vers j n'existe.
            }
        }
        printf("\n"); // Passe à la ligne suivante après avoir traité une ligne de la matrice.
    }
}


// Fonction pour vérifier si le graphe est non orienté.
int est_non_oriente(Graphe* graphe) 

{
    for (int i = 0; i < graphe->nb_noeuds; i++)// Parcourt tous les nœuds du graphe.
        
    { 
        for (int j = i + 1; j < graphe->nb_noeuds; j++)// Parcourt les nœuds pour former des paires sans répétition.
            { 
            if (sont_voisins(graphe, i, j) || sont_voisins(graphe, j, i))// Vérifie s'il existe une arête entre i et j dans les deux sens.
            { 
                // Si une arête existe dans une direction mais pas dans l'autre, le graphe est orienté.
                if (!(sont_voisins(graphe, i, j) && sont_voisins(graphe, j, i)))
                {
                    return 0; // Retourne 0 si le graphe est orienté.
                }
            }
        }
    }
    return 1; // Retourne 1 si toutes les arêtes sont bidirectionnelles, indiquant un graphe non orienté.
}

int main() {
    Graphe* graphe = NULL; // Initialisation à NULL pour gérer l'état de création du graphe.
    int choix, n, sommet1, sommet2, resultat;

    while (1) {
        printf("\nMenu:\n");
        printf("1. Créer un graphe vide\n");
        printf("2. Supprimer le graphe\n");
        printf("3. Ajouter une arête non orientée\n");
        printf("4. Ajouter une arête orientée\n");
        printf("5. Afficher le nombre de sommets\n");
        printf("6. Vérifier si deux sommets sont successeurs\n");
        printf("7. Vérifier si deux sommets sont prédecesseurs\n");
        printf("8. Afficher le nombre de successeurs d'un sommet\n"); // À implémenter
        printf("9. Afficher le nombre de prédecesseurs d'un sommet\n"); // À implémenter
        printf("10. Afficher le nombre de voisins d'un sommet\n");
        printf("11. Afficher le nombre total d'arêtes dans un graphe non orienté\n");
        printf("12. Afficher la matrice d'adjacence pour un graphe non orienté\n");
        printf("13. Afficher la matrice d'adjacence pour un graphe orienté\n");
        printf("14. Vérifier si le graphe est non orienté\n"); // À implémenter
        printf("15. Quitter\n");
        printf("Choix : ");
        scanf("%d", &choix);

        switch (choix) {
            case 1:
                if (graphe != NULL) {
                    supprime_graphe_liste(graphe);
                    free(graphe);
                }
                printf("Nombre de sommets : ");
                scanf("%d", &n);
                graphe = malloc(sizeof(Graphe));
                *graphe = cree_graphe_vide_liste(n);
                break;
            case 2:
                if (graphe != NULL) {
                    supprime_graphe_liste(graphe);
                    free(graphe);
                    graphe = NULL;
                    printf("Graphe supprimé.\n");
                } else {
                    printf("Aucun graphe à supprimer.\n");
                }
                break;
            case 3:
                printf("Entrez les deux sommets à connecter (non orienté): ");
                scanf("%d %d", &sommet1, &sommet2);
                ajoute_arete_non_oriente_liste(graphe, sommet1, sommet2);
                break;
            case 4:
                printf("Entrez les deux sommets à connecter (orienté): ");
                scanf("%d %d", &sommet1, &sommet2);
                ajoute_arete_oriente_liste(graphe, sommet1, sommet2);
                break;
            case 5:
                resultat = nb_sommets_liste(graphe);
                printf("Nombre de sommets dans le graphe: %d\n", resultat);
                break;
            case 6:
                printf("Entrez les deux sommets pour vérifier s'ils sont successeurs: ");
                scanf("%d %d", &sommet1, &sommet2);
                resultat = sont_successeurs_liste(graphe, sommet1, sommet2);
                if (resultat) {
                    printf("Les sommets %d et %d sont successeurs.\n", sommet1, sommet2);
                } else {
                    printf("Les sommets %d et %d ne sont pas successeurs.\n", sommet1, sommet2);
                }
                break;
            case 7:
                printf("Entrez les deux sommets pour vérifier s'ils sont prédecesseurs: ");
                scanf("%d %d", &sommet1, &sommet2);
                resultat = sont_predecesseurs_liste(graphe, sommet1, sommet2);
                if (resultat) {
                    printf("Le sommet %d est prédecesseur du sommet %d.\n", sommet1, sommet2);
                } else {
                    printf("Le sommet %d n'est pas prédecesseur du sommet %d.\n", sommet1, sommet2);
                }
                break;
             case 8:
                printf("Entrez le sommet pour connaître son nombre de successeurs: ");
                scanf("%d", &sommet1);
                // Assumant que vous avez une fonction pour calculer cela.
                resultat = nb_successeurs_liste(graphe, sommet1);
                printf("Le sommet %d a %d successeurs.\n", sommet1, resultat);
                break;
            case 9:
                printf("Entrez le sommet pour connaître son nombre de prédécesseurs: ");
                scanf("%d", &sommet1);
                // Assumant que vous avez une fonction pour calculer cela.
                resultat = nb_predecesseurs_liste(graphe, sommet1);
                printf("Le sommet %d a %d prédécesseurs.\n", sommet1, resultat);
                break;
             case 10:
                printf("Entrez le sommet pour connaître son nombre de voisins: ");
                scanf("%d", &sommet1);
                resultat = nb_voisins_liste(graphe, sommet1);
                printf("Le sommet %d a %d voisins.\n", sommet1, resultat);
                break;
            case 11:
                resultat = nb_aretes_non_oriente_liste(graphe);
                printf("Nombre total d'arêtes dans le graphe non orienté: %d\n", resultat);
                break;
            case 12:
                affiche_graphe_non_oriente_liste(graphe);
                break;
            case 13:
                affiche_graphe_oriente_liste(graphe);
                break;
             case 14:
                // Cette fonction vérifierait si pour chaque arête A->B, une arête B->A existe aussi.
                resultat = est_non_oriente(graphe);
                if (resultat == 1) {
                    printf("Le graphe est non orienté.\n");
                } else {
                    printf("Le graphe est orienté.\n");
                }
                break;
              case 15:
                if (graphe != NULL) {
                    supprime_graphe_liste(graphe);
                    free(graphe);
                }
                printf("Au revoir !\n");
                return 0;
        }