#
# 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) pour calculer une valeur de
# depart pour le meilleur circuit que l'on peut esperer
# ATTENTION : il est possible que cette heuristique ne fournisse ausun resultat
# c'est-a-dire ne trouve pas de circuit hamiltonien. Dans ce cas elle renvoie
# INFINI comme resultat.

resource TSP_heuristique()
  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], "]" );
  }

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

  int nbCircuitsComplets = 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); }


  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.
  #########################################################################

  procedure poursuivreChemin( Sequence chemin, int n, res int cout ) {
    if (longueur(chemin) == n) {
      cout = coutChemin(chemin);
      if ( areteExiste(queue(chemin), tete(chemin)) ) {
        cout += W[queue(chemin)][tete(chemin)];
      }
    } 
    else {
      int estime;
      int opt   = INFINI;
      int choix = 0;
      for [s = 1 to n st ~dejaVisite(chemin, s)] {
        if ( areteExiste(queue(chemin), s) ) {
          estime = coutEstime(chemin, s, n);
          if (estime < opt) { opt = estime; choix = s; }
        }
      }	  
      
      if ( choix == 0 ) { 
        # Dans ce cas on n'a pas trouve de circuit hamiltonien
	cout = INFINI; 
      } 
      else { 
	ajouterEnQueue(chemin, choix); 
	poursuivreChemin(chemin, n, cout); 
      }
    }
  }

  procedure trouverBorne( int sommetDepart, int n ) {
    Sequence chemin = creer();
    int      cout;

    # On explore un chemin.
    ajouterEnQueue(chemin, sommetDepart);
    poursuivreChemin(chemin, n, cout);

    # On imprime le resultat.
    imprimer( chemin ); 
    write( " =>", cout );
 
  }

  for [i = 1 to n] {
    trouverBorne( i, n );
  }
end