/* File: Graphe.cc -- Francois -- Last modified on 23 Jan 2002
 * 	
 *      Algorithme dans les Graphes
 *
 */




#include <iostream>

#include <string>
#include <vector>
#include <cassert>

// pour le parser:
#include <iomanip>
#include <cstdlib>
#include <fstream>


//=============================================
//  Classes auxiliaires

// Les deux classes suivantes sont utilisees pour: le parser et le
// constructeur Graphe::Graphe(triplet_SDS *)
// elles sont definies a` la fin...


// Type retourne par le parser  (liste de triplets)

struct triplet_SDS {
  string _source;
  double _duree;
  string _dest;
  
  triplet_SDS * _suivant;

  triplet_SDS(string s1 ="",double d =0,string s2 ="",triplet_SDS * suiv =0)
  {_source = s1; _duree = d; _dest = s2; _suivant = suiv;}
};


// type utilise par Graphe::Graphe(triplet_SDS *)
class Ensemble {
private :
  struct Elem {
    string _val;
    Elem * _suivant;
    Elem(string s,Elem * suiv)
    {_val=s; _suivant = suiv;}
  };

  Elem * debut;
public:
  Ensemble();
  bool Contient(string s);
  void Ajouter(string s);
  int Taille();
  string Acces(int i);  // retourne la i-eme chaine de l'ensemble (0...l-1)
  void Detruire();
};


//=============================================
//  Classe DISTANCE = double + {infini}


class Distance {
private:
  double _dist;
  bool _infini;  // vrai ssi infini 
public :
  Distance()
  {_dist=0; _infini=true;}
  Distance(double d)
  {_dist=d; _infini=false;}
  friend Distance operator +(const Distance & d1,const Distance & d2);
  friend bool operator >(const Distance & d1,const Distance & d2);
  friend ostream & operator <<(ostream & os,Distance d);
};

Distance operator +(const Distance & d1,const Distance & d2)
{
  if (d1._infini || d2._infini) return d1;
  return Distance(d1._dist+d2._dist);
}

bool operator >(const Distance & d1,const Distance & d2)
{
  if (d2._infini) return false;
  if (d1._infini) return true;
  return (d1._dist>d2._dist);
}

ostream & operator <<(ostream & os,Distance d)
{
  if (d._infini) 
    os << "oo";
  else cout << d._dist;
  return os;
}

Distance min(const Distance & d1,const Distance & d2)
{
  return (d1 > d2) ? d2 : d1;
}





// =============================================
//
//            La classe GRAPHEM - Matrice 
//
// =============================================


class Graphe; // declaree car utilisee ci-dessous

class GrapheM {
private :

  int _NS;                        // nombre de sommets
  vector<string> _Noms;           // noms de sommets
  vector<vector<Distance> > _M;   // Matrice d'adjacence

  int Numero(string s); // retourne le numero du noeud s

public :

  GrapheM();
  GrapheM(Graphe G);

  string Nom(int i);
  void Affiche();
  void PCC_Floyd();

};



// =============================================
//
//            La classe GRAPHE 
//
// =============================================





class Graphe {
private :

  struct Lsucc {
    double _duree;     //  duree de la transition
    int _idest;         //  numero du sommet dest
    Lsucc * _suivant;  //  prochain succ

    Lsucc(double d,int noeud,Lsucc * suiv)
    {_duree=d; _idest=noeud; _suivant = suiv;}
  };

  int _NS;                 // nombre de sommets
  vector<string> _Noms;    // noms de sommets
  vector<Lsucc *> _Ladj;   // tableau des listes d'adjacence


  int Numero(string s); // retourne le numero du noeud s
  void Graphe::PP_Visiter(int sommet,int & tps,vector<int> & debut,
                           vector<int> & fin, vector<bool> & DejaVu,
			  vector<int> & Pred) ;  // utilisee par ParcoursP()

