#include "Wakim Odier tp2.h"

//Fonction initialisation à faire.
/** Fonction */
/** Entrées :
int i (valeur à placer dans value)
list_Node* l (maillon précédent, NULL si inexistant)    */
/** Sortie : list_Node* (Pointeur vers le nouveau maillon)  */
/** Utilité : Crée un maillon de type list_Node pour une liste chainée  */
list_Node* new_Node(int i, list_Node* l)
{
    list_Node* lnew = (list_Node*) malloc(sizeof(list_Node)); // allocation de l'espace
    lnew->value = i; //initialisation des variables
    lnew->next = NULL;
    lnew->arc = NULL;
    if(!l) // vérification du prev
    {
        return lnew;
    }
    else
    {
        l->next = lnew;
    }
    return lnew;
}

/** Fonction */
/** Entrées :
int nbS (Permet de savoir combien d'éléments nous devons avoir dans notre liste chainée)*/
/** Sortie : list_Node* un pointeur vers la tête de la chaine*/
/** Utilité : Crée une liste chainée de nbS élèments facilement*/
list_Node* cree_list(int nbS)
{
    list_Node *lhead;
    if(nbS <= 0) return NULL; // vérification des entrées
    else
    {
        list_Node *l;
        lhead = l = new_Node(0, NULL);
        for(int i=1; i<nbS; i++) // boucle de création pour la chaine
        {
            l = new_Node(i, l); // crée et chaine
        }
    }
    return lhead;
}

/** Fonction */
/** Entrées :
list_Node* l (un pointeur vers la tête de la liste qu'on veut supprimer)*/
/** Sortie : void*/
/** Utilité : Libère l'espace mémoire occupé par une chaine*/
void free_list(list_Node* l)
{
     //cout << "0" << endl;
     if(!l) return;
     //cout <<"1" << endl;
     if(l->next) free_list(l->next);// récursivité sur next
     if(l->arc) free_list(l->arc);// récursivité sur arc
     free(l);// libération d'un élèment
     l = NULL;
     return;
}

/** Fonction */
/** Entrées :
list_Node* G (la chaine dans laquelle on cherche un élèment)
int ext (valeur que l'on cherche) */
/** Sortie : list_Node* l'élèment que l'on cherchait*/
/** Utilité : rechercher un élèment en particulier dans une chaine*/
list_Node* recherche(list_Node* G, int ext)
{
    list_Node *l = G;
    if(!G || ext<0) return NULL; // vérification des entrées
    else
    {
        while(l && l->value != ext) // parcourt la liste à la recherche de notre valeur
        {
            l = l->next;
        }
    }
    return l;
}

/** Fonction */
/** Entrées :
list_Node* l élèment auquel on veut ajouter un arc
int ext (une des valeurs pour l'arc)
int val (la seconde valeur pour l'arc)*/
/** Sortie : bool (retourne false si il y a une erreur) */
/** Utilité : crée un arc*/
bool add_arc(list_Node* l, int ext, int val)
{
    if(!l || ext<0) return false;// vérification des entrées
    else
    {
        list_Node* ltemp = l;
        while(ltemp->arc) // boucle pour se placer correctement
        {
            ltemp = ltemp->arc;
        }
        ltemp->arc = new_Node(ext, NULL); // création de l'arc
        ltemp->arc->next = new_Node(val, NULL); // création de l'arc
    }
    return true;
}

/** Fonction */
/** Entrées :
string nom (fichier contenant le graph)*/
/** Sortie : list_Node* un pointeur vers la SDD contenant les données*/
/** Utilité : lire un graph dans le mode succ*/
list_Node* lecture_graphe_succ (string nom)
{
    list_Node* G;
    ifstream fichier(nom.c_str(), ios::in); // ouverture du fichier
    if(fichier) // si on ouvre correctement
    {
        int nbSommets, extremiteI, extremiteT, valeurArc;
        list_Node* l;
        fichier >> nbSommets;
        G = cree_list(nbSommets); // création de la liste qui contient notre graphe
        fichier >> extremiteI;
        while(extremiteI != -1) // permet de lire tout le fichier
        {
            fichier >> extremiteT;
            fichier >> valeurArc;

            if(!(l = recherche(G,extremiteI))) return false; // on stocke dans la SDD

            if(!(add_arc(l,extremiteT, valeurArc))) return false; // on stocke dans la SDD


            fichier >> extremiteI;
        }
    }
    else // pas de fichier, pas de lecture
    {
        return NULL;
    }
    return G;
}

