#include "Flots.h"


bool lirefichierArc(vector<arc> &lesArcs,string &entree, string &sortie)
{
        ifstream fichier("exprof3.txt", ios::in);  // on ouvre le fichier en lecture
        arc unArc;
        unArc.sature = false;
        unArc.bloque = false;
        unArc.null = false;
        string capacite;
        unsigned i;

        if(fichier)  // si l'ouverture a réussi
        {
                string ligne;
                //lecture de l'entrée et de la sotie
                getline(fichier, ligne);

                i=0;
                while(ligne[i]!=9)
                {
                    entree = entree + ligne[i];
                    i++;
                }
                i++;
                while(ligne[i]!=9 && i < ligne.size())
                {
                    sortie = sortie + ligne[i];
                    i++;
                }

                unArc.flot = 0;

                while(getline(fichier, ligne))  // tant que l'on peut mettre la ligne dans "contenu"
                {
                        i=0;
                        while(ligne[i]!=9)
                        {
                            unArc.villeDep = unArc.villeDep + ligne[i];
                            i++;
                        }
                        i++;
                        while(ligne[i]!=9)
                        {
                            unArc.villeDest = unArc.villeDest + ligne[i];
                            i++;
                        }
                        i++;
                        while(ligne[i]!=9 && i < ligne.size())
                        {
                            capacite = capacite+ligne[i];
                            i++;
                        }

                        unArc.capa = unArc.capacite = atoi(capacite.c_str());
                        lesArcs.push_back(unArc);
                        capacite.clear();
                        unArc.villeDep.clear();
                        unArc.villeDest.clear();
              }
              fichier.close();  // on ferme le fichier
              return true;
        }
        else  // sinon
                cerr << "Impossible d'ouvrir le fichier !" << endl;

        return false;
}

void afficheArc(arc arc)
{
    cout << arc.villeDep << "-----["<< arc.capacite <<"]-"<< arc.flot <<"---->" << arc.villeDest;
    if(arc.sature == true) cout <<" sature";
    else if(arc.bloque == true) cout <<" bloque";
     cout << endl;
}

void afficheLesArcs(vector<arc> lesArcs)
{

    for(unsigned i = 0; i < lesArcs.size(); i++)
    {

        afficheArc(lesArcs[i]);
    }
    cout << endl;
}


arc arcNsMaxCapacite(vector<arc> lesArcs)
{
    int capaciteMax = 0;
    arc arcCapaciteMax;

    for(unsigned i=0; i<lesArcs.size();i++)
    {
        if(lesArcs[i].sature == false   && lesArcs[i].bloque == false)
        {
            if(lesArcs[i].capacite > capaciteMax)
            {
                capaciteMax = lesArcs[i].capacite;
                arcCapaciteMax = lesArcs[i];
            }
        }

    }
    return arcCapaciteMax;
}


arc arcNsMinCapacite(vector<arc> lesArcs)
{
    arc arcCapaciteMin = arcNsMaxCapacite(lesArcs);
    int capaciteMin = arcCapaciteMin.capacite;

        for(unsigned i=0; i<lesArcs.size();i++)
        {
            if(lesArcs[i].sature == false && lesArcs[i].bloque == false )
            {
                if(lesArcs[i].capacite < capaciteMin)
                {
                    capaciteMin = lesArcs[i].capacite;
                    arcCapaciteMin = lesArcs[i];
                }
            }
        }

    return arcCapaciteMin;
}

bool estPraticable(vector<arc> lesArcs)
{
    bool praticable = false;
    unsigned i = 0;

    while(praticable == false && i <lesArcs.size())
    {
        if(lesArcs[i].bloque == false && lesArcs[i].sature == false)praticable = true;
        i++;
    }

    return praticable;
}

void augmentationFlot(vector<arc> chemin, vector<arc> &lesArcs, int augmentation,vector< vector<arc> > &histoChemins)
{

        histoChemins.push_back(chemin);
        cout<<"Nouveau chemin etudie: "<<endl;
        afficheLesArcs(chemin);
        for(unsigned i=0; i<chemin.size();i++)
        {
            for(unsigned j=0; j<lesArcs.size();j++)
            {
                if(chemin[i].villeDep.compare(lesArcs[j].villeDep) == 0 && chemin[i].villeDest.compare(lesArcs[j].villeDest)==0)
                {

                    lesArcs[j].flot = lesArcs[j].flot+augmentation;
                    lesArcs[j].capacite = lesArcs[j].capacite-augmentation;


                    if( lesArcs[j].capacite == 0)
                    {
                        cout << "L'arc ";
                        afficheArc(lesArcs[j]);
                        cout << " est sature"<<endl<<endl;
                        lesArcs[j].sature = true;
                    }
                }

            }
        }

}

