include/CoAccessible.hpp

Go to the documentation of this file.
00001 // CoAccessible.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 COACCESSIBLE_HPP
00017 #define COACCESSIBLE_HPP
00018 
00019 #include<iostream>
00020 #include<list>
00021 #include<deque>
00022 #include "ReverseDFAAlgorithm.hpp"
00023 
00024 namespace regal{
00025   
00026   template<typename StateLabel_t,typename Sigma,class Automaton_t=AbstractAutomaton<StateLabel_t,Sigma> >
00027   class CoAccessibleTester{
00028     
00029   public:
00030     static bool testCoAccessibility(Automaton_t * a,const int* states=NULL,const int & num=-1){
00031       int n=a->getSize(),i;
00032       int asize=a->getAlphabetSize();
00033       std::list<int> * currentList;
00034       ReverseDFAAlgorithm<StateLabel_t,Sigma,Automaton_t> rda;
00035       bool * traversedStates=new bool[n];
00036       std::deque<int> stateStack;
00037       std::list<int> ** reverse=rda.reverseDFA(a);
00038       
00039       for(i=0;i<n;i++){
00040         if(a->isFinal(a->getRealValue(i))){
00041           stateStack.push_front(i);
00042           traversedStates[i]=true;
00043         }
00044         else
00045           traversedStates[i]=false;
00046       }
00047       
00048       while(!stateStack.empty()){
00049         currentList=reverse[stateStack.front()];
00050         stateStack.pop_front();
00051         for(i=0;i<asize;i++){
00052           for(std::list<int>::iterator currentInt=currentList[i].begin();currentInt!=currentList[i].end();currentInt++){
00053             if(!traversedStates[*currentInt]){
00054               traversedStates[*currentInt]=true;
00055               stateStack.push_front(*currentInt);
00056             }
00057           }
00058         }
00059       }
00060       
00061       if(num==-1){
00062         for(i=0;i<n;i++)
00063           if(traversedStates[i]==false){
00064             delete [] traversedStates;
00065             return false;
00066           }
00067       }
00068       else{
00069         for(i=0;i<num;i++){
00070           if(traversedStates[states[i]]==false){
00071             delete [] traversedStates;
00072             return false;
00073         }
00074         }
00075       }
00076       delete [] traversedStates;
00077       return true;
00078     }
00079     
00080     
00081   };
00082 
00083 }
00084 
00085 #endif

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