/** Fonction */
/** Entrées :
string nom (nom du fichier contenant le graph)*/
/** Sortie : list_Node* un pointeur vers la SDD contenant les données*/
/** Utilité : lire un grap dans le mode prev*/
list_Node* lecture_graphe_prev (string nom)
{
    list_Node* G;
    ifstream fichier(nom.c_str(), ios::in);
    if(fichier)
    {
        int nbSommets, extremiteI, extremiteT, valeurArc;
        list_Node* l;
        fichier >> nbSommets;
        G = cree_list(nbSommets); // création de la chaine contenant le graph

        fichier >> extremiteI;
        while(extremiteI != -1) // permet de lire tout le fichier
        {
            fichier >> extremiteT;
            fichier >> valeurArc;

            if(!(l = recherche(G,extremiteT))) return false; // on stocke dans la SDD
            if(!add_arc(l,extremiteI, valeurArc)) return false; // on stocke dans la SDD

            fichier >> extremiteI;
        }
    }
    else
    {
        return NULL;
    }
    return G;
}

/** Fonction */
/** Entrées :
list_Node* G (la SDD contenant un graphe) */
/** Sortie : void */
/** Utilité : affiche un graphe, permet la vérification de la lecture facilement*/
void aff_graphe(list_Node* G)
{
    if(!G) return;

    list_Node* l = G;
    list_Node* larc;
    while(l) // permet de parcourir toute la liste
    {
        printf("Sommet : %d \n", l->value);
        larc = l;
        while(larc->arc) // affichage de tous les arcs
        {
            larc = larc->arc;
            printf(" %d %d %d \n", l->value, larc->value, larc->next->value);
        }

        l = l->next;
    }
}
/** Fonction */
/** Entrées :
list_Node* Ghead (la SDD des résultats de belleman dans laquel on copie)
list_Nade* lhead (la SDD des résultats de bellman qu'on veut copier)*/
/** Sortie : void*/
/** Utilité : affiche et sauvegarde une SDD Bellman*/
list_Node* lbell_equal(list_Node* lhead, list_Node* Ghead)
{
    if(!lhead) return NULL;
    list_Node* l = lhead;
    list_Node* G = Ghead;
    list_Node* tp;
    int nbS = 1;
    while(l->next)
        {
            nbS++;
            l = l->next;
        }
    l = lhead;
    G =  cree_list(nbS);
    tp = G;
    while(l) // fin de l'initialisation de la SDD
        {
            if(!(add_arc(G, 0, 0))) return NULL; //ajout des arcs (ici le couple longueur, pivot)
            G = G->next;
            l = l->next;

        }
    G = tp;
    l = lhead;
    while(l)
    {
        G->value = l->value;
        G->arc->value = l->arc->value;
        G->arc->next->value = l->arc->next->value;
        G = G->next;
        l = l->next;
    }
    return tp;
}
/**------------- BELLMAN -----------*/