  vector<int> ParcoursP_CC(vector<int> ordre); // utilisee par ComposanteC()

  void PCC_Initialisation(int s,vector<Distance> & d,vector<int> & pred);
  void PCC_Relax(int u, int v, double duv, vector<Distance> & d,vector<int> & pred);


  friend GrapheM::GrapheM(Graphe G);

public :

  Graphe(int ns,vector<string> noms,vector<Lsucc*> ladj);
  Graphe(triplet_SDS * lt =0);
  string Nom(int i);
  void Affiche();

  // la fonction parcours retourne un tableau de dates de "fin"
  vector<int> ParcoursP();

  // ComposantesCC() retourne un tableau representant les CC (voir def)
  vector<int> ComposantesC();
  Graphe Transpose();

  bool PCC(string s1);  // algo Bellman-Ford

};




//====================================================
// DEFINITIONS DES FCT DE LA CLASSE GRAPHE


// retourne le nom du noeud i
string Graphe::Nom(int i)
{
  assert((i>=0) && (i<_NS));
  return _Noms[i];
}

// retourne le numero du noeud s
int Graphe::Numero(string s) 
  { int res;
  for (res=0;res<_NS;res++) 
    if (_Noms[res]==s) return res;
  assert(0); // si pas de noeud s -> stop !!
  }
    

//=================================================
//        Constructeurs

Graphe::Graphe(int ns,vector<string> noms,vector<Lsucc*> ladj)
{
  assert(noms.size() == ns);
  assert(ladj.size() == ns);
  _NS = ns;
  _Noms = noms;
  _Ladj = ladj;
}

// construit un Graphe a` partir de la liste de triplets fournies par
// le parser
Graphe::Graphe(triplet_SDS * lt =0)
{
  if (lt == 0) {
    _NS=0;
    return;
  }
  
  // Trouver l'ensemble des sommets:
  Ensemble S;
  triplet_SDS * ltaux;
  for (ltaux = lt; ltaux != 0; ltaux = ltaux->_suivant) {
    S.Ajouter(ltaux->_source);
    S.Ajouter(ltaux->_dest);
  }

  // On a le nombre de sommets:
  _NS = S.Taille();
  _Noms = vector<string>(_NS);  // on en deduit la taille de _Noms

  // affectation des noms:
  for (int i=0;i<_NS;i++) 
    _Noms[i] = S.Acces(i);
  
  S.Detruire();  // on n'a plus besoin de S

  // Construction des listes d'adjacence:
  _Ladj = vector<Lsucc *>(_NS);  // initialise avec le pointeur 0
  for (int i=0;i<_NS;i++)
    _Ladj[i]= 0;

  int indsource, inddest;
  for (ltaux = lt; ltaux != 0; ltaux = ltaux->_suivant) {
    indsource = Numero(ltaux->_source);
    inddest   = Numero(ltaux->_dest);
    _Ladj[indsource] = new Lsucc(ltaux->_duree, inddest, _Ladj[indsource]);
  }

  // et voila...
  // on fait le menage: on detruit la liste lt
  while (! lt) {
    ltaux = lt;
    lt = lt->_suivant;
    delete ltaux;
  }

}

//=================================================
//        Affiche un Graphe

void Graphe::Affiche()
{
  cout << "** Graphe: " << endl;
  cout << "Sommets: " << endl;
  
  for (int i=0;i<_NS; i++) 
    cout << _Noms[i] << "  ("<<i<<")"<< endl;
  cout << endl << "Transitions : " << endl;

  Lsucc * laux;
  for (int i=0;i<_NS;i++) {
    for (laux =_Ladj[i]; laux != 0; laux = laux->_suivant) 
      cout << _Noms[i] << " - " << laux->_duree << " -> " << _Noms[laux->_idest] << endl;
  }
  cout << "**" << endl;
}

//=================================================
//        Transpose d'un graphe

