include/MyMooreAlgorithm.hpp

Go to the documentation of this file.
00001 // MyMooreAlgorithm.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 MYMOOREALGORITHM
00017 #define MYMOOREALGORITHM
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 MyMooreAlgorithm: public MinimizingAlgorithm<StateLabel_t,Sigma,Automaton_t>{
00029   private:
00030     int *partitionTmp;
00031     int ** partitionWord;
00032     int complexity; 
00033     int aSize; 
00034     List_t ** lexicographical;
00035     List_t * lexicographicalRes;
00036     List_t * lexicographicalTMP;
00037     List_t * lexicographicalUndividable;
00038  
00039     void freeMemory(){
00040       if(this->partitionRes!=NULL)delete [] this->partitionRes;
00041       if(partitionTmp!=NULL)delete [] partitionTmp;
00042       if(partitionWord!=NULL){
00043         for(int i=0;i<this->size;i++){
00044           delete [] partitionWord[i];
00045           destroyList(lexicographical[i]);
00046         }
00047         free(lexicographical);
00048         destroyList(lexicographicalRes);
00049         destroyList(lexicographicalTMP);
00050         destroyList(lexicographicalUndividable);
00051         delete [] partitionWord;
00052       }
00053     }
00054     
00055     void initPartition(const int & s,const int & as){
00056       if(s!=this->size){
00057         freeMemory();
00058         this->size=s;
00059         aSize=as;
00060         this->partitionRes=new int[this->size];
00061         partitionTmp=new int[this->size];
00062         partitionWord=new int*[this->size];
00063         lexicographical=(List_t **)malloc(sizeof(List_t *)*s);
00064         for(int i=0;i<this->size;i++){
00065           partitionWord[i]=new int[as];
00066           lexicographical[i]=createList();
00067         }
00068         lexicographicalTMP=createList();
00069         lexicographicalRes=createList();
00070         lexicographicalUndividable=createList();
00071       }
00072     }
00073     
00074     void lexicographicalSort(const int & prof){
00075       doubleChainedList_t * tmp;
00076       while(lexicographicalRes->first!=NULL){
00077         tmp=extractFirstList(&lexicographicalRes);
00078         if(prof==0)
00079           insertNodeLastList(&lexicographical[this->partitionRes[tmp->val]],tmp);
00080         else
00081           insertNodeLastList(&lexicographical[this->partitionWord[tmp->val][prof-1]],tmp);
00082       }
00083       for(int i=0;i<this->maxClass;i++)
00084         concatList(&lexicographicalRes,&lexicographical[i]);    
00085     }
00086     
00087     void sortClasses(){
00088       doubleChainedList_t * tmp,*tmp2;
00089       for(int i=aSize;i>=0;i--)
00090         lexicographicalSort(i);
00091       this->maxClass=0;
00092       
00093       for(tmp=lexicographicalUndividable->first;tmp!=NULL;tmp=tmp->next)
00094         partitionTmp[tmp->val]=this->maxClass++;
00095 
00096       tmp2=extractFirstList(&lexicographicalRes);
00097       
00098       partitionTmp[tmp2->val]=this->maxClass++;
00099       insertNodeLastList(&lexicographicalUndividable,tmp2);
00100 
00101       while(lexicographicalRes->first!=NULL){
00102         tmp=extractFirstList(&lexicographicalRes);
00103         if(!sameClass(aSize,tmp->val,tmp2->val)){
00104           partitionTmp[tmp->val]=this->maxClass++;
00105           insertNodeLastList(&lexicographicalUndividable,tmp);
00106         }
00107         else{
00108           partitionTmp[tmp->val]=partitionTmp[tmp2->val];
00109           if(lexicographicalUndividable->last!=NULL&&lexicographicalUndividable->last->val==tmp2->val)
00110             insertNodeLastList(&lexicographicalTMP,extractLastList(&lexicographicalUndividable));
00111           insertNodeLastList(&lexicographicalTMP,tmp);
00112         }
00113         tmp2=tmp;
00114       }
00115 
00116       concatList(&lexicographicalRes,&lexicographicalTMP);
00117 
00118     }
00119     
00120     bool mooreFirstCutting(Automaton_t * a){
00121       int i;
00122       bool res=true;
00123       for(i=0;i<this->size;i++){
00124         if(a->isFinal(a->getRealValue(i))){
00125           this->partitionRes[i]=0;
00126           insertLastList(&lexicographicalRes,i);
00127         }
00128         else{
00129           this->partitionRes[i]=1;
00130           insertLastList(&lexicographicalTMP,i);
00131         }
00132       }
00133       if(lexicographicalRes->size==0||lexicographicalTMP->size==0)
00134         res=false;
00135       else if(lexicographicalRes->size==1){
00136         concatList(&lexicographicalUndividable,&lexicographicalRes);
00137         concatList(&lexicographicalRes,&lexicographicalTMP);
00138       }
00139       else if(lexicographicalTMP->size==1)
00140         concatList(&lexicographicalUndividable,&lexicographicalTMP);
00141       else
00142         concatList(&lexicographicalRes,&lexicographicalTMP);
00143       this->maxClass=2;
00144       
00145       return res;
00146     }
00147     
00148     bool sameClass(const int & alphabetSize,const int & state1,const int & state2){
00149       int i;
00150       if(this->partitionRes[state1]!=this->partitionRes[state2])return false;
00151       for(i=0;i<alphabetSize;i++)
00152         if(partitionWord[state1][i]!=partitionWord[state2][i])
00153           return false;
00154       return true;
00155     }
00156     
00157     bool isPartitionMinimal(){
00158       int i;
00159       for(i=0;i<this->size;i++)
00160         if(this->partitionRes[i]!=partitionTmp[i])
00161           return false;
00162       return true;
00163     }
00164     
00165   public:
00166     
00173     int * minimizeToPartition(Automaton_t * a,const int & it=-1){
00174       doubleChainedList_t * tmp;
00175       Alphabet<Sigma> al=a->getAlphabet();
00176       std::list<Sigma> listT=al.getList();
00177       initPartition(a->getSize(),al.getSize());
00178       complexity++;
00179       if(!mooreFirstCutting(a)){
00180         emptyList(lexicographicalRes);
00181         emptyList(lexicographicalTMP);
00182         return this->partitionRes;
00183       }
00184       while(1){
00185         complexity++;
00186         for(tmp=lexicographicalRes->first;tmp!=NULL;tmp=tmp->next){
00187           for(std::list<char>::iterator l=listT.begin();l!=listT.end();l++)
00188             partitionWord[tmp->val][al.getNumericalValue(*l)]=
00189               this->partitionRes[a->getArrivalState((StateLabel_t)tmp->val,*l)];
00190         }
00191         
00192         sortClasses();
00193         swapT(this->partitionRes,partitionTmp);
00194         if(lexicographicalRes->size==0||isPartitionMinimal()){
00195           emptyList(lexicographicalRes);
00196           emptyList(lexicographicalUndividable);
00197           return this->partitionRes;
00198         }
00199         
00200       }
00201       
00202     }
00203     
00204 
00210     int minimizeSize(Automaton_t * a){
00211       minimizeToPartition(a);
00212       return this->maxClass;
00213     }
00214 
00220     int minimizeComplexity(Automaton_t * a){
00221       complexity=0;
00222       minimizeToPartition(a);
00223       return complexity;
00224     }
00225 
00226     
00227     unsigned int * minimizeMultipleComplexity(Automaton_t * a){
00228       return NULL;
00229     }
00230     
00231 
00232 
00238     Automaton_t * minimize(Automaton_t * a){
00239       int i,j;
00240       Alphabet<Sigma> al=a->getAlphabet();
00241       std::list<Sigma> listT=al.getList();
00242       minimizeToPartition(a);
00243 
00244       /*for(i=0;i<a->getSize();i++)
00245         std::cout<<this->partitionRes[i]<<" ";
00246       std::cout<<std::endl;
00247       */
00248       int * viewed=new int[a->getSize()];
00249       int count;
00250       for(i=0;i<a->getSize();i++)
00251         viewed[i]=-1;
00252       for(i=0,count=0;i<a->getSize();i++)
00253         if(viewed[this->partitionRes[i]]==-1)viewed[this->partitionRes[i]]=count++;
00254       //reorderPartition(a->getSize());
00255       
00256       Automaton_t * res=new Automaton_t(this->maxClass,al);
00257       //Transform the partition into an Automaton
00258 
00259       for(i=0;i<this->maxClass;i++)
00260         res->addState();
00261       for(i=0,j=0;i<this->size;i++){
00262         j=viewed[this->partitionRes[i]];
00263         if(a->isInitial(i))
00264           res->setStateAsInitial(j,true);
00265         if(a->isFinal(i))
00266           res->setStateAsFinal(j,true);
00267         for(std::list<char>::iterator l=listT.begin();l!=listT.end();l++)
00268           res->addTransition(viewed[this->partitionRes[i]],viewed[this->partitionRes[a->getArrivalState((StateLabel_t)i,*l)]],*l);
00269         
00270         
00271       }
00272       return res;
00273     }
00274 
00275 
00276 
00280     MyMooreAlgorithm(){
00281       this->size=0;
00282       this->partitionRes=NULL;
00283       partitionTmp=NULL;
00284       partitionWord=NULL;
00285     }
00286     
00290     ~MyMooreAlgorithm(){
00291       freeMemory();
00292     }
00293     
00294 
00295   };
00296 
00297 }
00298 
00299 
00300 
00301 #endif

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