#
# Programme developpe par Guy Tremblay, Professeur au dept. d'informatique
# dans le cadre du cours INF7440.
# (Automne 2002, 2003, 2004)
# Modification par Cedric Chauve (Automne 2004)


resource TSP_largeur()
  const int INFINI = high(int);

  #############################################################
  # Matrices des couts pour le graphe.
  #############################################################

  # Lecture et verification du nombre d'elements a generer et a traiter
  int n; getarg(1, n); 

  if (n <= 0) {
    write("*** Erreur: n <= 0" );
    stop(1);
  }

  int germe; getarg(2, germe); 
  if (germe <= 0) {
    write("*** Erreur: germe <= 0" );
    stop(1);
  }

  int W[n][n];

  # Generation (aleatoire) des elements du tableau a.
  procedure generer( ref int a[*,*], int n ) 
  {
    seed(1.0 * germe); 
    for [i = 1 to n, j = 1 to n st i != j] {
      a[i][j] = int(random(1, 10*n));
    }
    for [i = 1 to n] {
      W[i][i] = 0;
    }
  }

  # Impression des elements d'un tableau.
  procedure imprimerCouts( int a[*][*], int n ) {
    for [i = 1 to n] {
      for [j = 1 to n-1] {
        writes( a[i][j], ", " );
      }
      write( a[i][n] );
    }
  }


  generer( W, n );
  write( "W = " );
  imprimerCouts( W, n );
  write();

  #############################################################
  # Types et procedures pour les sequences.
  #############################################################

  const int N = 100;
  type Sequence    = ptr SequenceRec;
  type SequenceRec = rec( int elems[N]; int ln; );

  procedure creer() returns Sequence s
  # POSTCONDITION
  #   s = []
  { s = new(SequenceRec); s^.ln = 0; }

  procedure cloner( Sequence s1 ) returns Sequence s2
  # POSTCONDITION
  #   s2 est un nouvel objet qui est une copie (profonde) de s1.
  { s2 = new(SequenceRec); s2^ = s1^; }

  procedure longueur( Sequence s ) returns int l
  # POSTCONDITION
  #   l = length(s)
  { l = s^.ln; }
 
  procedure ajouterEnQueue( Sequence s, int elem )
  # POSTCONDITION
  #   s = s' || [elem]
  { s^.ln += 1; s^.elems[s^.ln] = elem; }
  
  procedure supprimerQueue( Sequence s )
  # PRECONDITION
  #   s != []
  # POSTCONDITION
  #   s = s'[1..length(s')-1]
  { s^.ln -= 1; }
  
  procedure tete( Sequence s ) returns int t
  # PRECONDITION
  #   s != []
  # POSTCONDITION
  #   t = s[1]
  { t = s^.elems[1]; }

  procedure queue( Sequence s ) returns int q
  # PRECONDITION
  #   s != []
  # POSTCONDITION
  #   q = s[length(s)]
  { q = s^.elems[s^.ln]; }

  procedure element( Sequence s, int i ) returns int e
  # PRECONDITION
  #   i IN domain(s)
  # POSTCONDITION
  #   e = s[i]
  { e = s^.elems[i]; }

  procedure estElement( Sequence s, int e ) returns bool r 
  # POSTCONDITION
  #   r <=> e IN s
  { 
    r = false;
    for [i = 1 to s^.ln] {
      if( s^.elems[i] == e ) { r = true; return; }
    }
  }

  procedure imprimer( Sequence s ) 
  # POSTCONDITION
  #   Chacun des elements de s a ete imprime sur stdout.
  {
    writes("[");
    for [i = 1 to s^.ln-1] {
        writes( s^.elems[i], ", " );
    }
    writes( s^.elems[s^.ln], "]" );
  }

  #############################################################
  # Types et procedures pour les files.
  #############################################################

  # Structure de donnees pour un noeud de la liste chainee
  type Noeud    = ptr NoeudRec;
  type NoeudRec = rec( 
    Sequence elem;   # Chemin courant
    int estime;      # Estimation du cout minimum de la completion de elem
    Noeud suivant;   # Element suivant de la file
    Noeud precedent; # Element precedent de la file
  );

  # Structure de donnees pour la file
  type File     = ptr FileRec;
  type FileRec  = rec( 
    Noeud debut;    # Pointeur sur la cellule de debut de file
    Noeud fin ;     # Pointeur sur la cellule de fin de file
    int nbelements; # Nombre d'elements dans la file
    int nbelementsMax; # Nombre maximum d'elements dans la file
  );


  procedure creerF() returns File f { 
    f = new(FileRec); f^.debut = null; f^.fin = null; f^.nbelements = 0; f^.nbelementsMax = 0;
  }

  procedure ajouter( File f, int estime, Sequence elem ) { 
    Noeud N   = new(NoeudRec);
    N^.estime = estime;
    N^.elem   = elem;
    N^.precedent    = f^.fin;
    if ( f^.fin != null ) { 
      f^.fin^.suivant = N; 
    }
    else { 
      f^.debut = N; 
    }
    f^.fin = N;
    f^.nbelements++;
    if ( f^.nbelements > f^.nbelementsMax ) { f^.nbelementsMax = f^.nbelements; }
  }

  procedure estVide( File f ) returns bool r { 
    r = f^.debut == null; 
  }

  procedure obtenir( File f, ref int estime, ref Sequence elem ) {
    elem     = f^.debut^.elem;
    estime   = f^.debut^.estime;
    f^.debut = f^.debut^.suivant;
    if ( f^.debut == null ) { 
      f^.fin = null; 
    }
    else { 
      f^.debut^.precedent = null; 
    }
    f^.nbelements--;
  }

  #############################################################
  # Procedures pour le parcours du graphe. 
  #############################################################

  int nbCircuitsComplets = 0;
  int nbNoeudsParcourus  = 0;

  procedure areteExiste( int i, int j ) returns bool r 
  # ROLE
  #   Determine si une arete existe du sommet i vers le sommet j dans le graphe.
  # PRECONDITION
  #   i et j denote des numeros de sommets valides pour la matrice W.
  # POSTCONDITION
  #   r <=> W[i][j] != INFINI
  { r = W[i][j] != INFINI; }


  procedure dejaVisite( Sequence chemin, int sommet ) returns bool r
  # ROLE
  #   Determine si le sommet a deja ete visite, c'est-a-dire, 
  #   appartient deja au chemin indique.  
  # POSTCONDITION 
  #   r <=> estElement(chemin, sommmet)
  { r = estElement(chemin, sommet); nbNoeudsParcourus++; }


  procedure coutChemin( Sequence chemin ) returns int cout
  # POSTCONDITION 
  #   cout = sommme des couts des aretes reliant les sommets du chemin indique.
  {
    cout = 0;
    for [i = 1 to longueur(chemin)-1] {
      cout += W[element(chemin, i)][element(chemin, i+1)];
    }  
  }

  procedure coutMin( int couts[*], Sequence chemin, int aExclure ) returns int cout
  # POSTCONDITION
  #   cout = minimum des couts indiques, mais en ignorant le sommet aExclure
  #          de meme que les sommets deja visites de chemin (mais a l'exception 
  #          du sommet de depart, pour creer le cycle).
  {
    cout = high(int);
    for [i = 1 to ub(couts) st couts[i] > 0  
                            & i != aExclure 
                            & (~dejaVisite(chemin, i) | element(chemin, 1) == i) ] {
      cout = min(couts[i], cout);
    }
  }

  procedure coutEstime( Sequence chemin, int sommet, int n ) returns int cout
  # ROLE
  #   Determiner un estime (une borne inferieure) pour le cout d'un circuit
  #   obtenu en ajoutant le sommet indique au chemin existant.
  # POSTCONDITION
  #   cout = somme des couts du chemin + somme de l'arete reliant le dernier sommet
  #          du chemin a sommet + somme des couts minimum pour 
  #          aller vers les sommets pas visites puis vers le sommet de depart.
  #
  {
    cout = coutChemin(chemin);
    cout += W[queue(chemin)][sommet];
    cout += coutMin( W[sommet][*], chemin, queue(chemin) );
    for [s = 1 to n st s != sommet & ~dejaVisite(chemin, s)] {
      cout += coutMin( W[s][*], chemin, sommet );
    }
  }

  #########################################################################
  # Variables (globales) et procedures pour mise a jour du chemin minimum.
  #########################################################################

  Sequence cheminMin;
  int coutCheminMin = INFINI;

  procedure majCheminMin( Sequence chemin, int cout ) {
    if (cout < coutCheminMin) {
      cheminMin = chemin;
      coutCheminMin = cout;
    } 
  }

  procedure explorerCircuits( int n, res int lgFile ) {
    Sequence chemin = creer();
    File aExplorer  = creerF();
    int  estime;  

    ajouterEnQueue(chemin, 1);
    estime = coutEstime(chemin, 1, n);    
    ajouter(aExplorer, estime, chemin);

    while (~estVide(aExplorer)) {
      obtenir(aExplorer, estime, chemin);

      if (longueur(chemin) == n) {
        if ( areteExiste(queue(chemin), tete(chemin)) ) {
          int cout = coutChemin(chemin) + W[queue(chemin)][tete(chemin)];
          if (cout < coutCheminMin) {
            nbCircuitsComplets += 1; majCheminMin(chemin, cout); 
	    imprimer(chemin);write( " =>", coutCheminMin );
          }
        }
      }
      else {
        for [s = 1 to n st ~dejaVisite(chemin, s)] {
          estime = coutEstime(chemin, s, n); 
          if ( areteExiste(queue(chemin), s) & estime < coutCheminMin ) {
            Sequence ch = cloner(chemin); 
            ajouterEnQueue(ch, s);
            ajouter(aExplorer, estime, ch);
          }
        }
      }
    }

    lgFile = aExplorer^.nbelementsMax;
  }

  int lgFile;

  explorerCircuits(n, lgFile);

  write( nbCircuitsComplets, " circuits complets ont ete examines et ", nbNoeudsParcourus, "noeuds ont ete parcourus et la longueur max de la file des noeuds actifs etait de ", lgFile );
end