////////////////////////////////////////////
    //
    // structure.h
    //
    // Structure de données pour stocker
    // un graphe en mémoire.
    //
    // Michaël ORTEGA & Nicolas DUMOULIN
    // Projet de Graphe - Mai 2001
    //
    ////////////////////////////////////////////


#include <iostream> 
#include <string> 
#include <sys\timeb.h> 

using namespace std; 

#ifndef visualcpp 
    #ifndef autres_compilos 
        #define visualcpp 
    #endif 
#endif 

#define infini 30000 

class list_sommet; 

/////////////////// classe sommet /////////////////////////////////

class sommet       
/* chaque sommet contient une liste de successeur et son numéro dans le graph.*/
{     
    unsigned int code;            //numéro du sommet
    list_sommet * succ;            //liste des successeurs

public: 
//constructeurs et destructeur
    sommet(){succ=NULL;} 
    sommet(unsigned int c):code(c) {succ=NULL;} 
    ~sommet(){ supprime_liste();} 
//suppression de la liste des successeurs de la mémoire
    void supprime_liste(); 
//ajout d'un successeur dans la liste du sommet
    void ajout_liste(sommet * s,const unsigned int p); 
//affichage du numéro du sommet ainsi que de ses successeurs
    void affiche() const; 
//renvoie si le sommet a pour successeur le sommet dont le numéro est passé en paramètre
    int a_pour_succ(const unsigned int c) const; 
//partage des données avec la classe graph
    friend class graph; 
}; 

/////////////////// classe list_sommet ////////////////////////////

class list_sommet 
/*chaque élément de la liste de sommet contient le poids de l'arc entre le sommet qui génère la liste et le sommet dont l'adresse est stockée dans l'attribut "contenu"*/
{ 
    int poids;                //poids de l'arc
    sommet * contenu;        //pointeur sur le sommet correspondant
    list_sommet * suivant;    //suivant dans la liste
public: 
//partage des données avec les classes graph et sommet
    friend class sommet; 
    friend class graph; 
}; 

/////////////////// classe graph //////////////////////////////////

class graph 
{ 
    unsigned int nbs;            //nombre de sommets du graph
    sommet * tabsommet;    //tableau de sommets du graph
public: 
//constructeurs et destructeur
    graph():nbs(0){} 
    graph(const unsigned int n) : nbs(n) { tabsommet = new sommet [n]; 
                            for (unsigned int i=0;i<n;i++) tabsommet[i].code=i;} 
    ~graph() { if (nbs>0) delete [] tabsommet; } 
//affichage du graphe : liste des sommets et de leurs successeurs
    void affiche() const; 
//formation d'un arc de poids p, du sommet d au sommet a
    void ajout_succ(const unsigned int d,const unsigned int a,const unsigned int p);  
//on test si S a tous ses sommets marqués
    int test(const unsigned int * s) const; 
//algorithme de Dijkstra
    graph * dijkstra(unsigned long int & temps) const; 
//chargement d'un garphe à partir d'un fichier
    void charger(); 
//enregistrement d'un graphe dans un fichier
    void enregistrer() const; 
//propose à l'utilisateur d'afficher en d'enregistrer un graphe
    void sortie_graphe(); 
//génération aléatoire de graphe ayant n sommets
    void hasard(const unsigned int n,const unsigned int proba); 
//verifie si un graphe est connexe en utilisant un parcours en largeur, et dans le cas échéant le rend connexe
//renvoie un si une correction a été apportée
    int connexe();
};