/** Fonction */
/** Entrées :
list_Node* G (le graphe)
int source (le sommet de départ pour l'algorithme)
string name (nom du fichier pour la sauvegarde)*/
/** Sortie : void */
/** Utilité : copie*/
list_Node* bellman(list_Node* G, int source, string name)
{
    list_Node* l = G;
    list_Node* lbellhead;
    if(!G || source <0) // vérification des entrées
    {
        return NULL;
    }
    else
    {
        int nbS=1, somme=1;
        list_Node* lbell;
        list_Node* lbelltemp;
        bool test = true;
        while(l->next)
        {
            nbS++;
            l = l->next;
        }
        if(source > nbS-1 || source < 0) return NULL; // vérification de la variable source
        lbellhead =  cree_list(nbS);
        lbelltemp = lbell = lbellhead;

        lbell = G;
        while(lbell) // calcule du max pour avoir une valeur d'infini, on ajoutes toutes les valeurs positives des arcs + 1 pour être sûr qu'on ne peut pas avoir un trajet plus long
        {
            lbelltemp = lbell;
            while(lbelltemp->arc)
            {
                if (lbelltemp->arc->next->value >= 0)
                {
                    somme = somme + lbelltemp->arc->next->value;
                }
                lbelltemp = lbelltemp->arc;
            }
            lbell = lbell->next;
        }

        lbell = lbellhead;
        while(lbell) // fin de l'initialisation de la SDD
        {
            if(!(add_arc(lbell, somme, source))) return NULL; //ajout des arcs (ici le couple longueur, pivot)
            lbell = lbell->next;
        }
        lbell = lbellhead;
        lbell = recherche(lbellhead, source);
        lbell->arc->value = 0; // initialisation très importante du trajet le plus court pour notre point de départ
        list_Node* resultat = NULL; // pour stocker le résultat de l'étape précédente
        list_Node* tp; // tête de la chaine contenant le résultat de l'étape précèdente
        for(int i=0 ; i<nbS && test == true; i++) // boucle de l'algorithme de Bellman
        {
            lbell = lbellhead;
            free_list(resultat);
            tp = resultat = lbell_equal(lbell, resultat);// permet de ne pas utiliser les résultat de l'étape en court pour cette même étape
            test = false;
            while(resultat) // parcourt la totalité de la SDD contenant Bellman
            {
                lbelltemp = recherche(G, resultat->value); //on récupère les arcs ayant pour arrivée le point pour lequel on veut calculer le trajet le ^plus court
                while(lbelltemp->arc) // permet de parcourir toutes les possibilités
                {
                    l = recherche(tp, lbelltemp->arc->value); // on se place pour avoir les valeur de Pi de l'occurence précèdente
                    if(resultat->arc->value > l->arc->value + lbelltemp->arc->next->value && l->arc->value!=somme) // si on trouve un trajet plus court
                    {
                        lbell = recherche(lbellhead, resultat->value); // on se positionne
                        lbell->arc->value = l->arc->value + lbelltemp->arc->next->value; // mise à jour de la longueur
                        lbell->arc->next->value = lbelltemp->arc->value; // mise à jour du pivot
                        test = true; // permet de savoir si on a eu une modification ou non, permet de stopper bellman avant sa fin théorique maximale
                    }
                    lbelltemp = lbelltemp->arc;
                }
                resultat = resultat->next;
            }
            //aff_bellman(lbellhead, i, somme, name); // Sauvegarde de l'étape
        }
        free_list(resultat);
        free_list(tp);
    }
    return lbellhead;
}

/** Fonction */
/** Entrées :
list_Node* G (la SDD des résultats de belleman)
int step (numéro de l'étape)
int somme (trajet max = infinity)
string name (nom du fichier pour la sauvegarde)*/
/** Sortie : void*/
/** Utilité : affiche et sauvegarde une SDD Bellman*/
void aff_bellman(list_Node* G, int step, int somme, string name)
{
    if(!G) return;
    name = name + "R.txt"; // le nom du fichier de sauvegarde
    ofstream fichier(name.c_str(), ios::app); // le fichier
    if(fichier)
    {
        list_Node* l = G;
        fichier << "step : " << step << endl; // écriture
        printf("step : %d \n", step);
        while(l) // permet le parcours de la totalité de la SDD de bellman
        {
            if(l->arc->value == somme)
            {
                fichier << "Pi(" << l->value << ") : (infinity, " << l->arc->next->value << ") " << endl; // écriture
                printf("Pi(%d) : (infinity, %d) \n", l->value, l->arc->next->value);
            }
            else
            {
                fichier << "Pi(" << l->value << ") : (" << l->arc->value << ", " << l->arc->next->value << ") " << endl; // écriture
                printf("Pi(%d) : (%d, %d) \n", l->value, l->arc->value, l->arc->next->value);
            }

            l = l->next;
        }
    }
    else return; // pas de fichier pas de résultat !
}



