RandomAutomatonFactory2.h

Go to the documentation of this file.

 
#pragma once
 
#include <ext/algorithm>
#include <ext/random>
 
#include <alib/deque>
#include <alib/set>
 
#include <exception/CommonException.h>
 
#include <automaton/FSM/DFA.h>
 
namespace automaton {
 
namespace generate {
 
class RandomAutomatonFactory2 {
public:
    template < class SymbolType >
    static automaton::DFA < SymbolType, unsigned > generateDFA ( size_t statesMinimal, size_t statesDuplicates, size_t statesUnreachable, size_t statesUseless, ext::set < SymbolType> alphabet, double density );
    static automaton::DFA < std::string, unsigned > generateDFA ( size_t statesMinimal, size_t statesDuplicates, size_t statesUnreachable, size_t statesUseless, size_t alphabetSize, bool randomizedAlphabet, double density );
 
private:
    static size_t randomSourceState ( size_t statesMinimal, size_t visited, size_t depleted, const ext::deque < bool > & VStates, const ext::deque < bool > & DStates );
    static size_t randomTargetState ( size_t statesMinimal, size_t visited, const ext::deque < bool > & VStates );
    template < class SymbolType >
    static size_t randomSymbol ( unsigned sourceState, const ext::deque < SymbolType > & alphabet, const automaton::DFA < SymbolType, unsigned > & automaton );
    template < class SymbolType >
    static void addTransition ( automaton::DFA < SymbolType, unsigned > & automaton, unsigned source, SymbolType symbol, unsigned target, const ext::deque < ext::vector < unsigned > > & duplicates );
    template < class SymbolType >
    static automaton::DFA < SymbolType, unsigned > NonminimalDFA( size_t statesMinimal, size_t statesDuplicates, size_t statesUnreachable, size_t statesUseless, const ext::deque < SymbolType > & alphabet, double density );
};
 
template < class SymbolType >
automaton::DFA < SymbolType, unsigned > RandomAutomatonFactory2::generateDFA( size_t statesMinimal, size_t statesDuplicates, size_t statesUnreachable, size_t statesUseless, ext::set < SymbolType > alphabet, double density ) {
    ext::deque < SymbolType> alphabet2;
 
    for( const auto & s : alphabet )
        alphabet2.push_back ( s );
 
    return RandomAutomatonFactory2::NonminimalDFA ( statesMinimal, statesDuplicates, statesUnreachable, statesUseless, alphabet, density );
}
 
template < class SymbolType >
size_t RandomAutomatonFactory2::randomSymbol ( unsigned sourceState, const ext::deque < SymbolType > & alphabet, const automaton::DFA < SymbolType, unsigned > & automaton ) {
    size_t x = ext::random_devices::semirandom() % ( alphabet.size( ) - automaton.getTransitionsFromState ( sourceState ).size ( ) ) + 1;
    for( size_t i = 0, cnt = 0; i < alphabet.size ( ); i++ ) {
        if ( automaton.getTransitions ( ).find ( std::make_pair ( sourceState, alphabet [ i ] ) ) == automaton.getTransitions ( ).end ( ) )
            cnt ++;
 
        if( cnt == x )
            return i;
    }
 
    return -1;
}
 
template < class SymbolType >
void RandomAutomatonFactory2::addTransition ( automaton::DFA < SymbolType, unsigned > & automaton, unsigned source, SymbolType symbol, unsigned target, const ext::deque < ext::vector < unsigned > > & duplicates ) {
    for ( unsigned duplicateSource : duplicates [ source ] ) {
        unsigned duplicateTarget = duplicates [ target ] [ ext::random_devices::semirandom() % ( duplicates [ target ].size ( ) ) ];
        automaton.addTransition( duplicateSource, symbol, duplicateTarget );
    }
}
 
template < class SymbolType >
automaton::DFA < SymbolType, unsigned > RandomAutomatonFactory2::NonminimalDFA( size_t statesMinimal, size_t statesDuplicates, size_t statesUnreachable, size_t statesUseless, const ext::deque < SymbolType > & alphabet, double density ) {
    // TODO make the same transition function on one of final states and one of the nonfinal ones.
    // unreachable states accesible from each other atleast a bit
    if( alphabet.empty ( ) )
        throw exception::CommonException( "Alphabet size must be greater than 0." );
 
    ext::deque < bool > VStates;
    ext::deque < bool > FStates;
    ext::deque < bool > DStates;
    // to represent states that will merge
    ext::deque < ext::vector < unsigned > > duplicates;
 
    size_t visited;
    size_t finals = 0;
    size_t depleted = 0;
 
    automaton::DFA < SymbolType, unsigned > automaton ( 0 );
 
    for( const auto & s : alphabet )
        automaton.addInputSymbol( s );
 
    /* states partitioning -- | statesMinimal | statesUseless | statesUnreachable | statesDuplicates | */
 
    for( unsigned i = 0; i < statesMinimal + statesUseless + statesUnreachable + statesDuplicates; i ++ ) {
        VStates.push_back( false );
        DStates.push_back( false );
        FStates.push_back( false );
        duplicates.push_back ( ext::vector < unsigned > { i } );
        automaton.addState( i );
    }
 
    for ( unsigned i = 0; i < statesDuplicates; ++ i ) {
        size_t a = ext::random_devices::semirandom() % ( statesMinimal );
        duplicates [ a ].push_back ( i + statesMinimal + statesUseless + statesUnreachable );
    }
 
    // ---- base
    if( statesMinimal == 0 ) {
        return automaton;
    } else if( statesMinimal == 1 ) {
        addTransition( automaton, 0, alphabet[ ext::random_devices::semirandom() % alphabet.size( ) ], 0, duplicates );
 
        visited = 1;
        VStates[ 0 ] = true;
        DStates[ 0 ] = automaton.getTransitionsFromState ( 0 ).size ( ) == alphabet.size ( );
        if ( DStates[ 0 ]  )
            depleted ++;
    } else {
        size_t x = ( ext::random_devices::semirandom() % ( statesMinimal - 1 ) ) + 1;
        addTransition( automaton, 0, alphabet[ ext::random_devices::semirandom() % alphabet.size( ) ], x, duplicates );
        visited = 2;
 
        VStates[ 0 ] = true;
        VStates[ x ] = true;
 
        DStates[ 0 ] = automaton.getTransitionsFromState ( 0 ).size ( ) == alphabet.size ( );
        if ( DStates[ 0 ]  )
            depleted ++;
    }
 
    // ---- make statesMinimal reachable
    while( visited != statesMinimal ) {
        size_t a = randomSourceState ( statesMinimal, visited, depleted, VStates, DStates );
        size_t b = randomTargetState ( statesMinimal, visited, VStates );
        size_t c = randomSymbol ( a, alphabet, automaton );
 
        addTransition( automaton, a, alphabet[ c ], b, duplicates );
 
        visited ++;
        VStates[ b ] = true;
        DStates[ a ] = automaton.getTransitionsFromState ( a ).size ( ) == alphabet.size ( );
        if ( DStates[ a ]  )
            depleted ++;
    }
 
    // ---- make statesUseless reachable
    while( visited != statesMinimal + statesUseless ) {
        size_t a = randomSourceState ( statesMinimal + statesUseless, visited, depleted, VStates, DStates );
        size_t b = randomTargetState ( statesMinimal + statesUseless, visited, VStates );
        size_t c = randomSymbol ( a, alphabet, automaton );
 
        addTransition( automaton, a, alphabet[ c ], b, duplicates );
 
        visited ++;
        VStates[ b ] = true;
        DStates[ a ] = automaton.getTransitionsFromState ( a ).size ( ) == alphabet.size ( );
        if ( DStates[ a ]  )
            depleted ++;
    }
 
    // ---- make 0 state and leaf states connected by path
    unsigned last = 0;
    for ( unsigned i = 0; i < statesMinimal; ++ i ) {
        if ( automaton.getTransitionsFromState ( i ).empty ( ) ) {
            size_t c = randomSymbol ( i, alphabet, automaton );
            addTransition ( automaton, i, alphabet [ c ], last, duplicates );
            last = i;
        }
    }
 
    // ---- make 1/3 to 2/3 of base states final
    for ( unsigned i = 0; i < statesMinimal * 2 / 3; ++ i ) {
        if ( i > statesMinimal / 3 && ext::random_devices::semirandom() % 2 == 0 )
            continue;
 
        size_t a = randomSourceState ( statesMinimal, visited - statesUseless, finals, VStates, FStates );
        FStates [ a ] = true;
        finals ++;
 
        for ( unsigned s : duplicates [ a ] )
            automaton.addFinalState ( s );
    }
 
    // ---- make 1/3 to 2/3 of unreachable states final
    for ( unsigned i = 0; i < statesUnreachable * 2 / 3; ++ i ) {
        if ( i > statesUnreachable / 3 && ext::random_devices::semirandom() % 2 == 0 )
            continue;
 
        size_t a = ext::random_devices::semirandom() % statesUnreachable + statesMinimal + statesUseless;
        FStates [ a ] = true;
        finals ++;
 
        for ( unsigned s : duplicates [ a ] )
            automaton.addFinalState ( s );
    }
 
    visited += statesUnreachable;
    for ( unsigned i = 0; i < statesUnreachable; ++ i ) {
        VStates [ statesMinimal + statesUseless + i ] = true;
    }
 
    // ---- fill in the rest of transition function randomly
    double mnn100 = 100.0 / alphabet.size( ) / ( statesMinimal + statesUseless + statesUnreachable + statesDuplicates );
    while( automaton.getTransitions ( ).size( ) * mnn100 < density ) {
        size_t a = randomSourceState ( statesMinimal + statesUseless + statesUnreachable, visited, depleted, VStates, DStates );
        size_t b;
        if ( a < statesMinimal )
            b = ext::random_devices::semirandom() % ( statesMinimal );
        else if ( a < statesMinimal + statesUseless )
            b = ext::random_devices::semirandom() % ( statesUseless ) + statesMinimal;
        else
            b = ext::random_devices::semirandom() % ( statesMinimal + statesUseless + statesUnreachable );
 
        size_t c = randomSymbol ( a, alphabet, automaton );
 
        addTransition( automaton, a, alphabet [ c ], b, duplicates );
        DStates[ a ] = automaton.getTransitionsFromState ( a ).size ( ) == alphabet.size ( );
        if ( DStates[ a ]  )
            depleted ++;
    }
 
    return automaton;
}
 
} /* namespace generate */
 
} /* namespace automaton */