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

// Definition des structures 

// fic file

typedef struct _cellule // Définit une structure pour une cellule de la file
{ 
	int		identifiant; // Stocke l'identifiant (ou la valeur) de la cellule
	struct	_cellule* suivant; // Pointeur vers la cellule suivante dans la file
} Cellule;

typedef struct // Définit une structure pour la file
{ 
	Cellule* tete; // Pointeur vers la première cellule de la file
	Cellule* queue; // Pointeur vers la dernière cellule de la file
} File;



// Fic  graphe 


typedef struct _sommet {
	int		isucceseur;
	struct	_sommet* successeur;
} Sommet;

typedef struct {
	int		nb_sommets;
	Sommet** liste_successeurs;
} Graphe;


// Declaration des fonctions 

File creer_file_vide(); // fic file
int estVide(File* pF); // fic file
int Defiler(File *pF); // fic file
void Enfiler(File *pF, int idCellule); // fic file
void Detruire_file(File *pF); // fic file


fic graphe 


void affichage_graphe_liste_adjacence(Graphe* G)

// Fonctions


// Fonction qui cree une file vide 


File creer_file_vide() // Fonction pour initialiser une file vide
{
	File fileVide; // Crée une file vide
	fileVide.tete = NULL; // Initialise la tête de la file à NULL (file vide)
	return fileVide; // Retourne la file vide initialisée
}

// Fonction qui verifie si la file est vide 

int estVide(File* pF) // Fonction pour vérifier si une file est vide
{
	return (pF->tete == NULL); // Retourne vrai (1) si la file est vide, faux (0) sinon
}

// Fonction qui enfile 


void Enfiler(File *pF, int idCellule) // Fonction pour ajouter une cellule à la fin de la file
{
	Cellule* nouvelElement = (Cellule*) malloc(sizeof(Cellule)); // Alloue de la mémoire pour une nouvelle cellule

	nouvelElement->identifiant = idCellule; // Initialise l'identifiant de la nouvelle cellule
	nouvelElement->suivant = NULL; // Initialise le pointeur suivant de la nouvelle cellule à NULL
	
	if (pF->tete == NULL) // Si la file est vide
	{
		pF->tete = pF->queue = nouvelElement; // La nouvelle cellule devient à la fois la tête et la queue de la file
	}
	else // Si la file n'est pas vide
	{ 
		pF->queue->suivant = nouvelElement; // Lie la dernière cellule de la file à la nouvelle cellule
		pF->queue = nouvelElement; // La nouvelle cellule devient la nouvelle queue de la file
	}	
}


int Defiler(File *pF) // Fonction pour retirer et retourner l'identifiant de la cellule en tête de file
{	
	int id = pF->tete->identifiant; // Sauvegarde l'identifiant de la cellule en tête

	Cellule* temp = pF->tete; // Sauvegarde temporairement le pointeur vers la cellule en tête
	pF->tete = pF->tete->suivant; // Avance la tête de la file à la cellule suivante

	if (pF->tete == NULL) // Si après suppression la file est vide
		pF->queue = NULL; // Assure que la queue est également mise à NULL
	
	free(temp); // Libère la mémoire de la cellule supprimée
	return id; // Retourne l'identifiant de la cellule supprimée
}

void Detruire_file(File *pF) // Fonction pour détruire entièrement la file et libérer la mémoire
{
	Cellule* element = pF->tete; // Initialise un pointeur pour parcourir la file

	while (pF->tete != NULL) // Tant que la tête de la file n'est pas NULL (file pas vide)
	{
		element = pF->tete; // Sauvegarde le pointeur vers la cellule courante
		pF->tete = element->suivant; // Avance la tête de la file à la cellule suivante
		free(element); // Libère la mémoire de la cellule courante
	}
}





//-------------------Partie graphe--------------------------



// fonction qui lit le graphe depuis un fichier