/** ----------------------------------------------- FONCTIONS TP2 ---------------------------------------------------------------------*/

/** Fonction */
/** Entrées :
string name (nom du fichier)*/
/** Sortie : void*/
/** Utilité : affiche et sauvegarde un graphe non-orienté*/
list_Node* lecture_graphe (string nom)
{
    list_Node* G;
    ifstream fichier(nom.c_str(), ios::in); // ouverture du fichier
    if(fichier) // si on ouvre correctement
    {
        int nbSommets, extremiteI, extremiteT, valeurArc;
        list_Node* l;
        fichier >> nbSommets;
        G = cree_list(nbSommets); // création de la liste qui contient notre graphe
        fichier >> extremiteI;
        while(extremiteI != -1) // permet de lire tout le fichier
        {
            fichier >> extremiteT;
            fichier >> valeurArc;

            if(!(l = recherche(G,extremiteI))) return false; // on stocke dans la SDD

            if(!(add_arc(l,extremiteT, valeurArc))) return false; // on stocke dans la SDD

            // On cree l'arc de retour
            if(!(l = recherche(G,extremiteT))) return false;  // on se place au sommet et stockage
            if(!(add_arc(l,extremiteI,valeurArc))) return false; // ajout de l'arc et stockage

            fichier >> extremiteI;
        }
    }
    else // pas de fichier, pas de lecture
    {
        return NULL;
    }
    return G;
}

/** Fonction */
/** Entrées :
list_Node*G (notre graphe) */
/** Sortie : Bool (1 si vrai, 0 si faux)*/
/** Utilité : vérifie si le graphe est connexe*/
bool if_connexe (list_Node *G, string name)
{
    if(!G) return false; // on vérifie l'existance G
    list_Node *lhead = G;
    list_Node *l = lhead;
    list_Node *lrslthead, *lrslt, *ltemp;
    int somme = 1;

    l = lhead;

    while(l) // calcule du max pour avoir une valeur d'infini, on ajoutes toutes les valeurs positives des arcs + 1 pour être sûr qu'on ne peut pas avoir un trajet plus long
    {
        ltemp = l;
        while(ltemp->arc)
        {
            if (ltemp->arc->next->value >= 0)
            {
                somme = somme + ltemp->arc->next->value;
            }
            ltemp = ltemp->arc;
        }
        l = l->next;
    }

    l = lhead;
    while(l)  // parcours du graphe
    {
        lrslthead = lrslt = bellman(lhead, l->value, "resultat"); // On récupère le résultat de Bellman pour le sommet l->value

        resultat_tp2(lrslthead, name, 1);
        while(lrslt)  // On parcourt la structure de Bellman
        {
            if(lrslt->arc->value == somme)     // Si on a un trajet infini, le graphe n'est pas connexe alors on return false.
            {
                return false;
            }
            lrslt = lrslt->next;
        }
        l = l->next;
        free_list(lrslthead);   // Libération mémoire
    }
    return true;
}

/** Fonction */
/** Entrées :
list_Node*G (une liste_Node qu'on va copier)
/** Sortie : list_Node* (la liste copiée)*/
/** Utilité : Copie une liste*/
list_Node* copie_liste (list_Node* G)
{
    if(!G) return NULL; // On vérifie l'existance de G, il s'agit de notre condition d'arrêt
    list_Node *l;

    l = new_Node(G->value, NULL);
    l->next = copie_liste(G->next); // Fonction récursive
    l->arc = copie_liste(G->arc);
    return l;
}