Graphe Graphe::Transpose()
{
  vector<Lsucc*> ladjT(_NS);
  
  // construction du nouveau de LadjT:
  for (int i=0;i<_NS;i++) 
    ladjT[i] =0;
  
  Lsucc * laux;
  for (int i=0;i<_NS;i++) {
    for (laux = _Ladj[i]; laux; laux = laux->_suivant) 
      ladjT[laux->_idest] = new Lsucc(laux->_duree,i,ladjT[laux->_idest]);
  }
  Graphe res(_NS,_Noms,ladjT);
  return res;
}


//=================================================
//        Parcours en profondeur

vector<int> Graphe::ParcoursP()
{
  vector<int> debut(_NS,0);        // dates...
  vector<int> fin(_NS,0);
  vector<bool> DejaVu(_NS,false);  // remplace Couleur
  vector<int> IndPred(_NS,-1);     // indice du predecesseur (pi)
  int Time=0;
  
  for(int s=0;s<_NS;s++) 
    if (! DejaVu[s]) PP_Visiter(s,Time,debut,fin,DejaVu,IndPred);

  for (int i=0;i<_NS;i++) 
    cout << _Noms[i] << " : " << debut[i] << " - " << fin[i] << endl;

  return fin;
}


void Graphe::PP_Visiter(int sommet,int & tps,vector<int> & debut,vector<int> & fin, vector<bool> & DejaVu,vector<int> & Pred)
{
  DejaVu[sommet]=true;
  tps++;
  debut[sommet]=tps;
  for (Lsucc * aux = _Ladj[sommet]; aux!=0 ; aux=aux->_suivant) 
    if (! DejaVu[aux->_idest]) {
      Pred[aux->_idest] = sommet;
      PP_Visiter(aux->_idest,tps,debut,fin,DejaVu,Pred);
    }
  tps++;
  fin[sommet]=tps;
}

//======================================================
// Recherche de composantes fortement connexes
//======================================================

// fct auxiliaire  (pas efficace mais...)
vector<int> calcul_ordre(vector<int> dates)
{
  vector<int> res(dates.size(),-1);
  int aux;
  for (int i=0;i<dates.size();i++) {
    aux = 0;
    for (int j=1;j<dates.size();j++) 
      if (dates[j]>dates[aux]) aux=j;
    res[i]=aux;
    dates[aux]=-1 ; // dates[] ne contient que des entiers >0 -> on
  // met -1 pour etre sur qu'au coup suivant on trouvera le (n+1)eme
  // plus grand element...
	
  }
  return res;
}


// le tableau resultat contient les CFC au sens ou`:
// tabCC[s1] == tabCC[s2] ssi s1 et s2 appartiennent a` la meme CFC

vector<int> Graphe::ComposantesC()
{
  vector<int> tabCC(_NS,0);  // tableau resultat

  // on parcourt G une premiere fois
  vector<int> datesfin;
  datesfin = ParcoursP();

  // on calcule G_t
  Graphe Gt = Transpose();

  Gt.Affiche();

  // On parcourt Gt suivant l'ordre decroissant de datesfin
  // on commence par construire ordre[] un tableau tel que:
  // ordre[0] est le numero du sommet ayant la plus grande date de fin
  // ordre[1] est le .........................seconde...
  
  vector<int> ordre = calcul_ordre(datesfin);
  vector<int> pred = Gt.ParcoursP_CC(ordre);

  // il reste a` construire tabCC a` partir de Pred
  int s, aux, NbCC=0; // nb de CC
  for (s=0;s<_NS;s++) 
    if (pred[s]==-1) {
      NbCC++;
      tabCC[s]=NbCC;
    }
  // on a calcule le nb de CC, il reste a` trouver la CC de chaque noeud
  for (s=0;s<_NS;s++) {
    if (tabCC[s] == 0)  { // s n'est pas une racine de pred
      aux = pred[s];
      while (pred[aux] != -1) aux = pred[aux];
      tabCC[s]=tabCC[aux];  // on recupere le numero de CC de s
    }
  }
   
  return tabCC;
}