void graphe_liste_adjacence(Graphe* G, const char* nomFichierGraphe) // Fonction pour construire le graphe à partir d'un fichier
{
    FILE *fp;
    fp = fopen(nomFichierGraphe, "r"); // Ouvre le fichier de graphe en mode lecture
    
    if (fp != NULL) { // Vérifie si le fichier a été ouvert avec succès

        int nb_sommets, nb_arcs, sommetDepart, sommetArrivee;

        fscanf(fp, "%d %d", &nb_sommets, &nb_arcs); // Lit le nombre de sommets et d'arcs du graphe depuis le fichier
        
        G->nb_sommets = nb_sommets; // Initialise le nombre de sommets dans le graphe
        G->liste_successeurs = (Sommet**) malloc(nb_sommets * sizeof(Sommet*)); // Alloue la mémoire pour les listes de successeurs

        for (int i = 0; i < nb_sommets; i++) 
            G->liste_successeurs[i] = NULL; // Initialise chaque liste de successeurs à NULL
        
        for (int i = 0; i < nb_arcs; i++) // Pour chaque arc dans le fichier
        {
            fscanf(fp, "%d %d", &sommetDepart, &sommetArrivee); // Lit les sommets de départ et d'arrivée de l'arc
            
            Sommet* nouveauSommet = (Sommet*) malloc(sizeof(Sommet)); // Alloue la mémoire pour un nouveau sommet
            
            sommetDepart--; // Ajuste l'index du sommet de départ pour la base 0
            
            sommetArrivee--; // Ajuste l'index du sommet d'arrivée pour la base 0
            
            nouveauSommet->isucceseur = sommetArrivee; // Définit l'index du successeur
            nouveauSommet->successeur = G->liste_successeurs[sommetDepart]; // Ajoute le nouveau sommet au début de la liste de successeurs du sommet de départ
            G->liste_successeurs[sommetDepart] = nouveauSommet; // Met à jour la tête de la liste de successeurs du sommet de départ
        }
    }
    else printf("Le fichier n'a pas été trouvé."); // Affiche un message d'erreur si le fichier ne peut pas être ouvert
    fclose(fp); // Ferme le fichier
}




// Fonction qui effectue le parcours en largeur 




void parcours_largeur(Graphe* G, int sommet_id) // Démarre un parcours en largeur à partir d'un sommet donné
{
	int* marque = (int*) malloc(G->nb_sommets * sizeof(int)); // Alloue dynamiquement un tableau pour marquer les sommets visités
	
	for (int i = 0; i < G->nb_sommets; i++) // Initialise le tableau de marquage à 0 (non visité) pour tous les sommets
		marque[i] = 0;

    
	sommet_id--; // Ajuste l'indice du sommet pour passer d'une base 1 à une base 0
	marque[sommet_id] = 1; // Marque le sommet de départ comme visité
	
	File F = creer_file_vide(); // Initialise une file vide pour le parcours en largeur
	enfiler(&F, sommet_id); // Ajoute le sommet de départ à la file

	while(!est_vide(&F)) // Tant que la file n'est pas vide, continue le parcours
	{ 
		int sommet_sortant = defiler(&F); // Défile un sommet pour le traiter
		Sommet* courant = G->liste_successeurs[sommet_sortant]; // Obtient la liste des successeurs du sommet traité
		while (courant != NULL) // Parcourt tous les successeurs du sommet
		{
			if (marque[courant->isucceseur] != 1) // Si le successeur n'a pas encore été visité
			{
				marque[courant->isucceseur] = 1; // Marque le successeur comme visité
				printf(" (%d) ", courant->isucceseur + 1); // Affiche le successeur (en ajustant l'indice pour l'affichage)
				enfiler(&F, courant->isucceseur); // Ajoute le successeur à la file pour un traitement ultérieur
			}
			courant = courant->successeur; // Passe au successeur suivant dans la liste
		}
	} 
}



void affichage_graphe_liste_adjacence(Graphe* G) // Définit la fonction pour afficher le graphe sous forme de listes d'adjacence
{	
	for(int i = 0; i < G->nb_sommets; i++) // Boucle sur tous les sommets du graphe
	{
		printf("Sommet %d : ", i+1); // Affiche le numéro du sommet, ajusté pour un affichage commençant à 1

		Sommet* courant = G->liste_successeurs[i]; // Accède à la liste des successeurs du sommet courant

		while(courant != NULL) // Parcourt la liste des successeurs tant qu'il y a des éléments
		{
			printf("%d, ", courant->isucceseur + 1); // Affiche le successeur (ajusté pour un affichage commençant à 1)
			courant = courant->successeur; // Passe au successeur suivant dans la liste
		} 
		printf("\n"); // Insère une nouvelle ligne après avoir listé tous les successeurs d'un sommet
	}
}


// Explore récursivement le graphe à partir d'un sommet donné, en utilisant un parcours en profondeur.
void visiter_liste_adjacence(Graphe* G, int* marquage, int sommet)
{
	printf("%d, ", sommet + 1); // Affiche le sommet courant, ajusté pour un affichage commençant à 1
	marquage[sommet] = 1; // Marque le sommet comme visité

	Sommet* courant = G->liste_successeurs[sommet]; // Récupère la liste des successeurs du sommet
	while (courant != NULL) // Parcourt tous les successeurs du sommet
	{
		if (marquage[courant->isucceseur] == 0) // Si le successeur n'a pas encore été visité
			visiter_liste_adjacence(G, marquage, courant->isucceseur); // Visite récursivement le successeur

		courant = courant->successeur; // Passe au successeur suivant dans la liste
	}
}




// ----------------------------Parcours en profondeur-------------------------------




// Fonction qui visite en profondeur avec liste d'adjacence 