/** Fonction */
/** Entrées :
list_Node* G (une liste_Node qu'on va copier)
/** Sortie : Bool (1 si vrai, 0 si faux)*/
/** Utilité : Vérifie la présence d'un circuit*/
bool circuit_graphe (list_Node *G, string name)
{
    if(!G)
    {
        cout << "erreur" << endl;
        return false ;
    }
    list_Node *l, *lhead;
    l = copie_liste(G);
    lhead = l;
    while(l)
    {
        if(l->arc && l->arc->arc)    // On vérifie si le sommet a au moins 2 sommets
        {
            l = l->next;
        }
        else                // Le sommet n'a qu'un sommet
        {
            resultat_tp2(l, name, 0);
            lhead = supp_sommet(lhead, l);  // On supprime ce sommet
            l = lhead;
        }
    }

    if(!lhead) return false;
    else return true;
}

/** Fonction */
/** Entrées :
list_Node* G (la liste)
list_Node * S (le sommet à supprimer)
/** Sortie : list_Node (la nouvelle tête)*/
/** Utilité : supprimer un sommet*/
list_Node* supp_sommet (list_Node *G, list_Node *S)
{
    if(!G || !S) return NULL ;
    list_Node *lhead, *l, *lprev, *ltemp;
    lhead = G;
    int val = S->value;

    l = lhead;
    lprev = NULL;
    while(l)    // Parcours des next
    {
        if(l->value == val)    // Si le sommet qu'on veut supprimer existe
        {
            if(!lprev)      // Cas où on spprime la tête
            {
                G = lhead = l->next;    // On définit la nouvelle tête
                l->next = NULL;
                free_list(l);
                l = NULL;
            }
            else
            {
                lprev->next = l->next;
                l->next = NULL;
                free_list(l);
                l = NULL;
            }
        }
        else   // Sinon on décale
        {
            lprev = l;
            l = l->next;
        }
    }
    //aff_graphe(G);
    l = lhead;
    lprev = NULL;
    //PARCOURS DES ARCS
    while(l)    //parcours des next
    {
        ltemp = l;
        while(ltemp)    //parcours des arcs
        {
            if(ltemp->value == val) // Sommet qu'on veut supprimer trouvé
            {
                lprev->arc = ltemp->arc;
                ltemp->arc = NULL;
                free_list(ltemp);
                ltemp = NULL;
            }
             else    // On décale si la valeur n'a pas été trouvée
            {
                lprev = ltemp;
                ltemp = ltemp->arc;
            }
        }
        l = l->next;
    }
    G = lhead;
    //aff_graphe(G);
    return G;
}

/** Fonction */
/** Entrées :
list_Node* G (la liste)
string (le nom du fichier
/** Sortie : void*/
/** Utilité : affiche et sauvegarde le resultat*/
void resultat_tp2(list_Node* G, string name, bool type)
{
    if(!G) return;
    //name = name + "R.txt"; // le nom du fichier de sauvegarde
    ofstream fichier((name + "R.txt").c_str(), ios::app); // le fichier
    if(fichier)
    {

        if(type == 0)
        {

            fichier << "Le sommet : " << G->value << "est supprimé" << endl;
        }
        else
        {
            int somme=1;
            list_Node *l = G, *ltemp;
            while(l) // calcule du max pour avoir une valeur d'infini, on ajoutes toutes les valeurs positives des arcs + 1 pour être sûr qu'on ne peut pas avoir un trajet plus long
            {
                ltemp = l;
                while(ltemp->arc)
                {
                    if (ltemp->arc->next->value >= 0)
                    {
                        somme = somme + ltemp->arc->next->value;
                    }
                    ltemp = ltemp->arc;
                }
                l = l->next;
            }
            fichier << "résultat de bellman permettant de savoir si on peut aller vers tous les points : " << endl; // écriture
            l = G;
            while(l) // permet le parcours de la totalité de la SDD de bellman
            {
                if(l->arc->value == somme)
                {
                    fichier << "Pi(" << l->value << ") : (infinity, " << l->arc->next->value << ") " << endl; // écriture
                }
                else
                {
                    fichier << "Pi(" << l->value << ") : (" << l->arc->value << ", " << l->arc->next->value << ") " << endl; // écriture
                }
                l = l->next;
            }
        }
        fichier.close();
    }
    else return; // pas de fichier pas de résultat !
}