RandomTreeAutomatonFactory.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/TA/NFTA.h>
 
namespace automaton {
 
namespace generate {
 
class RandomTreeAutomatonFactory {
public:
    template < class SymbolType >
    static automaton::NFTA < SymbolType, unsigned > generateNFTA ( size_t statesCount, const ext::set < common::ranked_symbol < SymbolType > > & alphabet, double density );
 
    static automaton::NFTA < std::string, unsigned > generateNFTA ( size_t statesCount, size_t alphabetSize, size_t maxRank, 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::NFTA < SymbolType, unsigned > LeslieConnectedNFTA ( size_t n, const ext::deque < common::ranked_symbol < SymbolType > > & alphabet, double density );
};
 
template < class SymbolType >
automaton::NFTA < SymbolType, unsigned > RandomTreeAutomatonFactory::generateNFTA ( size_t statesCount, const ext::set < common::ranked_symbol < SymbolType > > & alphabet, double density ) {
    ext::deque < common::ranked_symbol < SymbolType > > alphabet2 ( alphabet.begin ( ), alphabet.end ( ) );
    return RandomTreeAutomatonFactory::LeslieConnectedNFTA ( statesCount, alphabet2, density );
}
 
template < class SymbolType >
automaton::NFTA < SymbolType, unsigned > RandomTreeAutomatonFactory::LeslieConnectedNFTA ( size_t n, const ext::deque < common::ranked_symbol < SymbolType > > & alphabet, double density ) {
    if( alphabet.empty ( ) )
        throw exception::CommonException( "Alphabet size must be greater than 0." );
 
    ext::deque < common::ranked_symbol < SymbolType > > nullaryAlphabet;
    for ( const common::ranked_symbol < SymbolType > & symbol : alphabet )
        if ( symbol.getRank ( ) == 0 )
            nullaryAlphabet.push_back ( symbol );
 
    if ( nullaryAlphabet.empty ( ) )
        throw exception::CommonException ( "Alphabet does not contain a nullary symbol" );
 
    ext::deque<bool> VStates;
    ext::deque<unsigned> Q;
 
    automaton::NFTA < SymbolType, unsigned > automaton;
 
    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( nullaryAlphabet[ ext::random_devices::semirandom() % nullaryAlphabet.size( ) ], ext::vector < unsigned > { }, Q[ 0 ] );
 
        VStates[ 0 ] = true;
    } else {
        unsigned x = ext::random_devices::semirandom() % n;
        automaton.addTransition( nullaryAlphabet[ ext::random_devices::semirandom() % nullaryAlphabet.size( ) ], ext::vector < unsigned > { }, Q[ x ] );
 
        VStates[ x ] = true;
    }
 
    size_t unvisited = n - 1;
 
    while( unvisited != 0 ) {
        int c = ext::random_devices::semirandom() % alphabet.size( );
        ext::vector < unsigned > from;
        while ( from.size ( ) < alphabet [ c ].getRank ( ) ) {
            size_t a = ithAccessibleState ( VStates, ext::random_devices::semirandom() % ( n - unvisited ) );   // select y-th accessible state
            from.push_back ( Q[ a ] );
        }
 
        size_t b = ithInaccessibleState ( VStates, ext::random_devices::semirandom() % unvisited );     // select z-th inaccessible state
 
        automaton.addTransition( alphabet[ c ], std::move ( from ), 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.getStates( ).begin ( ) );
        } else {
            for( const unsigned & q : Q ) {
                if( automaton.getTransitionsFromState( q ).empty ( ) ) {
                    automaton.addFinalState( q );
                    break;
                }
            }
        }
    }
 
    size_t accSourceStates = 1;
    for ( const common::ranked_symbol < SymbolType > & symbol : alphabet )
        accSourceStates += symbol.getRank ( );
 
    double mnn100 = 100.0 / alphabet.size( ) / accSourceStates / n; //FIXME check the computation of density
    while( automaton.getTransitions ( ).size ( ) * mnn100 < density ) {
        int a = ext::random_devices::semirandom() % alphabet.size( );
        ext::vector < unsigned > from;
        while ( from.size ( ) < alphabet [ a ].getRank ( ) ) {
            int y = ext::random_devices::semirandom() % n;
            from.push_back ( Q[ y ] );
        }
 
        int z = ext::random_devices::semirandom() % n;
 
        automaton.addTransition( alphabet [ a ], std::move ( from ), Q[ z ] );
    }
 
    ext::set < common::ranked_symbol < SymbolType > > alphabetUsage = automaton.getInputAlphabet ( );
    for ( const auto & t : automaton.getTransitions( ) )
        alphabetUsage.erase ( t.first.first );
 
    for ( const auto & kv : alphabetUsage )
        automaton.removeInputSymbol ( kv );
 
    return automaton;
}
 
} /* namespace generate */
 
} /* namespace automaton */