arc arcNsSuivant(arc unArc, vector<arc> lesArcs)
{
    arc arcSuivant;
    for(unsigned i=0; i<lesArcs.size();i++)
    {
        if(unArc.villeDest.compare(lesArcs[i].villeDep) == 0)
        {
            if(lesArcs[i].sature == false && lesArcs[i].bloque == false )return lesArcs[i];
        }
    }
    //sinon on retourne un arc null
    arcSuivant.null = true;
    return arcSuivant;
}

arc arcNsPrecedent(arc unArc, vector<arc> lesArcs)
{
    arc arcPrecedent;
    for(unsigned i=0; i<lesArcs.size();i++)
    {
        if(unArc.villeDep.compare(lesArcs[i].villeDest)== 0)
        {
            if(lesArcs[i].sature == false && lesArcs[i].bloque == false )return lesArcs[i];
        }
    }
    //sinon on retourne un arc null
    arcPrecedent.null = true;
    return arcPrecedent;
}

vector<arc> chercheChemin(arc arcCapaciteMin, vector<arc> &lesArcs, string entree, string sortie)
{
    vector<arc> chemin;
    arc arcAAjouter;
    bool circuit;

    do{

        circuit = false;
        arcAAjouter = arcCapaciteMin;
        chemin.push_back(arcAAjouter);

        while(arcAAjouter.villeDep.compare(entree) != 0 && circuit == false)
        {

            arcAAjouter = arcNsPrecedent(arcAAjouter,lesArcs);
            if(contientSommet(chemin,arcAAjouter.villeDep)== false)
            {
                chemin.insert(chemin.begin(),arcAAjouter);
            }
            else
            {
                circuit = true;
                metArcMinNull(lesArcs,chemin,arcAAjouter.villeDep);
            }

        }

        arcAAjouter = arcCapaciteMin;

        while(arcAAjouter.villeDest.compare(sortie) != 0 && circuit == false)
        {
            arcAAjouter = arcNsSuivant(arcAAjouter,lesArcs);

            if(contientSommet(chemin,arcAAjouter.villeDep)== false)
            {
                chemin.push_back(arcAAjouter);
            }
            else
            {
                circuit = true;
                metArcMinNull(lesArcs,chemin,arcAAjouter.villeDep);
            }
        }

        if(circuit == true)
        {
            cout << "Le chemin contenant le circuit est :" << endl;
            afficheLesArcs(chemin);
            chemin.clear();
        }


    }while(circuit == true);

    return chemin;
}

void chercheBlocage(vector<arc> &lesArcs,string entree, string sortie)
{
    bool blocage = true;
        while(blocage == true)
        {
            blocage = false;

            for(unsigned i=0; i<lesArcs.size();i++)
            {
                if(arcNsPrecedent(lesArcs[i],lesArcs).null == true)
                {
                    if(lesArcs[i].villeDep.compare(entree) != 0 )
                    {
                        if(lesArcs[i].bloque != true)
                        {
                            blocage = true;
                            lesArcs[i].bloque = true;
                        }

                    }
                }

                if(arcNsSuivant(lesArcs[i],lesArcs).null == true)
                {
                    if(lesArcs[i].villeDest.compare(sortie) != 0 )
                    {
                        if(lesArcs[i].bloque != true)
                        {
                            blocage = true;
                            lesArcs[i].bloque = true;
                        }
                    }
                }

            }
        }


}

int bloch(vector<arc> &lesArcs, string entree, string sortie,vector< vector<arc> >&trace,vector< vector<arc> > &histoChemins,vector<int> &lesAugmentationsFlot)
{
    arc arcCapaciteMin ;
    int i = 1;

    //while(estPraticable(lesArcs))
    while(estPraticable(lesArcs))
    {
        i++;

        arcCapaciteMin = arcNsMinCapacite(lesArcs);
        cout << "Selection de l'arc de capacite residuelle minimale:"<<endl;
        cout << "L'arc selectionne est: ";
        afficheArc(arcCapaciteMin);
        lesAugmentationsFlot.push_back(arcCapaciteMin.capacite);
        augmentationFlot(chercheChemin(arcCapaciteMin,lesArcs,entree,sortie),lesArcs,arcCapaciteMin.capacite,histoChemins);
        chercheBlocage(lesArcs,entree,sortie);
        cout << "APRES AUGMENTATION DES FLOTS VOICI L'ETAT DU RESEAU"<<endl;
        afficheLesArcs(lesArcs);
        metAjourTrace(trace,lesArcs);

    }
    cout << endl << "La valeure du flot complet est "<<flotComplet(lesAugmentationsFlot) <<endl<<endl;

    return 0;
}
bool contientSommet(vector<arc> lesArcs, string sommet)
{
    for(unsigned i=0; i<lesArcs.size();i++)
    {
        if( lesArcs[i].villeDep.compare(sommet)== 0 )return true;
    }
    return false;
}

