include/Local.hpp

Go to the documentation of this file.
00001 // Local.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 LOCAL_HPP
00017 #define LOCAL_HPP
00018 
00019 #include<iostream>
00020 #include<list>
00021 #include<deque>
00022 #include "DFAAutomaton.hpp"
00023 #include "ReverseDFAAlgorithm.hpp"
00024 #include "Pair.hpp"
00025 
00026 
00027 namespace regal{
00028 
00029   template<typename StateLabel_t,typename Sigma,class Automaton_t=AbstractAutomaton<StateLabel_t,Sigma> >
00030   class LocalTester{
00031   private:
00032 
00033     static int sum(const int & n){
00034       int res=0;
00035       for(int i=1;i<=n;i++){
00036         res+=i;
00037       }
00038       return res;
00039     }
00040 
00041     static bool testCycleRec(DFAAutomaton<Pair<StateLabel_t,StateLabel_t> ,Sigma> *a,Pair<int,int> p, int * tab){
00042       std::list<Sigma> listT=a->getAlphabet().getList();
00043       int tmpState;
00044       Pair<int,int> tmpPair;
00045       for(typename std::list<Sigma>::reverse_iterator l=listT.rbegin();l!=listT.rend();l++){
00046         tmpPair=a->getArrivalState(p,*l);
00047         tmpState=a->getIntegerValue(tmpPair);
00048         if(tab[tmpState]==1)
00049           return false;
00050         else if(!tab[tmpState]){
00051           tab[tmpState]=1;
00052           if(!testCycleRec(a,tmpPair,tab))
00053              return false;
00054           tab[tmpState]=2;
00055         }
00056       }
00057       return true;
00058     }
00059 
00060     /*
00061       Test if there is a cycle in the not-diagonal subset of P(A),
00062       meaning the states (p,q) such as p!=q.
00063       If there is no cycle, the automaton A is local.
00064       @param a the automaton P(A)
00065       @return true there is no cycle, false therefore
00066     */
00067     static bool testCyclesInPairAutomaton(DFAAutomaton<Pair<StateLabel_t,StateLabel_t> ,Sigma> *a){
00068       Pair<int,int> p;
00069       int i,size=a->getSize();
00070       int * tab=new int[size];
00071       for(i=0;i<size;i++){
00072         if(!tab[i]){
00073           p=a->getRealValue(i);
00074           tab[i]=1;
00075           if(!testCycleRec(a,p,tab)){
00076             delete [] tab;
00077             return false;
00078           }
00079           tab[i]=2;
00080         }
00081       }
00082       delete [] tab;
00083       return true; 
00084     }
00085 
00086 
00087     /* Build the automaton P(A) with the following rules:
00088        ((p,q),a,(r,s)) is a transition in P(A) if and only if
00089        (p,a,r) and (q,a,s) are transitions in A.
00090        The state (p,q) is equal to (q,p) -> we'll sort the values
00091        in the lexicographic order.
00092        @param a is the automaton to transform
00093        @Return P(A).
00094     */
00095     static DFAAutomaton<Pair<StateLabel_t,StateLabel_t> ,Sigma> * makePairAutomaton(Automaton_t * a){
00096       int size=a->getSize();
00097       int sumA=sum(size);
00098       std::list<Sigma> listT=a->getAlphabet().getList();
00099       Pair<StateLabel_t,StateLabel_t> p,p2;
00100       DFAAutomaton<Pair<StateLabel_t,StateLabel_t> ,Sigma> * pa=
00101         new DFAAutomaton<Pair<StateLabel_t,StateLabel_t> ,Sigma>(sumA,a->getAlphabet());
00102       for(p.first=0;p.first<size;p.first++)
00103         for(p.second=p.first;p.second<size;p.second++)
00104           pa->addState(p);
00105 
00106       for(p.first=0;p.first<size;p.first++)
00107         for(p.second=p.first;p.second<size;p.second++){
00108           for(typename std::list<Sigma>::reverse_iterator l=listT.rbegin();l!=listT.rend();l++){
00109             p2.first=a->getArrivalState(p.first,*l);
00110             p2.second=a->getArrivalState(p.second,*l);
00111             pa->addTransition(p,p2,*l);
00112           }
00113         }
00114       return pa;
00115     }
00116 
00117 
00118   public:
00119 
00120     /*
00121       Returns true if a is local, false otherwise.
00122       @param a is the automaton which we want to test
00123       @Return true if a is local, false otherwise.
00124     */
00125     static bool testLocality(Automaton_t * a){
00126       DFAAutomaton<Pair<StateLabel_t,StateLabel_t> ,Sigma> * pairA=makePairAutomaton(a);
00127       bool res=testCyclesInPairAutomaton(pairA);
00128       delete pairA;
00129       return res;
00130     }
00131 
00132   };
00133     
00134 }
00135 
00136 #endif

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