include/MooreAlgorithm.hpp

Go to the documentation of this file.
00001 // MooreAlgorithm.hpp: this file is part of the REGAL project.
00002 //
00003 // REGAL : Random and Exhaustive Generators for Automata - Library
00004 //
00005 // Copyright (C) 2007 Julien DAVID.
00006 //
00007 // This program is free software; you can redistribute it and/or
00008 // modify it under the terms of the GNU General Public License
00009 // as published by the Free Software Foundation; either version 2
00010 // of the License, or (at your option) any later version.
00011 //
00012 // The complete GNU General Public Licence Notice can be found as the
00013 // `COPYING' file in the root directory.
00014 //
00015 //
00016 #ifndef MOOREALGORITHM
00017 #define MOOREALGORITHM
00018 
00019 #include "MinimizingAlgorithm.hpp"
00020 #include "Alphabet.hpp"
00021 #include "toolbox/GenericFunction.hpp"
00022 #include "toolbox/LexicographicalSort.hpp"
00023 
00024 
00025 namespace regal{
00026   
00027   template<typename StateLabel_t,typename Sigma,class Automaton_t=AbstractAutomaton<StateLabel_t,Sigma> >
00028   class MooreAlgorithm: public MinimizingAlgorithm<StateLabel_t,Sigma,Automaton_t>{
00029   private:
00030     int *partitionTmp;
00031     int ** partitionWord; 
00032     int complexity; 
00033     int * tmpClassNum[2]; 
00034     bool tmpClassNumFlag;
00035     int aSize; 
00036     List_t ** lexicographical;
00037     List_t * lexicographicalRes;
00038     List_t * lexicographicalTMP;
00039 
00040     
00045     void freeMemory(){
00046       int i;
00047       if(this->partitionRes!=NULL)delete [] this->partitionRes;
00048       if(partitionTmp!=NULL)delete [] partitionTmp;
00049       if(partitionWord!=NULL){
00050         for(i=0;i<this->size;i++){
00051           delete [] partitionWord[i];
00052           destroyList(lexicographical[i]);
00053         }
00054         destroyList(lexicographical[i]);
00055         free(lexicographical);
00056         destroyList(lexicographicalRes);
00057         destroyList(lexicographicalTMP);
00058         delete [] partitionWord;
00059       }
00060     }
00061     
00065     void initPartition(const int & s,const int & as){
00066       int i;
00067       if(s!=this->size){
00068         freeMemory();
00069         this->size=s;
00070         aSize=as;
00071         this->partitionRes=new int[this->size];
00072         this->partitionTmp=new int[this->size];
00073         this->partitionWord=new int*[this->size];
00074         this->lexicographical=(List_t **)malloc(sizeof(List_t *)*(s+1));
00075         for(i=0;i<this->size;i++){
00076           this->partitionWord[i]=new int[as];
00077           this->lexicographical[i]=createList();
00078         }
00079         this->lexicographical[i]=createList();
00080         this->lexicographicalTMP=createList();
00081         this->lexicographicalRes=createList();
00082       }
00083     }
00084     
00091     void lexicographicalSort(int prof){
00092       doubleChainedList_t * tmp;
00093       while(lexicographicalRes->first!=NULL){
00094         tmp=extractFirstList(&lexicographicalRes);
00095         if(prof==0)
00096           insertNodeLastList(&(lexicographical[this->partitionRes[tmp->val]]),tmp);
00097         else{
00098           if(this->partitionWord[tmp->val][prof-1]!=-1)
00099             insertNodeLastList(&(lexicographical[this->partitionWord[tmp->val][prof-1]]),tmp);
00100           else
00101             insertNodeLastList(&(lexicographical[this->maxClass]),tmp);
00102         }
00103       }
00104       for(int i=0;i<=this->maxClass;i++)
00105         concatList(&lexicographicalRes,&lexicographical[i]);    
00106     }
00107     
00108     /*
00109       Launch the function lexicographicalSort k+1 times
00110       then compares the states in the list two by two.
00111       If their parameters are still the same, they are still in the same classes.
00112       Otherwise a new class is created.
00113     */
00114     void sortClasses(){
00115       doubleChainedList_t * tmp,*tmp2;
00116       if(tmpClassNumFlag==true)
00117         memset(tmpClassNum[1],0,this->size*sizeof(int));
00118       for(int i=aSize;i>=0;i--)
00119         lexicographicalSort(i);
00120       this->maxClass=1;
00121       
00122       for(tmp=lexicographicalRes->first,tmp2=NULL;tmp!=NULL;tmp2=tmp,tmp=tmp->next){
00123         if(tmp2!=NULL&&!sameClass(aSize,tmp->val,tmp2->val))
00124           this->maxClass++;
00125         partitionTmp[tmp->val]=this->maxClass-1;
00126         if(tmpClassNumFlag==true)
00127           tmpClassNum[1][this->maxClass]++;
00128       }
00129     }
00130     
00131     bool mooreFirstCutting(Automaton_t * a){
00132       int i;
00133       bool res=true;
00134       for(i=0;i<this->size;i++){
00135         if(a->isFinal(a->getRealValue(i))){
00136           this->partitionRes[i]=0;
00137           insertLastList(&lexicographicalRes,i);
00138         }
00139         else{
00140           this->partitionRes[i]=1;
00141           insertLastList(&lexicographicalTMP,i);
00142         }
00143       }
00144       if(lexicographicalRes->size==0||lexicographicalTMP->size==0){
00145         res=false;
00146         this->maxClass=1;
00147       }
00148       else{
00149         concatList(&lexicographicalRes,&lexicographicalTMP);
00150         this->maxClass=2;
00151       }
00152       return res;
00153     }
00154     
00155     bool sameClass(const int & alphabetSize,const int & state1,const int & state2){
00156       int i;
00157       if(this->partitionRes[state1]!=this->partitionRes[state2])return false;
00158       for(i=0;i<alphabetSize;i++)
00159         if(this->partitionWord[state1][i]!=this->partitionWord[state2][i])
00160           return false;
00161       return true;
00162     }
00163     
00164     bool isPartitionMinimal(){
00165       int i;
00166       for(i=0;i<this->size;i++)
00167         if(this->partitionRes[i]!=this->partitionTmp[i])
00168           return false;
00169       return true;
00170     }
00171     
00172   public:
00173     
00181     int * minimizeToPartition(Automaton_t * a,const int & Mit=-1){
00182       int i;
00183       Alphabet<Sigma> al=a->getAlphabet();
00184       std::list<Sigma> listT=al.getList();
00185       complexity=0;
00186       initPartition(a->getSize(),al.getSize());
00187       complexity++;
00188       if(!mooreFirstCutting(a)){
00189         emptyList(lexicographicalRes);
00190         return this->partitionRes;
00191       }
00192       /*std::cout<<"-----------------------------------"<<std::endl;
00193       for(i=0;i<this->size;i++)
00194       std::cout<<this->partitionRes[i]<<" ";
00195       std::cout<<std::endl;
00196       */
00197       //swapT(this->partitionRes,this->partitionTmp);
00198       while(1){
00199         complexity++;
00200         for(i=0;i<this->size;i++){
00201           for(std::list<char>::iterator l=listT.begin();l!=listT.end();l++)
00202             if(a->getArrivalState((StateLabel_t)i,*l)!=a->undefinedTransition())
00203               partitionWord[i][al.getNumericalValue(*l)]=this->partitionRes[a->getArrivalState((StateLabel_t)i,*l)];
00204             else
00205               partitionWord[i][al.getNumericalValue(*l)]=-1;      
00206         }
00207         sortClasses();
00208         if(tmpClassNumFlag==true)
00209           tmpClassNum[0][complexity-1]=this->maxClass;
00210         
00211         swapT(this->partitionRes,partitionTmp);
00212         /*for(i=0;i<this->size;i++)
00213           std::cout<<this->partitionRes[i]<<" ";
00214         std::cout<<std::endl;
00215         */
00216         if(this->maxClass==a->getSize()||isPartitionMinimal()||((complexity-1)==Mit)){
00217           emptyList(lexicographicalRes);
00218           return this->partitionRes;
00219         }
00220       }
00221       
00222     }
00223 
00230     int ** minimizeSteps(Automaton_t * a,const int & precision=-1){
00231       if(tmpClassNum[0]!=NULL){
00232         delete [] tmpClassNum[0];
00233         delete [] tmpClassNum[1];
00234       }
00235       tmpClassNum[0]=new int[a->getSize()];
00236       tmpClassNum[1]=new int[a->getSize()];
00237       tmpClassNumFlag=true;
00238       minimizeToPartition(a,precision);
00239       tmpClassNumFlag=false;
00240       tmpClassNum[0][0]=complexity;
00241       tmpClassNum[1][0]=this->maxClass;
00242       return tmpClassNum;
00243     }
00244 
00245        
00251     int minimizeSize(Automaton_t * a){
00252       minimizeToPartition(a);
00253       return this->maxClass;
00254     }
00255 
00261     int minimizeComplexity(Automaton_t * a){
00262       minimizeToPartition(a);
00263       return complexity;
00264     }
00265     unsigned int * minimizeMultipleComplexity(Automaton_t * a){
00266       return NULL;
00267     }
00268     
00269 
00275     Automaton_t * minimize(Automaton_t * a){
00276       int i,j;
00277       Alphabet<Sigma> al=a->getAlphabet();
00278       std::list<Sigma> listT=al.getList();
00279       minimizeToPartition(a);
00280 
00281       /*for(i=0;i<a->getSize();i++)
00282         std::cout<<this->partitionRes[i]<<" ";
00283       std::cout<<std::endl;
00284       */
00285       int * viewed=new int[a->getSize()];
00286       int count;
00287       for(i=0;i<a->getSize();i++)
00288         viewed[i]=-1;
00289       for(i=0,count=0;i<a->getSize();i++)
00290         if(viewed[this->partitionRes[i]]==-1)viewed[this->partitionRes[i]]=count++;
00291       //reorderPartition(a->getSize());
00292       
00293       Automaton_t * res=new Automaton_t(this->maxClass,al);
00294       //Transform the partition into an Automaton
00295 
00296       for(i=0;i<this->maxClass;i++)
00297         res->addState();
00298       for(i=0,j=0;i<this->size;i++){
00299         j=viewed[this->partitionRes[i]];
00300         if(a->isInitial(i))
00301           res->setStateAsInitial(j,true);
00302         if(a->isFinal(i))
00303           res->setStateAsFinal(j,true);
00304         for(std::list<char>::iterator l=listT.begin();l!=listT.end();l++)
00305           res->addTransition(viewed[this->partitionRes[i]],viewed[this->partitionRes[a->getArrivalState((StateLabel_t)i,*l)]],*l);
00306         
00307         
00308       }
00309       return res;
00310     }
00311 
00312 
00313     
00314     
00318     MooreAlgorithm(){
00319       this->size=0;
00320       this->partitionRes=NULL;
00321       partitionTmp=NULL;
00322       partitionWord=NULL;
00323       tmpClassNum[0]=NULL;
00324       tmpClassNum[0]=NULL;
00325       tmpClassNumFlag=false;
00326     }
00327     
00331     ~MooreAlgorithm(){
00332       freeMemory();
00333       if(tmpClassNum[0]!=NULL){delete [] tmpClassNum[0];delete [] tmpClassNum[1];}
00334     }
00335     
00336 
00337   };
00338 
00339 }
00340 
00341 
00342 
00343 #endif

Generated on Mon Sep 29 16:33:58 2008 for REGAL by  doxygen 1.5.1