RandomAutomatonFactory.h

Go to the documentation of this file.

 
/*
 * This file is part of Algorithms library toolkit.
 * Copyright (C) 2017 Jan Travnicek (jan.travnicek@fit.cvut.cz)
 
 * Algorithms library toolkit is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 
 * Algorithms library toolkit is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 
 * You should have received a copy of the GNU General Public License
 * along with Algorithms library toolkit.  If not, see <http://www.gnu.org/licenses/>.
 */
 
#pragma once
 
#include <ext/algorithm>
#include <ext/random>
 
#include <alib/deque>
#include <alib/set>
#include <alib/string>
 
#include <exception/CommonException.h>
 
#include <automaton/FSM/NFA.h>
 
namespace automaton {
 
namespace generate {
 
class RandomAutomatonFactory {
public:
    template < class SymbolType >
    static automaton::NFA < SymbolType, unsigned > generateNFA ( size_t statesCount, const ext::set < SymbolType > & alphabet, double density );
 
    static automaton::NFA < std::string, unsigned > generateNFA ( size_t statesCount, size_t alphabetSize, bool randomizedAlphabet, double density );
 
private:
    static unsigned ithAccessibleState ( const ext::deque < bool > & VStates, size_t i );
 
    static unsigned ithInaccessibleState ( const ext::deque < bool > & VStates, size_t i );
 
    template < class SymbolType >
    static automaton::NFA < SymbolType, unsigned > LeslieConnectedNFA ( size_t n, const ext::deque < SymbolType > & alphabet, double density );
};
 
template < class SymbolType >
automaton::NFA < SymbolType, unsigned > RandomAutomatonFactory::generateNFA ( size_t statesCount, const ext::set < SymbolType > & alphabet, double density ) {
    ext::deque < SymbolType > alphabet2 ( alphabet.begin ( ), alphabet.end ( ) );
    return RandomAutomatonFactory::LeslieConnectedNFA ( statesCount, alphabet2, density );
}
 
template < class SymbolType >
automaton::NFA < SymbolType, unsigned > RandomAutomatonFactory::LeslieConnectedNFA ( size_t n, const ext::deque < SymbolType > & alphabet, double density ) {
    if( alphabet.empty ( ) )
        throw exception::CommonException( "Alphabet size must be greater than 0." );
 
    ext::deque<bool> VStates;
    ext::deque<unsigned> Q;
    size_t unvisited;
 
    automaton::NFA < SymbolType, unsigned > automaton( 0 );
 
    for( const auto & s : alphabet )
        automaton.addInputSymbol( s );
 
    for( size_t i = 0; i < n; i ++ ) {
        VStates.push_back( false );
        Q.push_back( 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 {
        unsigned 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 a = ithAccessibleState ( VStates, ext::random_devices::semirandom() % ( n - unvisited ) );   // select y-th accessible state
        size_t b = ithInaccessibleState ( VStates, ext::random_devices::semirandom() % unvisited );     // select z-th inaccessible state
 
        int c = ext::random_devices::semirandom() % alphabet.size( );
        automaton.addTransition( Q[ a ], alphabet[ c ], Q[ b ] );
 
        unvisited -= 1;
        VStates[ b ] = true;
    }
 
    for( const unsigned & q : Q ) {
        if( automaton.getTransitionsFromState( q ).empty ( ) && ext::random_devices::semirandom() % 100 < 90 )
            automaton.addFinalState( q );
        else if( !automaton.getTransitionsFromState( q ).empty ( ) && ext::random_devices::semirandom() % 100 < 10 )
            automaton.addFinalState( q );
    }
 
    if( automaton.getFinalStates( ).empty ( ) ) {
        if( n == 1 ) {
            automaton.addFinalState( automaton.getInitialState( ) );
        } else {
            for( const unsigned & q : Q ) {
                if( automaton.getTransitionsFromState( q ).empty ( ) ) {
                    automaton.addFinalState( q );
                    break;
                }
            }
        }
    }
 
    double mnn100 = 100.0 / alphabet.size( ) / n / n;
    while( automaton.getTransitions ( ).size ( ) * 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::set < SymbolType > alphabetUsage = automaton.getInputAlphabet ( );
    for ( const auto & t : automaton.getTransitions ( ) )
        alphabetUsage.erase ( t.first.second );
 
    for ( const auto & kv : alphabetUsage )
        automaton.removeInputSymbol ( kv );
 
    return automaton;
}
 
} /* namespace generate */
 
} /* namespace automaton */