RandomAutomatonFactory3.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/MultiInitialStateNFA.h>
 
namespace automaton {
 
namespace generate {
 
class RandomAutomatonFactory3 {
public:
    template < class SymbolType >
    static automaton::MultiInitialStateNFA < SymbolType, unsigned > generate ( size_t statesMinimal, size_t statesDuplicates, size_t statesUnreachable, size_t statesUseless, size_t initialStates, size_t finalStates, ext::set < SymbolType> alphabet, double density, bool deterministic );
    static automaton::MultiInitialStateNFA < std::string, unsigned > generate ( size_t statesMinimal, size_t statesDuplicates, size_t statesUnreachable, size_t statesUseless, size_t initialStates, size_t finalStates, size_t alphabetSize, bool randomizedAlphabet, double density, bool deterministic );
 
private:
    static ext::vector < unsigned > makeVector ( size_t begin, size_t end );
    template < class SymbolType >
    static size_t randomSymbol ( unsigned sourceState, const ext::deque < SymbolType > & alphabet, const automaton::MultiInitialStateNFA < SymbolType, unsigned > & automaton, bool deterministic );
    template < class SymbolType>
    static bool makeRelationElement ( automaton::MultiInitialStateNFA < SymbolType, unsigned > & automaton, const ext::deque < SymbolType> & alphabet, const ext::vector < unsigned > & sourceSet, const ext::vector < unsigned > & targetSet, const ext::deque < ext::vector < unsigned > > & duplicates, bool deterministic );
    template < class SymbolType >
    static void makeRelation ( automaton::MultiInitialStateNFA < SymbolType, unsigned > & automaton, const ext::deque < SymbolType> & alphabet, const ext::vector < unsigned > & sourceSet, const ext::vector < unsigned > & targetSet, const ext::deque < ext::vector < unsigned > > & duplicates, double density, bool deterministic );
    template < class SymbolType >
    static bool addTransition ( automaton::MultiInitialStateNFA < SymbolType, unsigned > & automaton, unsigned source, SymbolType symbol, unsigned target, const ext::deque < ext::vector < unsigned > > & duplicates );
    template < class SymbolType >
    static automaton::MultiInitialStateNFA < SymbolType, unsigned > run ( ext::vector < unsigned > statesMinimal, size_t statesDuplicates, ext::vector < unsigned > statesUnreachable, ext::vector < unsigned > statesUseless, size_t statesInitial, size_t statesFinal, const ext::deque < SymbolType > & alphabet, double density, bool deterministic );
};
 
template < class SymbolType >
automaton::MultiInitialStateNFA < SymbolType, unsigned > RandomAutomatonFactory3::generate ( size_t statesMinimal, size_t statesDuplicates, size_t statesUnreachable, size_t statesUseless, size_t initialStates, size_t finalStates, ext::set < SymbolType > alphabet, double density, bool deterministic ) {
    if ( deterministic && initialStates > 1 )
        throw exception::CommonException("Deterministic automaton has to have a single initial state.");
 
    if ( initialStates == 0 )
        throw exception::CommonException("There has to be at least one initial state.");
 
    ext::deque < SymbolType> alphabet2;
 
    for( const auto & s : alphabet )
        alphabet2.push_back ( s );
 
    return RandomAutomatonFactory3::run ( makeVector ( 0                                    , statesMinimal ),
                                          statesDuplicates,
                                          makeVector ( statesMinimal                        , statesMinimal + statesUnreachable ),
                                          makeVector ( statesMinimal + statesUnreachable    , statesMinimal + statesUnreachable + statesUseless ),
                                          initialStates, finalStates, alphabet, density, deterministic );
}
 
template < class SymbolType >
size_t RandomAutomatonFactory3::randomSymbol ( unsigned sourceState, const ext::deque < SymbolType > & alphabet, const automaton::MultiInitialStateNFA < SymbolType, unsigned > & automaton, bool deterministic ) {
    if ( ! deterministic )
        return ext::random_devices::semirandom ( ) % alphabet.size ( );
 
    size_t modulo = alphabet.size ( ) - automaton.getTransitions ( ).count ( ext::slice_comp ( sourceState ) );
    if ( modulo == 0 )
        throw exception::CommonException("State does not have any remaining symbol available.");
 
    size_t x = ext::random_devices::semirandom ( ) % modulo + 1; // the +1 to match the incrementation of cnt if the symbol is not used
    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;
    }
 
