RandomizeAutomaton.h

/*
 * RandomizeAutomaton.h
 *
 * 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/>.
 *
 *  Created on: 9. 2. 2017
 *	  Author: Jan Travnicek
 */

#ifndef AUTOMATON_RANDOMIZE_H_
#define AUTOMATON_RANDOMIZE_H_

#include <automaton/FSM/EpsilonNFA.h>
#include <automaton/FSM/MultiInitialStateNFA.h>
#include <automaton/FSM/NFA.h>
#include <automaton/FSM/DFA.h>

#include <common/Permutation.hpp>

namespace automaton {

namespace generate {

/**
 * Algorithm for random shuffling of the finite automata states.
 * Effectively just renames the states of the FSM using the original state names.
 */
class RandomizeAutomaton {
public:
	/**
	 * Shuffle the set of states of the automaton.
	 *
	 * @tparam SymbolType Type of input symbols.
	 * @tparam EpsilonType Type of epsilon symbol.
	 * @tparam StateType Type of states.
	 * @param fsm automaton to shuffle
	 */
	template < class SymbolType, class EpsilonType, class StateType >
	static automaton::EpsilonNFA < SymbolType, EpsilonType, StateType > randomize( const automaton::EpsilonNFA < SymbolType, EpsilonType, StateType > & fsm );

	/**
	 * @overload
	 */
	template < class SymbolType, class StateType >
	static automaton::MultiInitialStateNFA < SymbolType, StateType > randomize( const automaton::MultiInitialStateNFA < SymbolType, StateType > & fsm );

	/**
	 * @overload
	 */
	template < class SymbolType, class StateType >
	static automaton::NFA < SymbolType, StateType > randomize( const automaton::NFA < SymbolType, StateType > & fsm );

	/**
	 * @overload
	 */
	template < class SymbolType, class StateType >
	static automaton::DFA < SymbolType, StateType > randomize( const automaton::DFA < SymbolType, StateType > & fsm );
};

template < class SymbolType, class StateType >
automaton::DFA < SymbolType, StateType > RandomizeAutomaton::randomize(const automaton::DFA < SymbolType, StateType > & origFSM) {
	ext::map < StateType, StateType > statePermutationMap = common::Permutation::permutationMap ( origFSM.getStates ( ) );

	automaton::DFA < SymbolType, StateType > res ( statePermutationMap.find ( origFSM.getInitialState ( ) )->second );

	res.setStates ( origFSM.getStates ( ) );
	res.setInputAlphabet ( origFSM.getInputAlphabet ( ) );

	for ( const StateType & finalState : origFSM.getFinalStates ( ) )
		res.addFinalState ( statePermutationMap.find ( finalState )->second );

	for ( const std::pair < std::pair < StateType, SymbolType >, SymbolType > & transition : origFSM.getTransitions ( ) )
		res.addTransition ( statePermutationMap.find ( transition.first.first )->second, transition.first.second, statePermutationMap.find ( transition.second )->second );

	return res;
}

template < class SymbolType, class StateType >
automaton::MultiInitialStateNFA < SymbolType, StateType > RandomizeAutomaton::randomize(const automaton::MultiInitialStateNFA < SymbolType, StateType > & origFSM) {
	ext::map < StateType, StateType > statePermutationMap = common::Permutation::permutationMap ( origFSM.getStates ( ) );

	automaton::MultiInitialStateNFA < SymbolType, StateType > res;

	res.setStates ( origFSM.getStates ( ) );
	res.setInputAlphabet ( origFSM.getInputAlphabet ( ) );
	
	for ( const StateType & initialState : origFSM.getInitialStates ( ) )
		res.addInitialState ( statePermutationMap.find ( initialState )->second );

	for ( const StateType & finalState : origFSM.getFinalStates ( ) )
		res.addFinalState ( statePermutationMap.find ( finalState )->second );

	for ( const std::pair < std::pair < StateType, SymbolType >, ext::set < SymbolType > > & transition : origFSM.getTransitions ( ) )
		for ( const StateType & target : transition.second )
			res.addTransition ( statePermutationMap.find ( transition.first.first )->second, transition.first.second, statePermutationMap.find ( target )->second );

	return res;
}

template < class SymbolType, class StateType >
automaton::NFA < SymbolType, StateType > RandomizeAutomaton::randomize(const automaton::NFA < SymbolType, StateType > & origFSM) {
	ext::map < StateType, StateType > statePermutationMap = common::Permutation::permutationMap ( origFSM.getStates ( ) );

	automaton::NFA < SymbolType, StateType > res ( statePermutationMap.find ( origFSM.getInitialState ( ) )->second );

	res.setStates ( origFSM.getStates ( ) );
	res.setInputAlphabet ( origFSM.getInputAlphabet ( ) );

	for ( const StateType & finalState : origFSM.getFinalStates ( ) )
		res.addFinalState ( statePermutationMap.find ( finalState )->second );

	for ( const std::pair < std::pair < StateType, SymbolType >, ext::set < SymbolType > > & transition : origFSM.getTransitions ( ) )
		for ( const StateType & target : transition.second )
			res.addTransition ( statePermutationMap.find ( transition.first.first )->second, transition.first.second, statePermutationMap.find ( target )->second );

	return res;
}

template < class SymbolType, class EpsilonType, class StateType >
automaton::EpsilonNFA < SymbolType, EpsilonType, StateType > RandomizeAutomaton::randomize( const automaton::EpsilonNFA < SymbolType, EpsilonType, StateType > & origFSM ) {
	ext::map < StateType, StateType > statePermutationMap = common::Permutation::permutationMap ( origFSM.getStates ( ) );

	automaton::EpsilonNFA < SymbolType, EpsilonType, StateType > res ( statePermutationMap.find ( origFSM.getInitialState ( ) )->second );

	res.setStates ( origFSM.getStates ( ) );
	res.setInputAlphabet ( origFSM.getInputAlphabet ( ) );

	for ( const StateType & finalState : origFSM.getFinalStates ( ) )
		res.addFinalState ( statePermutationMap.find ( finalState )->second );

	for ( const std::pair < std::pair < StateType, ext::variant < EpsilonType, SymbolType > >, ext::set < SymbolType > > & transition : origFSM.getTransitions ( ) )
		for ( const StateType & target : transition.second )
			res.addTransition ( statePermutationMap.find ( transition.first.first )->second, transition.first.second, statePermutationMap.find ( target )->second );

	return res;
}

} /* namespace generate */

} /* namespace automaton */

#endif /* AUTOMATON_RANDOMIZE_H_ */