/**********************************************************************
 ***** Pierre Hyvernat, cours info404 "Algorithmes de graphes"    *****
 *****                                                            *****
 ***** Il s'agit des définitions de quelques types de données     *****
 ***** pour le TP en salles machines...                           *****
 ***** Le fichier contient également les prototypes de toutes les *****
 ***** les fonctions définies dans "graphes.c" et les prototypes  *****
 ***** des fonctions que vous devrez définir.                     *****
 *********************************************************************/


#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>

/* Une abbréviation pour la liste vide. */
#define NILL NULL

#define NON_VU 0
#define VU 1
#define EXAMINE 2
#define GRIS 0
#define ROUGE 1
#define VERT -1



/* On va utiliser des listes chainées pour les listes d'adjacences.
 * Comme on veut pouvoir faire des graphes avec un poids sur les arêtes,
 * on utilise la définition suivante.
 *
 * Une liste d'adjacence est donc définit par le type "ListeAdj". Si L
 * est une telle liste, on peut accéder aux différents champs avec
 *   - "L->but"    :   but de la première arête
 *   - "L->poids"  :   poids de la première arête
 *   - "L->suivant :   suite de la liste
 *
 */
struct __arc {
 int poids ;  /* poids de l'arête en question */
 int but ;    /* sommet but de l'arête en question */
 struct __arc *suivant ;
} ;

typedef struct __arc *ListeAdj ;


/* prototype de la fonction "cons".
 * Pour faciliter l'insertion, on définit une fonction "cons" qui
 * rajoute une arête en tête de liste chainées. Elle prend en arguments
 * un poids "p" et un but "b" et renvoie une nouvelle liste d'adjacence.
 */
ListeAdj cons(int,int,const ListeAdj) ;


/* Le type des graphes en liste d'adjacences est maintenant simple à
 * définir : un graphes est une structure qui contient un entier "n"
 * (nombre de sommets) et un tableau de listes d'adjacences de longueur
 * "n".
 */
typedef struct {
 int nb_sommets ;
 ListeAdj *Adj ;
} *GrapheListe ;


/* prototype de la fonction de création d'un graphe en listes
 * d'ajacences.  On définit une fonction qui initialise un graphe vide.
 * Elle prend en argument le nombre de sommets du graphe voulu.
 */
GrapheListe grapheListeVide (int) ;


/* Le type des graphes en matrices d'adjacences... */
typedef struct {
 int nb_sommets ;
 int ** Matr ;
} *GrapheMatr ;


/* prototype de la fonction de création d'un graphe en matrice d'adjacence.
 * Une fonction qui initialise une matrice d'adjacence. ATTENTION, cette
 * fonction ne fait que créer la structure. La matrice est complêtement
 * arbitraire...
 */
GrapheMatr grapheMatrVide (int) ;


/* prototype de la fonction de lecture d'un graphe dans un fichier.
 * Une petite fonction qui permet de lire un graphe dans un fichier. La
 * première ligne du fichier devra comporter un entier "n" qui
 * représentera le nombre de sommets du graphe ; et chaque ligne
 * suivante sera de la forme "a p b" où a est l'origine d'un arc, b le
 * but de l'arc et p le poids de l'arc.
 * L'argument est le nom du fichier, et la valeur de retour un graphe
 * sous forme de liste d'adjacence.
 */
GrapheListe lireGrapheListe(const char*) ;


/* prototype de la fonction de génération aléatoire d'un graphe.  Une
 * petite fonction pour générer un graphe de manière aléatoire.  Cette
 * fonction prend en arguments le nombre de sommets (n), le nombre
 * d'arcs à générer (m), le poids maximum d'un arc (p) et un booléen
 * pour savoir si le graphe doit être orienté ou pas (o).
 */
GrapheListe grapheListeAleatoire(int,int,int,int) ;



/* ********************************************************************
 * ********************************************************************
 * ***** LE RESTE CONTIENT LES PROTOTYPES DES FONCTIONS QUE VOUS  *****
 * ***** DEVREZ DÉFINIR PENDANT LE TP...                          *****
 * ********************************************************************
 * ********************************************************************/



/* prototype de la fonction d'affichage */
void afficheGrapheListe (const GrapheListe) ;


/* protytpes des fonctions de conversion */
GrapheMatr listeVersMatrice(const GrapheListe) ;
GrapheListe matriceVersListe(const GrapheMatr) ;


/* prototype de la fonction qui renverse tous les arcs. */
GrapheListe transpose(const GrapheListe) ;


/* prototype de la fonction qui teste si un graphe est biparti */
int*biparti(const GrapheListe) ;


/* prototype de la fonction qui calcule les composantes fortement connexes */
int composantesFortemenentConnexes(const GrapheListe,int*) ;