include/RandomTreeAutomatonGenerator.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 RANDOMTREEAUTOMATONGENERATOR
00017 #define RANDOMTREEAUTOMATONGENERATOR
00018 
00019 #include "AbstractRandomGenerator.hpp"
00020 #include "AbstractAutomaton.hpp"
00021 #include "toolbox/GenericFunction.hpp"
00022 #include "VerboseOption.hpp"
00023 
00024 
00025 
00026 namespace regal{  
00027 
00028   template<typename StateLabel_t,typename Sigma, class Automaton_t=AbstractAutomaton<StateLabel_t,Sigma> >
00029   class RandomTreeAutomatonGenerator : 
00030     public AbstractRandomGenerator<Automaton_t>{
00031   private:
00032 
00033     StateLabel_t * randomMap_state;
00034     Sigma * randomMap_letter;
00035     int size,asize;
00036     Alphabet<Sigma> alphabet;
00037     Automaton_t * result;
00038     double probability;
00039 
00040     
00041     void reinitTransitions(){
00042       std::list<Sigma> listT=alphabet.getList();
00043       typename std::list<Sigma>::iterator l;
00044       for(int i=0;i<size;i++)
00045         for(l=listT.begin();l!=listT.end();l++)
00046           result->addTransition(result->getRealValue(i),result->getRealValue(-1),*l);
00047       
00048     }
00049 
00053     void randomFinalization(){
00054       int i;
00055       StateLabel_t state;
00056       for(i=0;i<size;i++){
00057         state=result->getRealValue(i);
00058         
00059         if(((rand()%RAND_MAX)/(double)RAND_MAX)<probability)
00060           result->setStateAsFinal(state,true);
00061         else
00062           result->setStateAsFinal(state,false);
00063       }
00064     }
00065     
00066   public:
00067     
00068 
00069 
00070     Automaton_t * random(){
00071       std::list<Sigma> listT=alphabet.getList();
00072       typename std::list<Sigma>::iterator l;
00073       int randomValue,i,j;
00074 
00075       reinitTransitions();
00076 
00077       for(j=0,l=listT.begin();l!=listT.end();l++,j++){ 
00078         randomMap_state[j]=result->getRealValue(0);
00079         randomMap_letter[j]=*l;
00080       }
00081 
00082       for(i=1;i<size;i++){
00083         randomValue=rand()%((asize-1)*i+1);
00084         result->addTransition(randomMap_state[randomValue],result->getRealValue(i),randomMap_letter[randomValue]);
00085         
00086         l=listT.begin();
00087         
00088         randomMap_state[randomValue]=result->getRealValue(i);
00089         randomMap_letter[randomValue]=*l;
00090         for(j=0,l++;l!=listT.end();l++,j++){ 
00091           randomMap_state[(asize-1)*i+1+j]=result->getRealValue(i);
00092           randomMap_letter[(asize-1)*i+1+j]=*l;
00093         }
00094       }
00095 
00096       randomFinalization();
00097       return result;
00098     }
00099 
00100     RandomTreeAutomatonGenerator(const int & autSize,const Alphabet<Sigma> & alpha,
00101                                  const double & prob=0.5):alphabet(alpha){
00102       int i;
00103       time_t t;
00104       srand(time(&t));
00105       size=autSize;
00106       probability=prob;
00107       asize=alphabet.getSize();
00108       randomMap_state=new StateLabel_t[(asize-1)*size+1];
00109       randomMap_letter=new Sigma[(asize-1)*size+1];
00110       result=new Automaton_t(size,alphabet);
00111       for(i=0;i<size;i++)
00112         result->addState();
00113     }
00114 
00115     ~RandomTreeAutomatonGenerator(){
00116       delete [] randomMap_state;
00117       delete [] randomMap_letter;
00118       delete result;
00119     }
00120     
00121 
00122   };
00123 
00124 }
00125 
00126 #endif

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