// retourne le tableau de l'arborescence 
vector<int> Graphe::ParcoursP_CC(vector<int> ordre)
{
  vector<int> debut(_NS,0);        // dates...
  vector<int> fin(_NS,0);
  vector<bool> DejaVu(_NS,false);  // remplace Couleur
  vector<int> IndPred(_NS,-1);     // indice du predecesseur (pi)
  int Time=0;
  for(int i=0;i<_NS;i++) 
    if (! DejaVu[ordre[i]]) 
      PP_Visiter(ordre[i],Time,debut,fin,DejaVu,IndPred);

  for (int i=0;i<_NS;i++) 
    cout << _Noms[i] << " a comme predecesseur " << IndPred[i] << endl;

  return IndPred;
}


//=====================================================
//       Plus courts chemins - algo Bellman-Ford
//=====================================================

bool Graphe::PCC(string s)
{
  vector<Distance> Dist(_NS);
  vector<int> Pred(_NS);
  int ns = Numero(s);
  int i,j;
  Lsucc * aux;

  PCC_Initialisation(ns,Dist,Pred);

  for (i=0;i<_NS-1;i++) 
    for (j=0;j<_NS;j++) 
      for (aux = _Ladj[j]; aux; aux = aux->_suivant) 
	PCC_Relax(j,aux->_idest,aux->_duree,Dist,Pred);
    
  /*  // on affiche les PCC:
  for (i=0;i<_NS;i++) {
    cout << "Sommet " << _Noms[i] << " : " << Dist[i];
    cout << " predecesseur: " << ((Pred[i] == -1) ? "nil" : _Noms[Pred[i]]) << endl;
    }*/

  // on detecte la presence d'un cycle negatif:
  for (j=0;j<_NS;j++) 
    for (aux = _Ladj[j]; aux; aux = aux->_suivant) 
      if (Dist[aux->_idest] > Dist[j]+aux->_duree)
	return false;
  
  return true;  // pas de cycle negatif
}



void Graphe::PCC_Initialisation(int s, vector<Distance> & d,vector<int> & pred)
{
  for (int i=0;i<_NS;i++) {
    d[i]=Distance();
    pred[i]=-1;
  }
  d[s]=Distance(0);   
}

void Graphe::PCC_Relax(int u, int v, double duv, vector<Distance> & d,vector<int> & pred)
{
  if (d[v] > d[u]+duv) {
    d[v] = d[u]+duv;
    pred[v]=u;
  }
}





//====================================================

// DEFINITIONS DES FCT DE LA CLASSE GRAPHE_M  (Matrice)

//====================================================

string GrapheM::Nom(int i)
{
  assert((i>=0) && (i<_NS));
  return _Noms[i];
}

// retourne le numero du noeud s
int GrapheM::Numero(string s) 
  { int res;
  for (res=0;res<_NS;res++) 
    if (_Noms[res]==s) return res;
  assert(0); // si pas de noeud s -> stop !!
  }
    
GrapheM::GrapheM()
{_NS=0;}

GrapheM::GrapheM(Graphe G) 
{
  _NS = G._NS;
  _Noms = G._Noms;
  _M = vector<vector<Distance> >(_NS,vector<Distance>(_NS,Distance()));

  for (int i=0;i<_NS;i++)
    for (Graphe::Lsucc * aux=G._Ladj[i]; aux != 0; aux = aux->_suivant) 
      _M[i][aux->_idest] = Distance(aux->_duree);
}

void GrapheM::Affiche() 
{
  cout << "Graphe:"<< endl;
  for (int i=0;i<_NS;i++) 
    cout << '\t' << _Noms[i];
  cout << endl;

  for (int i=0;i<_NS;i++) {
    cout << _Noms[i] << '\t';
    for (int j=0;j<_NS;j++) 
      cout << _M[i][j] << '\t';
    cout << endl;
  }
  cout << "*" << endl;
}