void metArcMinNull(vector<arc> &lesArcs,vector<arc> chemin,string sommetCirc)
{
    unsigned i=0;
    while( chemin[i].villeDep.compare(sommetCirc)!=0 )
    {
        chemin.erase(chemin.begin()+i);
    }

    arc arcMinChemin = arcNsMinCapacite(chemin);
    for(unsigned i=0; i<lesArcs.size();i++)
    {
        if(arcMinChemin.villeDep.compare(lesArcs[i].villeDep)==0 && arcMinChemin.villeDest.compare(lesArcs[i].villeDest)==0)
        {
            lesArcs[i].bloque = true;
            cout << "A cause du circuit, l'arc ";
            afficheArc(lesArcs[i]);
        }
    }
}

void metAjourTrace(vector< vector<arc> > &trace,vector<arc> lesArcs)
{
    vector<arc> arcsAajoutes;
    for(unsigned i =0;i<lesArcs.size();i++)
    {
        arcsAajoutes.push_back(lesArcs[i]);
    }
    trace.push_back(arcsAajoutes);

}

void afficheTrace(vector< vector<arc> > trace, vector<arc> lesArcs)
{
    cout << "TRACE D'EXECUTION" << endl;
    unsigned nbLignes = lesArcs.size();
    unsigned nbColonnes = trace.size();

            for(unsigned j = 0;j<nbLignes;j++)
            {
                cout << lesArcs[j].villeDep << lesArcs[j].villeDest<<"  ";
                for(unsigned i = 0;i<nbColonnes;i++)
                {
                    cout << trace[i][j].capacite;
                    if(trace[i][j].capacite <10)cout<<" ";
                    cout << " ";
                }
                cout << endl;
            }
            cout << endl;
}

void ecrire_fichier(vector< vector<arc> > traceB, vector<arc> lesArcsB, vector< vector<arc> > traceF, vector<arc> lesArcsF,vector< vector<arc> > histoChemins,vector<int> lesAugmentationsFlot,vector<string> Trace_chemin,vector<int> Trace_value,int flotMax)
{
    ofstream fichier("test.html");
    if(fichier)
    {
        unsigned nbLignes = lesArcsB.size();
        unsigned nbColonnes = traceB.size();
        fichier << "<link rel=""stylesheet"" href=""design.css"" />" << endl;
        fichier << "<h1> Algorithme de Bloch </h1>" << endl;
        fichier << "<p> Noir : normal. Rouge : saturé. Bleu : bloqué. </p>" << endl;
        fichier << "<table>" << endl;
        fichier << "<tr> <th> Arcs </th> <th> </th> </tr>" << endl;
        for(unsigned j=0; j<nbLignes ; j++)
        {
            fichier << "<tr> <td> "<< lesArcsB[j].villeDep << lesArcsB[j].villeDest << "</td>";
            for(unsigned i=0 ; i<nbColonnes ; i++)
            {
                if(traceB[i][j].sature == true) fichier << "<td style=""color:white"""";background-color:rgb(255,23,23)"">" << "[" << traceB[i][j].capa << "]" << traceB[i][j].flot << "</td>";
                else if(traceB[i][j].bloque ==  true) fichier << "<td style=""color:white"""";background-color:rgb(23,135,247)"">" << "[" << traceB[i][j].capa << "]" << traceB[i][j].flot<< "</td>";
                else fichier << "<td>" << "[" << traceB[i][j].capa << "]" << traceB[i][j].flot << "</td>";
            }
        }
        fichier << "</table></br>" << endl;

        //affichage chemins
        fichier << "<p> Chemins analysés </p>" << endl;
        fichier << "<table>" << endl;
        fichier << "<tr> <td>Chemin</td> <td>Augmentation</td> </tr>"<<endl;
        for(unsigned j=0;j<histoChemins.size();j++)
        {
            fichier << "<tr> <td> <div id=""chemin"">";
            for(unsigned i=0;i<histoChemins[j].size();i++)
            {
                fichier << histoChemins[j][i].villeDep << " - ";
                if(histoChemins[j].size() == i+1 )fichier << histoChemins[j][i].villeDest;

            }
            fichier << "</div></td> <td>+" << lesAugmentationsFlot[j]<< "</td></tr> ";
        }
        fichier << "</table>" << endl;

        fichier << "<p> Flot complet à : " << flotComplet(lesAugmentationsFlot)<<"</p>" << endl;

        nbLignes = lesArcsF.size();
        nbColonnes = traceF.size();
        fichier << "<br/> <h1> Algorithme de Ford Fulkerson </h1>" << endl;
        fichier <<"<p> Diminution de la CR en bleu. Augmentation en rouge. <br/> </p>" << endl;
        fichier << "<table>" << endl;
        fichier << "<tr> <th> Arcs </th> <th>  </th>" << endl;
        for(unsigned j = 0;j<nbLignes;j++)
        {
            fichier << "<tr> <td> "<< lesArcsF[j].villeDep << lesArcsF[j].villeDest << "</td>";
            for(unsigned i = 0;i<nbColonnes;i++)
            {
                if(i!=0 && (traceF[i][j].flot < traceF[i-1][j].flot)) fichier << "<td style=""color:white"""";background-color:rgb(255,23,23)"">" << "[" << traceF[i][j].capa << "]" << traceF[i][j].flot << "</td>";
                else if(i!=0 && traceF[i][j].flot > traceF[i-1][j].flot) fichier << "<td style=""color:white"""";background-color:rgb(23,135,247)"">" << "[" << traceF[i][j].capa << "]" << traceF[i][j].flot << "</td>";
                else fichier << "<td>" << "[" << traceF[i][j].capa << "]" << traceF[i][j].flot << "</td>";
            }
        }
        fichier << "</table>" << endl;

        //afichage chemins pour ford

        //affichage chemins
        fichier << "<p> Chemins analysés </p>" << endl;
        fichier << "<table>" << endl;
        fichier << "<tr> <td>Chemin</td> <td>Diminution/Augmentation</td> </tr>"<<endl;
        for(unsigned j=0;j<Trace_chemin.size();j++)
        {
            fichier << "<tr> <td> <div id=""chemin"">";

                fichier << Trace_chemin[j];

            fichier << "</div></td> <td>" << Trace_value[j]<< "</td></tr> ";
        }
        fichier << "</table>" << endl;

        fichier << "<p> Flot maximal à : " << flotMax<<"</p>" << endl;
    }
    else
    {
        cout << "Erreur : impossible d'ouvrir le fichier" << endl;
    }

}

