Fonction qui tris les Variables et met un ID correspondant

Messages : 1 Date d'inscription : 17/02/2015

Code:: void tri_liste_variable()
{
   if(nombreVariable == 1)// cas ou il n'y a que une variable
   {
   listeVariables->id = 0 ;
   return;
   }

   int i;
   int* tab_nbr_apparition_variable = (int*) malloc(nombreVariable * sizeof(int)); // nombreVariable var global donné par le yacc
   char* tab; // stocke le tableau presence variable d'une contrainte
   listeContrainte newContrainte; // liste des contraintes d'une variabl
   int fini = -1;
   variables news = listeVariables, tampon , precedent, suivant;

   for(i =0 ; i<nombreVariable ; i++) // initialisation du tableau a 0
   {
   tab_nbr_apparition_variable[i] = 0;
   }

   while( !(fin_de_liste(news)) ) // boucle remplissant le tableau avec les nbr d'aparition des variables dans les contraintes
   {
   newContrainte = news->contraintes;
   while(newContrainte != NULL)
   {
   tab =newContrainte->presenceVariable ;
   for(i =0 ; i<nombreVariable ; i++)
   {
   if(tab[i] == '1')
   {
   tab_nbr_apparition_variable[i]++;
   }
   }
   newContrainte = newContrainte->suivant;
   }
   news = news->suivant;
   }


   news = listeVariables;
   i = 0;


   while( !(fin_de_liste(news)) )
   { // boucle affectant les id des dans les variables: nombre d'apparition contrainte divise par taille domaine
   news->id = tab_nbr_apparition_variable[i++] / (float)taille(news->domaines->dom);
   news = news->suivant;
   }

   while(fini != 1) // tri a bulle de la liste doublement chainée
   {
   fini = 1;

   precedent = listeVariables;
   news = precedent->suivant;
   suivant = news->suivant;
   tampon = precedent->precedent;

   if(precedent->id < news->id) // cas particulier pour savoir si le pointeur en debut de liste doit changer
   {
   fini = 0;
   precedent->suivant = suivant;
   precedent->precedent = news;
   news->suivant = precedent;
   news->precedent = tampon;
   if(suivant != NULL)
   suivant->precedent = precedent;
   tampon = precedent;
   precedent = news;
   news = tampon;

   listeVariables = precedent;
   }
   tampon = precedent;
   precedent = news;
   news = suivant;
   if(suivant != NULL)
   suivant = suivant->suivant;

   while( ! fin_de_liste(news))
   {

   if(precedent->id < news->id)
   {
   fini = 0;
   precedent->suivant = suivant;
   precedent->precedent = news;
   news->suivant = precedent;
   news->precedent = tampon;
   tampon->suivant = news;

   if(suivant != NULL)
   suivant->precedent = precedent;

   tampon = precedent;
   precedent = news;
   news = tampon;
   }
   tampon = precedent;
   precedent = news;
   news = suivant;

   if(suivant != NULL)
   suivant = suivant->suivant;
   }
   }

   // maintenant que les variables sont triées on leurs affectent un id correspondant de 0 a nombreVariable-1
   news = listeVariables;
   i=0;
   while (! fin_de_liste(news) )
   {
   news->id = i++;
   news = news->suivant;
   }
   free(tab_nbr_apparition_variable);
}

Messages : 12 Date d'inscription : 04/02/2015

je viens de me rendre compte de problèmes avec cette fonction

premièrement, on tri les variables alors que les contraintes ont déjà été affectées dans les variables.
or l'affectation des contraintes dans les variables dépend de l'ordre des variables et on change celui-ci avec cette fonction. la fonction affecter variable permet au moment de vérifier un arbre de contrainte, de toujours avoir toutes les variables ayant une valeur. donc il y aura des cas où des variables n'auront pas de valeur ici.

pour corriger on pourrai appeler cette fonction avant d'affecter les contraintes des variables

mais on a aussi un autre problème: avec les tableaux presenceVariable
ces tableaux aussi suppose que les variables sont dans le bon ordre. or si on change l'ordre des variables, alors tout les tableau presenceVariable ne correspondront plus à l'ordre des variables.

pour remédier à ces problèmes je vois plusieurs solutions

dans tous les cas il faut appeler cette fonction de tri avant l'appel de affecterContraintesDansVariables (qui est fait dans yacc), et pas dans la fonction main comme je l'ai fait

Première solution:
-on utilise la variable listeContrainte pour obtenir l'ensemble des contraintes (au lieu de récupérer les contraintes dans les variables)
-on tri les tableaux presenceVariable de toutes les contraintes en même temps qu'on tri la liste des variables
==> un peu dure je pense. et pas très efficace. mais possible

Deuxième solution:
-on ne fait plus intervenir le nombre d’occurrence d'une variable dans les contraintes (on tri seulement par ordre décroissant de taille du domaine)
-on appelle la fonction de tri des variables AVANT de commencer l'analyse des contraintes dans yacc. comme ça on construit les tableaux presenceVariable avec le nouvel ordre des variables
==> facile, mais on perd le critère du nombre d’occurrence qui je pense est important

Troisième solution:
-on analyse une première fois le fichier du CSP en faisant seulement un comptage du nombre d’occurrence des variables
-puis on l'analyse une deuxième fois comme actuellement
-on appelle la fonction de tri des variables AVANT de commencer l'analyse des contraintes.
==> niveau de difficulté entre les 2 précédents. cette solution m'a l'air bien. mais il fraudai un deuxième fichier yacc pour faire une analyse différente (ou alors tout faire dans un seul fichier en faisant pour chaque action sémantique : if(premièreAnalyse) ... else ...)

Quatrième solution:
-on ne tri pas, on met seulement les nombres entre 0 et nombreVariable-1 dans le champ ID des variables
==> très facile mais on enlève l'heuristique de trié les variables pour allé plus vite.

Messages : 12 Date d'inscription : 04/02/2015

nabil et moi avons implanté la première solution

le tri de variable fonctionne maintenant et chaque variable a son ID placé dans le champ ID