void visiter_liste_adjacence(Graphe* G, int* marquage, int sommet)
{
	printf("%d, ", sommet + 1); // Affiche le sommet courant, ajusté pour un affichage commençant à 1
	marquage[sommet] = 1; // Marque le sommet comme visité

	Sommet* courant = G->liste_successeurs[sommet]; // Récupère la liste des successeurs du sommet
	while (courant != NULL) // Parcourt tous les successeurs du sommet
	{
		if (marquage[courant->isucceseur] == 0) // Si le successeur n'a pas encore été visité
			visiter_liste_adjacence(G, marquage, courant->isucceseur); // Visite récursivement le successeur

		courant = courant->successeur; // Passe au successeur suivant dans la liste
	}
}


// Fonction qui effectue le parcours en profondeur 




void parcours_profondeur_liste_adjacence(Graphe* G, int sommet)


{
    
	int* marquage = (int*)malloc(sizeof(int) * G->nb_sommets) ; // Alloue un tableau pour marquer les sommets visités

	for (int i = 0; i < G->nb_sommets; i++) // Initialise tous les sommets comme non visités (marqués à 0)

        
		marquage[i] = 0;

	visiter_liste_adjacence(G, marquage, sommet - 1); // Commence le parcours en profondeur du sommet spécifié, ajusté pour l'indexation à base 0
}



// ------------------- Graphe biparti--------------------


//Question 1

// Tableau T de card(V) initialisé à -1 

// for all s dans V 
	// if T[s]==-1 then
	        // T[s]=0
		// f <-creer file 
		// f.enfiler(s)
		// while non f vide() do 
			// s <- defiler()
			// for all voisins adj de s dans V do:
				// if T[adj]==-1 then 
					// T[adj]=1-T[s]
					// f.enfiler(adj)
					// end if 
				// elif T[adj]==T[s]
					//then return False 
//return True 
				//end elif 
			//end for 
		//end while 
	//end if 
//end for  

// Question 2

//Les opérations coûteuses sont le parcours des voisins de chacun des sommets ainsi que  la vérification de la couleur  car il faut être sûre que chaque sommet a bien été visité et coloré correctement sans entrer dans une boucle infinie.


//La représentation la plus adaptée pour cet algorithme  qui a donc avec la complexité la plus faible est avec des listes d’adjacence car l’espace mémoire allouée est beaucoup plus faible. En effet avec une matrice la complexité est de V**2 et avec des listes d’adjacence, elle est de V+E avec V  est le nombre de sommets et E le nombre d’arêtes. 


//On décide d’utiliser une file pour représenter les sommets à visiter. De plus, les sommets sont dits  ouverts lorsqu’ils sont enfilés dans la file et « fermés » une fois défilés . Enfin on utilise un tableau de marquage qui permet d’identifier les sommets non visités.







bool biparti(Graphe* G, int sommet_id) // Démarre la vérification de la propriété bipartite à partir d'un sommet donné
{
	int* marque = (int*) malloc(G->nb_sommets * sizeof(int)); // Alloue un tableau pour marquer les sommets (non visité, ensemble 1 ou 2)
	
	for (int i = 0; i < G->nb_sommets; i++) // Initialise le tableau à 0 (non visité) pour tous les sommets
		marque[i] = 0;

	sommet_id--; // Ajuste l'indice du sommet pour l'indexation à base 0
    
	marque[sommet_id] = 1; // Marque le sommet de départ comme appartenant à l'ensemble 1
	
	File F = creer_file_vide(); // Initialise une file pour le parcours en largeur
    
	enfiler(&F, sommet_id); // Ajoute le sommet de départ à la file

	while(!est_vide(&F)) // Tant que la file n'est pas vide, continue le parcours
	{ 
		int sommet_out = defiler(&F); // Défile un sommet pour le traiter
        
		Sommet* courant = G->liste_successeurs[sommet_out]; // Accède à la liste des successeurs du sommet traité
		while (courant != NULL) // Parcourt tous les successeurs du sommet
		{
			if (marque[courant->isucceseur] == 0) // Si le successeur n'a pas encore été visité
			{
				// Marque le successeur avec le marqueur opposé à celui du sommet actuel
				marque[courant->isucceseur] = (marque[sommet_out] == 1) ? 2 : 1; 
				printf(" (%d) ", courant->isucceseur + 1); // Affiche le successeur (ajusté pour un affichage basé 1)
				enfiler(&F, courant->isucceseur); // Ajoute le successeur à la file pour son traitement ultérieur
			}
			else if (marque[sommet_out] == marque[courant->isucceseur]) // Si le sommet actuel et le successeur ont le même marqueur
				return false; // Le graphe n'est pas biparti
			courant = courant->successeur; // Passe au successeur suivant
		}
	} 
	return true; // Si le graphe passe tous les tests, il est biparti
}