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


// Définition des structures 

typedef struct 
{
	int   nb_sommets;
	int** matrice_adjacence;
} Graphe;

// Declaration des fonctions

void lire_graphe_fichier_matrice(Graphe* G, const char* graph_fic_nom) ; 
void visiter_matrice_prof(Graphe* G, int* tabMarque, int sommet) ;
void affichage_graphe(Graphe* G);
void profondeur(Graphe* G, int sommet);

// Fonctions

void lire_graphe_fichier_matrice(Graphe* G, const char* graph_fic_nom) // Déclaration de la fonction pour lire un graphe depuis un fichier
{
	FILE* fp; // Déclare un pointeur de fichier
	fp = fopen(graph_fic_nom, "r"); // Ouvre le fichier en mode lecture

	if (fp != NULL) // Vérifie si le fichier a été ouvert avec succès
	{
		int nb_sommets, nb_arcs; // Déclare les variables pour stocker le nombre de sommets et d'arcs
		fscanf(fp, "%d %d", &nb_sommets, &nb_arcs); // Lit le nombre de sommets et d'arcs depuis le fichier

		G->nb_sommets = nb_sommets; // Initialise le nombre de sommets dans le graphe
		G->matrice_adjacence = (int**) malloc(nb_sommets * sizeof(int*)); // Alloue de la mémoire pour la matrice d'adjacence

		for (int i = 0; i < nb_sommets; i++) // Boucle pour allouer de la mémoire pour chaque ligne de la matrice
			G->matrice_adjacence[i] = (int*) malloc(nb_sommets * sizeof(int)); // Alloue de la mémoire pour une ligne de la matrice d'adjacence

		/*Initialiser la matrice d'adjacence */
		for (int i = 0; i < nb_sommets; i++) // Double boucle pour initialiser la matrice d'adjacence avec des zéros
			for (int j = 0; j < nb_sommets; j++)
				G->matrice_adjacence[i][j] = 0; // Initialise la cellule [i][j] à 0

		/*Instancier la matrice d'adjacence à partir d'un fichier */
		for (int i = 0; i < nb_arcs; i++) // Boucle pour lire les arcs du fichier
		{
			int u, v; // Déclare les variables pour stocker les sommets de l'arc
			fscanf(fp, "%d%d", &u, &v); // Lit un arc du fichier
			G->matrice_adjacence[u - 1][v - 1] = 1; // Marque l'existence de l'arc dans la matrice d'adjacence
		}
		printf("Soit le graphe G (matrice d'adjacence) : \n"); // Affiche un message indiquant que le graphe a été chargé
		//affichage_graphe(G); // Appel à une fonction d'affichage du graphe (commenté ici)
		fclose(fp); // Ferme le fichier
	}
	else printf("Le fichier n'a pas été trouvé."); // Imprime un message d'erreur si le fichier n'est pas trouvé
}





// Fonction qui afffcihe le graphe matrice 


void affichage_graphe(Graphe* G) // Déclaration de la fonction pour afficher la matrice d'adjacence d'un graphe
{  
    
    
    printf("Matrice d'adjacence du graphe :\n"); // Affiche un en-tête pour la matrice d'adjacence

 
	for (int i = 0; i < G->nb_sommets; i++) // Boucle externe sur tous les sommets du graphe
	{
		for (int j = 0; j < G->nb_sommets; j++) // Boucle interne pour chaque sommet, itère sur tous les autres sommets
            
			printf("%d ", G->matrice_adjacence[i][j]); // Affiche la valeur de l'adjacence entre le sommet i et le sommet j suivie d'un espace
        
		printf("\n"); // Après avoir affiché toutes les adjacences pour le sommet i, imprime un saut de ligne pour passer au sommet suivant
	}
    
}

// /* G est le graphe, et sommet est le numéro du sommet dans le tableau de sommet de G 


// Fonction qui visite le graphe selon le parcours en profondeur 

    
void visiter_matrice_prof(Graphe* G, int* tabMarque, int sommet) 
{
    printf("%d, ", sommet + 1); // Affiche le sommet actuel (ajusté de +1 pour un affichage plus naturel, partant de 1 au lieu de 0)
    tabMarque[sommet] = 1; // Marque le sommet comme visité

    for (int i = 0; i < G->nb_sommets; i++)// Pour chaque sommet dans le graphe
        { 
        if (G->matrice_adjacence[sommet][i] == 1 && tabMarque[i] == 0) // Si le sommet i est adjacent au sommet actuel et n'a pas encore été visité
        
        { 
            visiter_matrice_prof(G, tabMarque, i); // Visite récursivement le sommet i
        }
    }
}


//Fonction qui initialise le parcours en profondeur à un sommet spécifié 

void profondeur(Graphe* G, int sommet)

{
	// Alloue et initialise le tableau de marquage des sommets
    
	int* tabMarque = (int*) malloc(sizeof(int) * G->nb_sommets);

	for (int i = 0; i < G->nb_sommets; i++) // Initialiser tous les sommets comme non visités
        
		tabMarque[i] = 0;

	visiter_matrice_prof(G, tabMarque, sommet); // Commence le parcours en profondeur à partir du sommet donné
}


int main() {
    Graphe G;
    int choix, sommet;
    const char* graph_fic_nom = "graph_10_13.txt";
    bool grapheChargé = false;

    do {
        printf("\nMenu :\n");
        printf("1. Charger le graphe depuis un fichier\n");
        printf("2. Afficher la matrice d'adjacence du graphe\n");
        printf("3. Effectuer un parcours en profondeur à partir d'un sommet\n");
        printf("4. Quitter\n");
        printf("Entrez votre choix : ");
        scanf("%d", &choix);

        switch (choix) {
            case 1:
                lire_graphe_fichier_matrice(&G, graph_fic_nom);
                grapheChargé = true;
                break;
            case 2:
                if (grapheChargé) {
                    affichage_graphe(&G);
                } else {
                    printf("Veuillez d'abord charger un graphe.\n");
                }
                break;
            case 3:
                if (grapheChargé) {
                    printf("Entrez le numéro du sommet (commençant à 0) : ");
                    scanf("%d", &sommet);
                    if (sommet >= 0 && sommet < G.nb_sommets) {
                        printf("\nParcours en profondeur à partir du sommet %d : ", sommet + 1);
                        profondeur(&G, sommet);
                        printf("\n");
                    } else {
                        printf("Numéro de sommet invalide.\n");
                    }
                } else {
                    printf("Veuillez d'abord charger un graphe.\n");
                }
                break;
            case 4:
                printf("Au revoir!\n");
                break;
            default:
                printf("Choix invalide. Veuillez réessayer.\n");
        }
    } while (choix != 4);

    return 0;

}