    throw exception::CommonException("Should not be reached.");
}
 
template < class SymbolType >
bool RandomAutomatonFactory3::addTransition ( automaton::MultiInitialStateNFA < SymbolType, unsigned > & automaton, unsigned source, SymbolType symbol, unsigned target, const ext::deque < ext::vector < unsigned > > & duplicates ) {
    bool res = false;
    for ( unsigned duplicateSource : duplicates [ source ] ) {
        unsigned duplicateTarget = duplicates [ target ] [ ext::random_devices::semirandom() % ( duplicates [ target ].size ( ) ) ];
        res |= automaton.addTransition ( duplicateSource, symbol, duplicateTarget );
    }
    return res;
}
 
template < class SymbolType>
bool RandomAutomatonFactory3::makeRelationElement ( automaton::MultiInitialStateNFA < SymbolType, unsigned > & automaton, const ext::deque < SymbolType> & alphabet, const ext::vector < unsigned > & sourceSet, const ext::vector < unsigned > & targetSet, const ext::deque < ext::vector < unsigned > > & duplicates, bool deterministic ) {
    unsigned a = sourceSet [ ext::random_devices::semirandom ( ) % sourceSet.size ( ) ];
 
    if ( deterministic && automaton.getTransitions ( ).count ( ext::slice_comp ( a ) ) == alphabet.size ( ) )
        return false;
 
    unsigned c = randomSymbol ( a, alphabet, automaton, deterministic );
    unsigned b = targetSet [ ext::random_devices::semirandom ( ) % targetSet.size ( ) ];
 
    return addTransition ( automaton, a, alphabet [ c ], b, duplicates );
}
 
template < class SymbolType >
void RandomAutomatonFactory3::makeRelation ( automaton::MultiInitialStateNFA < SymbolType, unsigned > & automaton, const ext::deque < SymbolType> & alphabet, const ext::vector < unsigned > & sourceSet, const ext::vector < unsigned > & targetSet, const ext::deque < ext::vector < unsigned > > & duplicates, double density, bool deterministic ) {
 
    ext::vector < unsigned > targetSetIncludingDuplicates;
    for ( unsigned targetState : targetSet )
        for ( unsigned duplicateTarget : duplicates [ targetState ] )
            targetSetIncludingDuplicates.push_back ( duplicateTarget );
 
    std::sort ( targetSetIncludingDuplicates.begin ( ), targetSetIncludingDuplicates.end ( ) );
 
    if ( targetSet.empty ( ) )
        return;
 
    size_t entriesToCreate = sourceSet.size ( ) * alphabet.size ( );
    if ( ! deterministic )
        entriesToCreate *= targetSet.size ( );
 
    if ( deterministic )
        for ( size_t state : sourceSet )
            entriesToCreate -= automaton.getTransitions ( ).count ( ext::slice_comp ( state ) );
    else
        for ( unsigned state : sourceSet )
            for ( const std::pair < const ext::pair < unsigned, SymbolType >, unsigned > & transition : automaton.getTransitionsFromState ( state ) ) // transitions are not sorted by the target ...
                if ( std::binary_search ( targetSetIncludingDuplicates.begin ( ), targetSetIncludingDuplicates.end ( ), transition.second ) )
                    -- entriesToCreate;
 
    entriesToCreate *= density;
 
    while ( entriesToCreate )
        if ( makeRelationElement ( automaton, alphabet, sourceSet, targetSet, duplicates, deterministic ) )
            -- entriesToCreate;
}
 
template < class Callback >
void callbackOnRandom ( Callback callback, size_t states, const ext::vector < unsigned > & set1, const ext::vector < unsigned > & set2, const ext::deque < ext::vector < unsigned > > & duplicates ) {
    while ( states ) {
        size_t index = ext::random_devices::semirandom ( ) % ( set1.size ( ) + set2.size ( ) );
 
        unsigned state;
        if ( index < set1.size ( ) )
            state = set1 [ index ];
        else {
            index -= set1.size ( );
            state = set2 [ index ];
        }
 
        bool res = false;
        for ( unsigned duplicateState : duplicates [ state ] ) {
            res |= callback ( duplicateState );
        }
 
        if ( res )
            -- states;
    }
}
 
template < class SymbolType >
automaton::MultiInitialStateNFA < SymbolType, unsigned > RandomAutomatonFactory3::run ( ext::vector < unsigned > statesMinimal, size_t statesDuplicates, ext::vector < unsigned > statesUnreachable, ext::vector < unsigned > statesUseless, size_t statesInitial, size_t statesFinal, const ext::deque < SymbolType > & alphabet, double density, bool deterministic ) {
    automaton::MultiInitialStateNFA < SymbolType, unsigned > automaton;
 
    for ( const auto & s : alphabet )
        automaton.addInputSymbol( s );
 
    ext::deque < ext::vector < unsigned > > duplicates;
 
    for ( unsigned state : statesMinimal ) {
        duplicates.push_back ( ext::vector < unsigned > { state } );
        automaton.addState ( state );
    }
 
    for ( unsigned state : statesUnreachable ) {
        duplicates.push_back ( ext::vector < unsigned > { state } );
        automaton.addState ( state );
    }
 
    for ( unsigned state : statesUseless ) {
        duplicates.push_back ( ext::vector < unsigned > { state } );
        automaton.addState ( state );
    }
 
    size_t statesNow = automaton.getStates ( ).size ( );
    for ( unsigned duplicate = 0; duplicate < statesDuplicates; ++ duplicate ) {
        automaton.addState ( statesNow + duplicate );
 
        size_t a = ext::random_devices::semirandom() % ( statesNow );
        duplicates [ a ].push_back ( statesNow + duplicate );
    }
 
    callbackOnRandom ( [ & ] ( unsigned state ) {
        return automaton.addFinalState ( state );
    }, statesFinal, statesMinimal, statesUnreachable, duplicates );
 
    unsigned initialState = ext::random_devices::semirandom ( ) % statesMinimal.size ( );
    automaton.addInitialState ( initialState );
    callbackOnRandom ( [ & ] ( unsigned state ) {
        return automaton.addInitialState ( state );
    }, statesInitial - 1, statesMinimal, statesUseless, duplicates );
 
    ext::vector < unsigned > visited { initialState };
    ext::vector < unsigned > unused = statesMinimal;
    unused.erase ( std::find ( unused.begin ( ), unused.end ( ), initialState ) );
 
    while ( visited.size ( ) != statesMinimal.size ( ) ) {
        unsigned a = visited [ ext::random_devices::semirandom ( ) % visited.size ( ) ];
 
        if ( automaton.getTransitions ( ).count ( ext::slice_comp ( a ) ) == alphabet.size ( ) )
            continue;
 
        size_t c = randomSymbol ( a, alphabet, automaton, deterministic );
        size_t b = ext::random_devices::semirandom ( ) % unused.size ( );
 
        addTransition( automaton, a, alphabet [ c ], unused [ b ], duplicates );
        visited.push_back ( unused [ b ] );
        unused.erase ( unused.begin ( ) + b );
    }
 
    makeRelation ( automaton, alphabet, statesMinimal, statesMinimal, duplicates, density, deterministic );
    makeRelation ( automaton, alphabet, statesUnreachable, statesUnreachable, duplicates, density, deterministic );
    makeRelation ( automaton, alphabet, statesUseless, statesUseless, duplicates, density, deterministic );
 
    if ( ! statesUnreachable.empty ( ) && ! statesUseless.empty ( ) )
        makeRelationElement ( automaton, alphabet, statesUnreachable, statesUseless, duplicates, deterministic );
 
    makeRelation ( automaton, alphabet, statesMinimal, statesUseless, duplicates, density, deterministic );
    makeRelation ( automaton, alphabet, statesUnreachable, statesMinimal, duplicates, density, deterministic );
    makeRelation ( automaton, alphabet, statesUnreachable, statesUseless, duplicates, density, deterministic );
 
    return automaton;
}
 
} /* namespace generate */
 
} /* namespace automaton */