include/RandomDFAGenerator.hpp

Go to the documentation of this file.
00001 // RandomDFAGenerator.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 RANDOMDFAGENERATOR
00017 #define RANDOMDFAGENERATOR
00018 
00019 #include "AbstractRandomGenerator.hpp"
00020 #include "AbstractDFAGenerator.hpp"
00021 #include "BoltzmannSampler.hpp"
00022 #include "toolbox/GenericFunction.hpp"
00023 #include "VerboseOption.hpp"
00024 #include "MyMooreAlgorithm.hpp"
00025 #include "StronglyConnected.hpp"
00026 #include "CoAccessible.hpp"
00027 #include "Local.hpp"
00028 
00029 
00030 
00031 namespace regal{
00032   
00033   template<typename StateLabel_t,typename Sigma, class Automaton_t=AbstractAutomaton<StateLabel_t,Sigma> >
00034   class RandomDFAGenerator : 
00035     public AbstractRandomGenerator<Automaton_t>, AbstractDFAGenerator<StateLabel_t,Sigma,Automaton_t>{
00036   private:
00037     BoltzmannSampler * bs; 
00038     int *partBoltzmann; 
00039     int * partMin; 
00040     int * partFinalMemory; 
00041     //int * catS; /*!< CatalanSuit - Word of Dyck : used to create a trie */
00042     //int * comS; /*!< CompletionSuit : used to complete the trie into a DFA */ 
00043     int * permutation; 
00044     int rejectCounters[2];
00045     double probability;
00046     int setSize; 
00047     int subsetNumber; 
00048     int incomplete; 
00053     void sortPartition(){
00054       int i,j;
00055       for(i=0;i<subsetNumber;i++)partMin[i]=-1;
00056 
00057       for(i=0,j=0;i<setSize;i++){
00058         if(partMin[partFinalMemory[i]]==-1)partMin[partFinalMemory[i]]=j++;
00059         partFinalMemory[i]=partMin[partFinalMemory[i]];
00060       }
00061       
00062     }
00063 
00064     
00065     
00069     void printPartition(){
00070       int i;
00071       //std::cout<<"Taille ensemble "<<setSize<<std::endl;
00072       //std::cout<<"Taille des sous ensembles "<<std::endl;
00073       /*for(i=0;i<subsetNumber;i++)
00074         std::cout<<partBoltzmann[i]<<" ";
00075       std::cout<<std::endl;
00076       */
00077       //std::cout<<"Partition"<<std::endl;
00078       for(i=0;i<setSize;i++)
00079         std::cout<<partFinalMemory[i]<<" ";
00080       std::cout<<std::endl;
00081     }
00082     
00089     int * randomPermutation(){
00090       int i,pos;
00091       int * l=permutation;
00092       for(i=0;i<setSize;i++){
00093         pos=rand()%(i+1);
00094         if(pos!=i)
00095           l[i]=l[pos];
00096         l[pos]=i+1;
00097       }
00098       return l;
00099     }
00100     
00107     void randomPartition(){
00108       int i,j,counter,pos;
00109       int * l=randomPermutation();
00110       
00111       partBoltzmann=bs->sample();
00112       
00113       for(pos=0,i=0,counter=0;counter<setSize;i++){
00114         for(j=0;j<partBoltzmann[i];j++,pos++){
00115           partFinalMemory[l[pos]-1]=i;
00116         }
00117         counter+=partBoltzmann[i];
00118       }
00119       sortPartition();
00120       //Adds the last transition without boltzmann to ensure equiprobability that has been
00121       //proved for automatonSize*alphabetSize+1
00122       
00123       //if(incomplete)partFinalMemory[setSize]=rand()%subsetNumber;
00124     }
00125     
00126     
00132     /*void partitionToSuits(){
00133       int i,max=-10,pos=0;
00134       for(i=0;i<setSize;i++){
00135         if(partFinalMemory[i]>max)max=partFinalMemory[i];
00136         else{
00137           comS[pos]=partFinalMemory[i]+1;
00138           catS[pos]=max+1;
00139           pos++;
00140         }
00141       }
00142 
00143       }*/
00144     
00148     void randomFinalization(){
00149       int i;
00150       StateLabel_t state;
00151       for(i=0;i<this->result->getSize();i++){
00152         state=this->result->getRealValue(i);
00153         
00154         if(((rand()%RAND_MAX)/(double)RAND_MAX)<probability)
00155           this->result->setStateAsFinal(state,true);
00156         else
00157           this->result->setStateAsFinal(state,false);
00158       }
00159     }
00160     
00161     
00165     void onlyOneFinalState(){
00166       int i;
00167       StateLabel_t state;
00168       for(i=0;i<this->result->getSize();i++){
00169         state=this->result->getRealValue(i);
00170         this->result->setStateAsFinal(state,false);
00171       }
00172       this->result->setStateAsFinal(this->result->getRealValue(rand()%this->result->getSize()),true);
00173     }
00174     
00175 
00179     void randomUnfinalizedDFA(){
00180       rejectCounters[1]=0;
00181       do{
00182         randomPartition();
00183         //partitionToSuits();
00184         rejectCounters[1]++;
00185         //printPartition();
00186       }
00187       //while(!this->isACatalanSuit(catS,incomplete));
00188       while(!this->isAValidSetPartition(partFinalMemory,incomplete));
00189 #ifdef __REJECTFLAG
00190       std::cout<<"Nombre de rejet : "<<rejectCounters[1]<<std::endl;
00191 #endif 
00192  
00193       this->setToDFA(partFinalMemory,incomplete);
00194       //this->suitToDFA(catS,comS,incomplete);
00195       //std::cout<<*this->result<<std::endl;
00196     }
00197 
00198 
00199     bool isMinimal(Automaton_t * a){
00200       int i,max=0,size=a->getSize();
00201       bool zero=false;
00202       MyMooreAlgorithm<int,char,Automaton_t > ma;
00203       int * partition=ma.minimizeToPartition(a);
00204       for(i=0;i<size;i++){
00205         if(partition[i]>max)
00206           max=partition[i];
00207         zero=(partition[i]==0)?true:false;
00208       }
00209       if(max==(size-1)&&zero)
00210         return true;
00211       return false;
00212     }
00213 
00214     
00215   public:
00216     
00221     Automaton_t * random(){
00222       randomUnfinalizedDFA();
00223       randomFinalization();
00224       return this->result;
00225     }
00226     
00231     Automaton_t * randomMinimal(){
00232       do{
00233         random();
00234       }while(!isMinimal(this->result));
00235       return this->result;
00236     }
00237 
00242     Automaton_t * randomStronglyConnected(){
00243       do{
00244         random();
00245       }while(!StronglyConnectedTester<StateLabel_t,Sigma,Automaton_t>::testConnectability(this->result));
00246       return this->result;
00247     }
00248 
00253     Automaton_t * randomLocal(){
00254       do{
00255         randomStronglyConnected();
00256       }while(!LocalTester<StateLabel_t,Sigma,Automaton_t>::locality(this->result));
00257       return this->result;
00258     }
00259 
00260     
00261     
00266     Automaton_t * randomCoAccessible(){
00267       do{
00268         random();
00269       }while(!CoAccessibleTester<StateLabel_t,Sigma,Automaton_t>::testCoAccessibility(this->result));
00270       return this->result;
00271     }
00272 
00277     Automaton_t * randomOneFinalState(){
00278       randomUnfinalizedDFA();
00279       onlyOneFinalState();
00280       return this->result;
00281     }
00282 
00287     int * getRejectCounters(){
00288       rejectCounters[0]=bs->getRejectCounter();
00289       return rejectCounters;
00290     }
00291     
00298     RandomDFAGenerator(const int & autSize,const Alphabet<Sigma> & alpha,const double & prob=0.5,const bool & c=false):
00299       AbstractDFAGenerator<StateLabel_t,Sigma,Automaton_t>::AbstractDFAGenerator(autSize,alpha){
00300       incomplete=(c)?1:0;
00301       setSize=autSize*alpha.getSize()+1;
00302       subsetNumber=autSize+incomplete;
00303       bs=new BoltzmannSampler(setSize,subsetNumber);
00304       //catS=new int[autSize*(alpha.getSize()-1)+1];
00305       //comS=new int[autSize*(alpha.getSize()-1)+1];
00306       permutation=new int[setSize];
00307       partMin=new int[subsetNumber];
00308       partFinalMemory=new int[setSize];
00309       probability=prob;
00310       verbose("Creation of the RandomDFAGenerator");
00311     }
00312     
00313     
00317     ~RandomDFAGenerator(){
00318       delete bs;
00319       //delete [] catS;
00320       //delete [] comS;
00321       delete [] permutation;
00322       delete [] partFinalMemory;
00323       delete [] partMin;
00324       verbose("Destruction of the RandomDFAGenerator");
00325       
00326     }
00327     
00328   };
00329 
00330 }
00331 
00332 #endif

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