void GrapheM::PCC_Floyd()
{
  for (int k=0;k<_NS;k++) 
    for (int i=0;i<_NS;i++) 
      for (int j=0;j<_NS;j++) 
	_M[i][j] = min(_M[i][j],_M[i][k]+_M[k][j]);
}




//======================================================
//          MAIN

// On declare la fct parser 
triplet_SDS * LireGraphe(char * fich);

int main(int argc,char * * argv)
{
  // argc est le nb d'arguments+1
  // argv[0] = nom de l'executable
  // argv[1] = premier argument 
  // argv[2] = second ...

  if (argc != 2) {
    cout << "Il faut un (et un seul) argument !!" << endl;
    exit(1);
  }

  Graphe G(LireGraphe(argv[1]));  // on construit le graphe avec le fichier "argv[0]"

  /*
  G.Affiche();
  vector<int> cc = G.ComposantesC();

  for (int i=0;i<cc.size();i++) 
    cout << G.Nom(i) << " numero de CC : " << cc[i] << endl;
  bool res = G.PCC("z");
  if (res) 
    cout << "Il n'y a pas de cycle negatif !" << endl;
  else cout << "Il y a un cycle negatif !" << endl;
  */


  GrapheM M(G);
  M.Affiche();
  M.PCC_Floyd();
  M.Affiche();

}

//================================================================

//           Parser pour les descriptions de graphe

//================================================================



// le parser...
triplet_SDS * LireGraphe(char * fich)
{

  string debut("Graphe:");  // mot cle'  du debut
  string fin(".");          // mot cle'  de fin
  string buff;
  string s1;
  double d;
  triplet_SDS * res =0;

  ifstream inFile (fich,ios::in);
  
  if (! inFile)
    { cerr << "pb ! mauvais nom de fichier " << endl;
    exit(1);}

  // on passe tout ce qui est avant le mot cle de debut:
 while ((inFile >> buff) && (buff != debut)) ;

  // on lit les transitions ...
  // il y a deux types:  qw - 42.43 -> erty   OU  qw -> erty

 while ((inFile >> buff) && (buff != fin)) {   
   s1 = buff;  // c'est le noeud source
   inFile >> buff; // - ou ->

   if (buff == "-") {   
     inFile >> buff;          // duree 
     d = atof(buff.c_str());  // transforme le string en double
     inFile >> buff;          // lit le ->
     assert(buff == "->");
   }
   else d = 0.0; 

   inFile >> buff;  // lit le noeud dest
   res = new triplet_SDS(s1,d,buff,res);
 }
  
 return res;
}


//================================================================
// -----------  classe  EnsembleS : ensemble de string ------
//              utilise par le constructeur Graphe::Graphe

Ensemble::Ensemble()
  {debut=0;}

bool Ensemble::Contient(string s)
  {
    for(Elem * aux=debut; aux != 0; aux = aux->_suivant)
      if (aux->_val == s) 
	return true;
    return false;
  }

void Ensemble::Ajouter(string s)
  {
    if (! Contient(s)) 
      debut = new Elem(s,debut);
  }

int Ensemble::Taille()
  { 
    int res=0;
    for (Elem * aux=debut; aux != 0; aux = aux->_suivant) res++;
    return res;
  }

string Ensemble::Acces(int i)  // retourne la i-eme chaine de l'ensemble (0...l-1)
  {
    int c=0;
    Elem * aux;
    for (aux=debut; (c<i) && (aux != 0); aux = aux->_suivant) c++;
    if (aux==0) 
      return "";
    return aux->_val;
  }

void Ensemble::Detruire()
  {
    Elem * aux=debut, * aux2;
    while (! aux) {
      aux2 = aux;
      aux = aux->_suivant;
      delete aux2;
    }
  }