Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Concepts
RandomTreeAutomatonFactory.h
Go to the documentation of this file.
1
6/*
7 * This file is part of Algorithms library toolkit.
8 * Copyright (C) 2017 Jan Travnicek (jan.travnicek@fit.cvut.cz)
9
10 * Algorithms library toolkit is free software: you can redistribute it and/or modify
11 * it under the terms of the GNU General Public License as published by
12 * the Free Software Foundation, either version 3 of the License, or
13 * (at your option) any later version.
14
15 * Algorithms library toolkit is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
19
20 * You should have received a copy of the GNU General Public License
21 * along with Algorithms library toolkit. If not, see <http://www.gnu.org/licenses/>.
22 */
23
24#pragma once
25
26#include <ext/algorithm>
27#include <ext/random>
28
29#include <alib/deque>
30#include <alib/set>
31#include <alib/string>
32
34
35#include <automaton/TA/NFTA.h>
36
37namespace automaton {
38
39namespace generate {
40
48public:
59 template < class SymbolType >
61
75 static automaton::NFTA < std::string, unsigned > generateNFTA ( size_t statesCount, size_t alphabetSize, size_t maxRank, bool randomizedAlphabet, double density );
76
77private:
86 static unsigned ithAccessibleState ( const ext::deque < bool > & VStates, size_t i );
87
96 static unsigned ithInaccessibleState ( const ext::deque < bool > & VStates, size_t i );
97
109 template < class SymbolType >
110 static automaton::NFTA < SymbolType, unsigned > LeslieConnectedNFTA ( size_t n, const ext::deque < common::ranked_symbol < SymbolType > > & alphabet, double density );
111};
112
113template < class SymbolType >
116 return RandomTreeAutomatonFactory::LeslieConnectedNFTA ( statesCount, alphabet2, density );
117}
118
119template < class SymbolType >
120automaton::NFTA < SymbolType, unsigned > RandomTreeAutomatonFactory::LeslieConnectedNFTA ( size_t n, const ext::deque < common::ranked_symbol < SymbolType > > & alphabet, double density ) {
121 if( alphabet.empty ( ) )
122 throw exception::CommonException( "Alphabet size must be greater than 0." );
123
125 for ( const common::ranked_symbol < SymbolType > & symbol : alphabet )
126 if ( symbol.getRank ( ) == 0 )
127 nullaryAlphabet.push_back ( symbol );
128
129 if ( nullaryAlphabet.empty ( ) )
130 throw exception::CommonException ( "Alphabet does not contain a nullary symbol" );
131
132 ext::deque<bool> VStates;
134
136
137 for( const auto & s : alphabet )
138 automaton.addInputSymbol( s );
139
140 for( size_t i = 0; i < n; i ++ ) {
141 VStates.push_back( false );
142 Q.push_back( i );
143 automaton.addState( Q[ i ] );
144 }
145
146 if( n == 0 ) {
147 return automaton;
148 } else if( n == 1 ) {
149 automaton.addTransition( nullaryAlphabet[ ext::random_devices::semirandom() % nullaryAlphabet.size( ) ], ext::vector < unsigned > { }, Q[ 0 ] );
150
151 VStates[ 0 ] = true;
152 } else {
153 unsigned x = ext::random_devices::semirandom() % n;
154 automaton.addTransition( nullaryAlphabet[ ext::random_devices::semirandom() % nullaryAlphabet.size( ) ], ext::vector < unsigned > { }, Q[ x ] );
155
156 VStates[ x ] = true;
157 }
158
159 size_t unvisited = n - 1;
160
161 while( unvisited != 0 ) {
162 int c = ext::random_devices::semirandom() % alphabet.size( );
164 while ( from.size ( ) < alphabet [ c ].getRank ( ) ) {
165 size_t a = ithAccessibleState ( VStates, ext::random_devices::semirandom() % ( n - unvisited ) ); // select y-th accessible state
166 from.push_back ( Q[ a ] );
167 }
168
169 size_t b = ithInaccessibleState ( VStates, ext::random_devices::semirandom() % unvisited ); // select z-th inaccessible state
170
171 automaton.addTransition( alphabet[ c ], std::move ( from ), Q[ b ] );
172
173 unvisited -= 1;
174 VStates[ b ] = true;
175 }
176
177 for( const unsigned & q : Q ) {
178 if( automaton.getTransitionsFromState( q ).empty ( ) && ext::random_devices::semirandom() % 100 < 90 )
179 automaton.addFinalState( q );
180 else if( !automaton.getTransitionsFromState( q ).empty ( ) && ext::random_devices::semirandom() % 100 < 10 )
181 automaton.addFinalState( q );
182 }
183
184 if( automaton.getFinalStates( ).empty ( ) ) {
185 if( n == 1 ) {
186 automaton.addFinalState( * automaton.getStates( ).begin ( ) );
187 } else {
188 for( const unsigned & q : Q ) {
189 if( automaton.getTransitionsFromState( q ).empty ( ) ) {
190 automaton.addFinalState( q );
191 break;
192 }
193 }
194 }
195 }
196
197 size_t accSourceStates = 1;
198 for ( const common::ranked_symbol < SymbolType > & symbol : alphabet )
199 accSourceStates += symbol.getRank ( );
200
201 double mnn100 = 100.0 / alphabet.size( ) / accSourceStates / n; //FIXME check the computation of density
202 while( automaton.getTransitions ( ).size ( ) * mnn100 < density ) {
203 int a = ext::random_devices::semirandom() % alphabet.size( );
205 while ( from.size ( ) < alphabet [ a ].getRank ( ) ) {
207 from.push_back ( Q[ y ] );
208 }
209
211
212 automaton.addTransition( alphabet [ a ], std::move ( from ), Q[ z ] );
213 }
214
215 ext::set < common::ranked_symbol < SymbolType > > alphabetUsage = automaton.getInputAlphabet ( );
216 for ( const auto & t : automaton.getTransitions( ) )
217 alphabetUsage.erase ( t.first.first );
218
219 for ( const auto & kv : alphabetUsage )
220 automaton.removeInputSymbol ( kv );
221
222 return automaton;
223}
224
225} /* namespace generate */
226
227} /* namespace automaton */
228
Nondeterministic finite tree automaton without epsilon transitions. Accepts regular tree languages.
Definition: NFTA.h:72
Definition: RandomTreeAutomatonFactory.h:47
static automaton::NFTA< SymbolType, unsigned > generateNFTA(size_t statesCount, const ext::set< common::ranked_symbol< SymbolType > > &alphabet, double density)
Definition: RandomTreeAutomatonFactory.h:114
Definition: ranked_symbol.hpp:20
Basic exception from which all other exceptions are derived.
Definition: CommonException.h:21
Class extending the deque class from the standard library. Original reason is to allow printing of th...
Definition: deque.hpp:44
static semirandom_device & semirandom
The reference to singleton semirandom device.
Definition: random.hpp:147
Definition: set.hpp:44
Class extending the vector class from the standard library. Original reason is to allow printing of t...
Definition: vector.hpp:45
Definition: BarSymbol.cpp:12
int i
Definition: AllEpsilonClosure.h:118
q
Definition: SingleInitialStateEpsilonTransition.h:85
Definition: ToGrammar.h:31