RandomAutomatonFactory.cpp

#include "RandomAutomatonFactory.h"
#include <registration/AlgoRegistration.hpp>

namespace automaton {

namespace generate {

automaton::NFA < std::string, unsigned > RandomAutomatonFactory::generateNFA( size_t statesCount, size_t alphabetSize, bool randomizedAlphabet, double density ) {
	constexpr size_t ENGLISH_ALPHABET_SIZE = 26;
	if(alphabetSize > ENGLISH_ALPHABET_SIZE)
		throw exception::CommonException("Too big alphabet.");

	ext::deque < std::string > alphabet;
	for(char i = 'a'; i <= 'z'; i++)
		alphabet.push_back ( std::string ( 1, i ) );

	if(randomizedAlphabet)
		shuffle(alphabet.begin(), alphabet.end(), ext::random_devices::semirandom);

	alphabet.resize ( alphabetSize );

	return automaton::generate::RandomAutomatonFactory::LeslieConnectedNFA( statesCount, alphabet, density );
}

unsigned RandomAutomatonFactory::ithAccessibleState ( const ext::deque < bool > & VStates, size_t i ) {
	i ++;
	for( size_t j = 0; j < VStates.size ( ); j++ ) {
		if( VStates[ j ] )
			i --;

		if( i == 0 )
			return j;
	}
	throw std::logic_error ( "Not enough states in deque of visited states" );
}

unsigned RandomAutomatonFactory::ithInaccessibleState ( const ext::deque < bool > & VStates, size_t i ) {
	i ++;
	for( size_t j = 0; j < VStates.size ( ); j++ ) {
		if( ! VStates[ j ] )
			i --;

		if( i == 0 )
			return j;
	}
	throw std::logic_error ( "Not enough states in deque of visited states" );
}

} /* namespace generate */

} /* namespace automaton */

namespace {

auto GenerateNFA1 = registration::AbstractRegister < automaton::generate::RandomAutomatonFactory, automaton::NFA < DefaultSymbolType, unsigned >, size_t, const ext::set < DefaultSymbolType > &, double > ( automaton::generate::RandomAutomatonFactory::generateNFA, abstraction::AlgorithmCategories::AlgorithmCategory::DEFAULT, "statesCount", "alphabet", "density" ).setDocumentation (
"Generates a random finite automaton.\n\
@param statesCount number of states in the generated automaton\n\
@param alphabet Input alphabet of the automaton\n\
@param density density of the transition function (0-100)\n\
@return random nondeterministic finite automaton" );

auto GenerateNFA2 = registration::AbstractRegister < automaton::generate::RandomAutomatonFactory, automaton::NFA < std::string, unsigned >, size_t, size_t, bool, double > ( automaton::generate::RandomAutomatonFactory::generateNFA, abstraction::AlgorithmCategories::AlgorithmCategory::DEFAULT, "statesCount", "alphabetSize", "randomizedAlphabet", "density" ).setDocumentation (
"Generates a random finite automaton.\n\
\n\
@param statesCount number of states in the generated automaton\n\
@param alphabetSize size of the alphabet (1-26)\n\
@param randomizedAlphabet selects random symbols from a-z range if true\n\
@param density density of the transition function (0-100). 100 means every possible transition is created\n\
@return random nondeterministic finite automaton" );

} /* namespace */