RandomAutomatonFactory.cpp

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

#include "RandomAutomatonFactory.h"
#include <exception/CommonException.h>

#include <algorithm>
#include <random>

#include <registration/AlgoRegistration.hpp>

namespace automaton {

namespace generate {

automaton::NFA < > RandomAutomatonFactory::generateNFA( size_t statesCount, ext::set<DefaultSymbolType> alphabet, double density ) {
	ext::deque<DefaultSymbolType> alphabet2;
	for( const auto & s : alphabet )
		alphabet2.push_back( s );
	return RandomAutomatonFactory::LeslieConnectedNFA( statesCount, alphabet2, density );
}

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

	ext::vector<DefaultSymbolType> symbols;
	for(int i = 0; i < 26; i++) symbols.push_back(DefaultSymbolType((char)(i + 'a')));
	if(randomizedAlphabet) shuffle(symbols.begin(), symbols.end(), ext::random_devices::semirandom);
	ext::deque<DefaultSymbolType> alphabet(symbols.begin(), symbols.begin() + alphabetSize);

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

automaton::NFA < > RandomAutomatonFactory::LeslieConnectedNFA( size_t n, const ext::deque<DefaultSymbolType> & alphabet, double density ) {
	if( alphabet.size( ) <= 0 )
		throw exception::CommonException( "Alphabet size must be greater than 0." );

	ext::deque<bool> VStates;
	ext::deque<DefaultStateType> Q;
	int unvisited;

	automaton::NFA < > automaton( DefaultStateType( 0 ) );

	for( const auto & s : alphabet )
		automaton.addInputSymbol( s );

	for( size_t i = 0; i < n; i ++ ) {
		VStates.push_back( false );
		Q.push_back( DefaultStateType ( (int) i ) );
		automaton.addState( Q[ i ] );
	}

	if( n == 0 ) {
		return automaton;
	} else if( n == 1 ) {
		automaton.addTransition( Q[ 0 ], alphabet[ ext::random_devices::semirandom() % alphabet.size( ) ], Q[ 0 ] );

		unvisited = 0;
		VStates[ 0 ] = true;
	} else {
		int x = ( ext::random_devices::semirandom() % ( n - 1 ) ) + 1;
		automaton.addTransition( Q[ 0 ], alphabet[ ext::random_devices::semirandom() % alphabet.size( ) ], Q[ x ] );
		unvisited = n - 2;

		VStates[ 0 ] = true;
		VStates[ x ] = true;
	}

	while( unvisited != 0 ) {
		size_t y = ext::random_devices::semirandom() % ( n - unvisited ) + 1;	// select y-th accessible state
		size_t z = ext::random_devices::semirandom() % unvisited + 1;		// select z-th inaccessible state
		int a = -1, b = -1;

		for( size_t i = 0, cnt = 0; i < n; i++ ) {
			if( VStates[ i ] == true )
				cnt ++;

			if( cnt == y ) {
				a = i;
				break;
			}
		}
		for( size_t i = 0, cnt = 0; i < n; i++ ) {
			if( VStates[ i ] == false )
				cnt ++;

			if( cnt == z )
			{
				b = i;
				break;
			}
		}

		int c = ext::random_devices::semirandom() % alphabet.size( );
		automaton.addTransition( Q[ a ], alphabet[ c ], Q[ b ] );


		unvisited -= 1;
		VStates[ b ] = true;

		// ---------
	}

	for( const DefaultStateType & q : Q ) {
		if( automaton.getTransitionsFromState( q ).size( ) == 0 && ext::random_devices::semirandom() % 100 < 90 )
			automaton.addFinalState( q );
		else if( automaton.getTransitionsFromState( q ).size( ) > 0 && ext::random_devices::semirandom() % 100 < 10 )
			automaton.addFinalState( q );
	}

	if( automaton.getFinalStates( ).size( ) == 0 ) {
		if( n == 1 ) {
			automaton.addFinalState( automaton.getInitialState( ) );
		} else {
			for( const DefaultStateType & q : Q ) {
				if( automaton.getTransitionsFromState( q ).size( ) == 0 ) {
					automaton.addFinalState( q );
					break;
				}
			}
		}
	}

	double mnn100 = 100.0 / alphabet.size( ) / n / n;
	while( automaton.transitionsSize( ) * mnn100 < density ) {
		int y = ext::random_devices::semirandom() % n;
		int z = ext::random_devices::semirandom() % n;
		int a = ext::random_devices::semirandom() % alphabet.size();

		automaton.addTransition( Q[ y ], alphabet [ a ], Q[ z ] );
	}

	ext::map<DefaultSymbolType, bool> alphabetUsage;
	for( const auto & a : automaton.getInputAlphabet( ) )
		alphabetUsage[ a ] = false;
	for( const auto & t : automaton.getTransitions( ) )
		alphabetUsage[ t.first.second ] = true;

	for( const auto & kv : alphabetUsage )
		if( kv.second == false )
			automaton.removeInputSymbol( kv.first );

	return automaton;
}

auto GenerateNFA = registration::AbstractRegister < RandomAutomatonFactory, automaton::NFA < >, size_t, size_t, bool, double > ( RandomAutomatonFactory::generateNFA, abstraction::AlgorithmCategories::AlgorithmCategory::DEFAULT, "statesCount", "alphabetSize", "randomizedAlphabet", "density" );

} /* namespace generate */

} /* namespace automaton */