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

#include "structure.h" 

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

    //suppression de la liste des successeurs de la mémoire
void sommet::supprime_liste() 
/*suppression totale de la liste*/
{ 
    list_sommet * tmp; 
    while (succ!=NULL) { 
            tmp=succ->suivant; 
            delete succ; 
            succ=tmp; 
    } 
} 

    //ajout d'un successeur dans la liste du sommet
void sommet::ajout_liste(sommet * s,const unsigned int p) 
/*insertion en début de liste, c'est a dire entre le sommet générateur de la liste et la tête de liste*/
{ 
    list_sommet * nouveau=new list_sommet; 
    nouveau->poids=p; 
    nouveau->contenu=s; 
    nouveau->suivant=succ; 
    succ=nouveau; 
} 

    //affichage du numéro du sommet ainsi que de ses successeurs
void sommet::affiche() const 
{ 
    list_sommet * courant=succ; 
    cout<<"Liste des successeurs de "<<code<<" : "<<endl; 
    while (courant != NULL) 
    { 
        cout<<" sommet : "<<courant->contenu->code<<" poids de l'arc : "<<courant->poids<<endl; 
        courant=courant->suivant; 
    } 
} 

    //renvoie si le sommet a pour successeur le sommet dont le numéro est passé en paramètre
int sommet::a_pour_succ(const unsigned int c) const 
{ 
    list_sommet * courant=succ; 
     
    while (courant!=NULL) 
    { 
        if (courant->contenu->code==c) return (courant->poids); 
        courant=courant->suivant; 
    } 
    return -1;    //le sommet n'était pas dans la liste de successeurs
} 

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

    //affichage du graphe : liste des sommets et de leurs successeurs
void graph::affiche() const 
{ 
    cout<<"affichage du graphe :"<<endl; 
    for (unsigned int i=0;i<nbs;i++) tabsommet[i].affiche(); 
} 

    //formation d'un arc de poids p, du sommet d au sommet a
void graph::ajout_succ(const unsigned int d,const unsigned int a,const unsigned int p) 
{ 
    tabsommet[d].ajout_liste(tabsommet+a,p); 
} 


    //on test si S a tous ses sommets marqués
int graph::test(const unsigned int * s) const 
{ 
    for (unsigned int i=0;i<nbs;i++)  
        if (s[i]==0) return 1; 
    return 0; 
} 

    //algorithme de Dijkstra
graph * graph::dijkstra(unsigned long int & temps) const 
{ 
    unsigned int progression=0;                    //indicateur de progression de l'algo
    cout<<".";                                            //affichage du début de la progression
    unsigned int * S = new unsigned int [nbs]; 
    unsigned int * Pi = new unsigned int [nbs]; 
    unsigned int xpivot=0;                        //initialisation de xpivot au premier sommet
    graph * resultat = new graph(nbs);    //allocation mémoire du graphe resultant
    list_sommet * courant;                //pour parcourir la liste des successeurs de xpivot
     
    struct timeb deb,fin; 

    ftime(&deb);        //debut du "chronomètrage"
     
    for (unsigned int i=0;i<nbs;i++) S[i]=0;    //initialisation du tableau (aucun des sommets n'est marqué)
#ifdef visualcpp 
    for (i=0;i<nbs;i++) Pi[i]=infini;    //initialisation de pi pour chaque sommet
#else 
    for (unsigned int i=0;i<nbs;i++) Pi[i]=infini;    //initialisation de pi pour chaque sommet
#endif     
    //marquage du premier sommet
    S[0]=1;     
    Pi[0]=0; 

    while ( test(S) && (Pi[xpivot]<infini) ) 
    { 
        courant=tabsommet[xpivot].succ; 
        unsigned int x; 
        while (courant!=NULL) 
        { 
            x=courant->contenu->code; 
            if ( Pi[x] > (Pi[xpivot] + courant->poids) ) 
                Pi[x] = Pi[xpivot] + courant->poids; 
            courant=courant->suivant; 
        } 
        //recherche du Pi minimum parmis les sommets non marqués
        unsigned int min=infini; 
        for (unsigned int i=0;i<nbs;i++) if (S[i]==0) if (Pi[i]<min) {min=Pi[i];xpivot=i;} 
        //on a trouvé notre xpivot
        S[xpivot]=1; 
        //affichage de la progression : 10 points affichés= progression terminée
        progression++; 
        if (progression%((nbs+11)10)==0) cout<<"."; 
        //on a mis nbs+11 car si on a moins de 10 sommet ça plante!
#ifdef visualcpp 
        for (i=0;i<nbs;i++) if (S[i]==1) 
#else 
        for (unsigned int i=0;i<nbs;i++) if (S[i]==1) 
#endif     
        { 
            courant=tabsommet[i].succ; 
            while ((courant!=NULL) && (courant->contenu->code != xpivot)) 
                //tant que l'on est pas à la fin de la liste des successeurs du sommet i
                // et que le successeur courant n'est pas xpivot faire
                courant=courant->suivant; 
            if (courant!=NULL) 
                if (Pi[xpivot]==(Pi[i] + courant->poids)) 
                { 
                    resultat->ajout_succ(i,xpivot,courant->poids); 
                    i=nbs; 
            } 
        } 
         
    } 
    ftime(&fin);        //fin du "chronomètrage"
    temps=(fin.time-deb.time)*1000+fin.millitm-deb.millitm; 
    return resultat; 
} 

#include <fstream> 

    //chargement d'un garphe à partir d'un fichier
