RandomAutomatonFactory.cpp

/*
 * RandomAutomatonFactory.cpp
 *
 *  Created on: 27. 3. 2014
 *	  Author: Tomas Pecka
 */

#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 ) {
	if(alphabetSize > 26)
		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 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 ] == true )
			i --;

		if( i == 0 )
			return i;
	}
	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 ] == false )
			i --;

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

auto GenerateNFA1 = registration::AbstractRegister < RandomAutomatonFactory, automaton::NFA < DefaultSymbolType, unsigned >, size_t, const ext::set < DefaultSymbolType > &, double > ( 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\n\
@return random nondeterministic finite automaton" );

auto GenerateNFA2 = registration::AbstractRegister < RandomAutomatonFactory, automaton::NFA < std::string, unsigned >, size_t, size_t, bool, double > ( 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-1). 1 means every possible transition is created\n\
@return random nondeterministic finite automaton" );

} /* namespace generate */

} /* namespace automaton */