include/StronglyConnected.hpp

Go to the documentation of this file.
00001 // Stronglyconnected.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 STRONGLYCONNECTED_HPP
00017 #define STRONGLYCONNECTED_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 StronglyConnectedTester{
00028     
00029   public:
00030     static bool testConnectability(Automaton_t * a){
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       bool res=true;
00037       std::deque<int> stateStack;
00038       std::list<int> ** reverse=rda.reverseDFA(a);
00039       
00040       for(i=0;i<n;i++)
00041         traversedStates[i]=false;
00042       
00043       stateStack.push_front(0);
00044       traversedStates[0]=true;
00045       while(!stateStack.empty()){
00046         currentList=reverse[stateStack.front()];
00047         stateStack.pop_front();
00048         for(i=0;i<asize;i++){
00049           for(std::list<int>::iterator currentInt=currentList[i].begin();currentInt!=currentList[i].end();currentInt++){
00050             if(!traversedStates[*currentInt]){
00051               traversedStates[*currentInt]=true;
00052               stateStack.push_front(*currentInt);
00053             }
00054           }
00055         }
00056       }  
00057       
00058       for(i=0;i<n;i++)
00059         if(traversedStates[i]==false){
00060           res=false;
00061           break;
00062         }
00063       
00064       delete [] traversedStates;
00065       return res;
00066       
00067     }
00068 
00069   };
00070     
00071 }
00072 
00073 #endif

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