void graph::charger() 
{ 
    int tmp; 
    char tmpc[20]; 
    char nom_fichier[256]; 

    cout<<" Veuillez saisir le nom du fichier : "; 
    cin>>nom_fichier; 
     
    ifstream fich(nom_fichier); 
    fich>>nbs; 
    tabsommet = new sommet [nbs]; 
    for (unsigned int i=0;i<nbs;i++)  
    { 
        fich>>tmpc; //pour les sauts de lignes des séparations de chaque sommet dans le fichier
        tabsommet[i].code=i; 
        for (unsigned int j=0;j<nbs;j++) 
        { 
            fich>>tmp; 
            if (tmp!=-1) ajout_succ(i,j,tmp); 
        } 
         
    } 
    fich.close(); 
} 

    //enregistrement d'un graphe dans un fichier
void graph::enregistrer() const 
{ 
    int choix=0;         
    if (nbs>20) 
    { 
        cout<<"Attention, votre graphe est volumineux, l'enregistrer dans un fichier risque de prendre du temps !"<<endl; 
        cout<<"  de plus la lecture de ce fichier sera tres fastidieuse"<<endl<<endl; 
        cout<<"              Voulez-vous tout de même "; 
        if (nbs>200) cout<<"prendre un cafe et "; 
        cout<<"lancer l'enregistrement : Oui (tapez 0)  Non (tapez 1)"<<endl<<endl<<"  ? -> "; 
        cin>>choix; 
    } 
    if (!choix) 
    { 
        char nom_fichier[256]; 

        cout<<" Veuillez saisir le nom du fichier : "; 
        cin>>nom_fichier; 
         
        ofstream fich(nom_fichier); 
        fich<<nbs<<endl; 
        for (unsigned int i=0;i<nbs;i++) 
        { 
            fich<<"******"<<endl;    //ligne de séparation pour augmenter la lisibilité
            for (unsigned int j=0;j<nbs;j++) fich<<tabsommet[i].a_pour_succ(j)<<endl; 
        } 
    } 
} 

    //propose à l'utilisateur d'afficher en d'enregistrer un graphe
void graph::sortie_graphe() 
{ 
    int choix_menu; 

    cout<<"  Voulez-vous : 1 -> afficher ce graphe"<<endl; 
    cout<<"                2 -> sauver ce graphe dans un fichier"<<endl; 
    cout<<"                3 -> passer a la suite"<<endl<<endl; 
    cout<<"                ? -> "; 
    cin>>choix_menu; 
    cout<<endl<<endl; 
    if (choix_menu==1) this->affiche(); 
    else if (choix_menu==2) enregistrer(); 
} 

    //génération aléatoire de graphe ayant n sommets
void graph::hasard(const unsigned int n, const unsigned int proba) 
{ 
    unsigned int progression=0;                    //indicateur de progression
    cout<<".";                            //affichage du début de la progression
    nbs=n; 
    tabsommet = new sommet [nbs]; 
    for (unsigned int i=0;i<nbs;i++)  
    { 
        tabsommet[i].code=i; 
        //affichage de la progression : 10 points affichés= progression terminée
        progression++; 
        if (progression%((nbs+11)10)==0) cout<<"."; 
        //on a mis nbs+11 car si on a moins de 10 sommet ça plante!
        //attribution des successeurs
        for (unsigned int j=0;j<nbs;j++) 
        { 
            if (i!=j) 
            { 
                int p=rand() % 100; 
                if (p<proba) 
                { 
                    p=rand()%10+1; 
                    ajout_succ(i,j,p); 
                } 
            } 
        } 
    } 
    cout<<endl<<endl<<"        generation terminee"<<endl<<endl;
    cout<<" Verification de la connexite du graphe genere : ..."<<endl<<endl;
    connexe();
    cout<<"        Verification et eventuelles corrections effectuees."<<endl<<endl<<endl;
} 


//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 graph::connexe()
{
    int resultat=1;            //valeur de retour
    unsigned int * S = new unsigned int [nbs];    //tableau des sommets marqués
    unsigned int * F = new unsigned int [nbs+1];    //File
    list_sommet * courant;        //pour parcourir la liste des successeurs de xpivot
    unsigned int xpivot=0,tete=0,queue=0;        //sommet en cours de traitement, tête et queue de la file
    
    for (unsigned int i=0;i<nbs;i++) S[i]=0;    //initialisation du tableau (aucun des sommets n'est marqué)
    F[tete]=0;                                    //marquage de la racine
    while (tete<=queue)
    {
        xpivot=F[tete];
        //parcours de la liste des successeurs de xpivot
        courant=tabsommet[xpivot].succ;
        while (courant!=NULL)        
        {
            if (!S[courant->contenu->code])
            {
                S[courant->contenu->code]=S[xpivot]+1;
                queue++;
                F[queue]=courant->contenu->code;
            }
            courant=courant->suivant;
        }
        tete++;
    }
    //fin du marquage
    delete [] F;
    //on teste maintenant si des sommets ne sont pas marqués, auquel cas le graphe n'est
    //pas connexe. On ajoute alors un arête pour le connecter au reste du graphe
#ifdef visualcpp
    for (i=1;i<nbs;i++)
#else
    for (unsigned int i=1;i<nbs;i++)
#endif
    if ( (!S[i])&&(tabsommet[i-1].a_pour_succ(i)==-1) ) 
    {
        ajout_succ(i-1,i,rand()%10+1);
        resultat=0;
    }
    //si on a un sommet isolé, on rajoute un arc entre le sommet le précédent (dans la numérotation)
    //en vérifiant qu'ils ne sont pas déjà liés : en effet ces deux sommets n'étaient peut-être
    //pas connectés au reste du graphe, mais son prédecesseur a déjà subit le test et est donc
    // désormais connecté au reste du graphe, le sommet courant l'est donc aussi ...
    return resultat;
}