RandomAutomatonFactory.cpp

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

#include "RandomAutomatonFactory.h"
#include <automaton/Automaton.h>

#include <algorithm>

namespace automaton {

namespace generate {

automaton::NFA RandomAutomatonFactory::generateNFA( size_t statesCount, std::set<alphabet::Symbol> alphabet, double density ) {
	std::deque<alphabet::Symbol> 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, double density ) {
	srand( time( NULL ) );

	if(alphabetSize > 26)
		throw exception::AlibException("Too big alphabet.");

	std::deque<alphabet::Symbol> alphabet;
	while( alphabet.size( ) < alphabetSize ) {
		std::string s( 1, rand() % 26 + 'a' );
		alphabet::Symbol symbol = alphabet::symbolFrom (s);
		if( std::find( alphabet.begin( ), alphabet.end( ), symbol ) == alphabet.end( ) )
			alphabet.push_back( symbol );
	}

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

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

	srand( time( NULL ) );

	std::deque<bool> VStates;
	std::deque<automaton::State> Q;
	int unvisited;

	automaton::NFA automaton( automaton::State( 0 ) );

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

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

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

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

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

	while( unvisited != 0 ) {
		size_t y = rand() % ( n - unvisited ) + 1;	// select y-th   accessible state
		size_t z = rand() % 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 = rand() % alphabet.size( );
		automaton.addTransition( Q[ a ], alphabet[ c ], Q[ b ] );


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

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

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

	if( automaton.getFinalStates( ).size( ) == 0 ) {
		if( n == 1 ) {
			automaton.addFinalState( automaton.getInitialState( ) );
		} else {
			for( automaton::State const& 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 = rand( ) % n;
		int z = rand( ) % n;
		int a = rand( ) % alphabet.size();

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

	std::map<alphabet::Symbol, 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;
}

} /* namespace generate */

} /* namespace automaton */