int flotComplet(vector<int> lesAugmentationsFlot)
{
    int flotComplet = 0;
    for(unsigned i = 0;i<lesAugmentationsFlot.size();i++)
    {
        flotComplet += lesAugmentationsFlot[i];
    }
    return flotComplet;
}

int flotMax(vector<arc> lesArcsF,string sortie)
{
    int flotMax = 0 ;
    for(unsigned i = 0; i < lesArcsF.size(); i++)
    {
        if(lesArcsF[i].villeDest.compare(sortie)==0)flotMax += lesArcsF[i].flot;
    }
    return flotMax;
}

bool connexeMat(vector<arc> lesArcs,string entree, string sortie){

    arc arcCourant;
    arc arcSuivant;
    arc arcDrapeau;// utile pr le cas du circuit

    //pour le cas du circuit, on garde les sommet en memoire
    vector<string> sommetsDuChemin;


    for(unsigned i = 0;i<lesArcs.size();i++)
    {
       arcCourant = lesArcs[i];
       arcSuivant = arcCourant;
       sommetsDuChemin.clear();

       sommetsDuChemin.push_back(arcCourant.villeDep);
       sommetsDuChemin.push_back(arcCourant.villeDest);

       while(arcSuivant.null == false){

            arcDrapeau = arcSuivant;
            arcSuivant = arcNsSuivant(arcSuivant,lesArcs);

            // on gere ici le cas du circuit
            if(existDslist(sommetsDuChemin, arcSuivant.villeDest)== false)
            {
                sommetsDuChemin.push_back(arcSuivant.villeDest);
            }
            else
            {

                // on sature l'arc pour pas qu'il ne soit pas repris en compte

                for(unsigned j = 0;j<lesArcs.size();j++)
                {
                    if(lesArcs[j].villeDep == arcSuivant.villeDep && lesArcs[j].villeDest == arcSuivant.villeDest)
                    {
                        lesArcs[j].sature = true;
                    }
                }
                arcSuivant = arcNsSuivant(arcDrapeau,lesArcs);

            }


            if(arcSuivant.null == false){
                arcCourant = arcSuivant;
                afficheArc(arcCourant);
            }
       }

       if(arcCourant.villeDest.compare(sortie) != 0) return false;

    }

return true;
}



bool existDslist(vector<string> sommets, string sommet)
{
    for(unsigned i = 0;i<sommets.size();i++)
    {
        if(sommets[i].compare(sommet)==0)return true;
    }
    return false;
}