ToArcFactored.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 "automaton/TA/NondeterministicZAutomaton.h"
#include "automaton/TA/ArcFactoredNondeterministicZAutomaton.h"
 
#include "automaton/properties/AllEpsilonClosure.h"
 
#include "alphabet/StartSymbol.h"
 
namespace automaton {
 
namespace simplify {
 
class ToArcFactored {
public:
    template < class SymbolType, class StateType >
    static ArcFactoredNondeterministicZAutomaton < SymbolType, ext::vector < ext::variant < SymbolType, StateType > > > convert ( const NondeterministicZAutomaton < SymbolType, StateType > & automaton );
};
 
template < class SymbolType, class StateType >
ArcFactoredNondeterministicZAutomaton < SymbolType, ext::vector < ext::variant < SymbolType, StateType > > > ToArcFactored::convert ( const NondeterministicZAutomaton < SymbolType, StateType > & automaton ) {
    ext::map < StateType, ext::set < StateType > > epsilonClosure = automaton::properties::AllEpsilonClosure::allEpsilonClosure ( automaton );
 
    ext::multimap < ext::pair < ext::variant < SymbolType, StateType >, ext::vector < ext::variant < SymbolType, StateType > > >, StateType > nonEpsilonTransitions;
    for ( const std::pair < const ext::pair < ext::variant < SymbolType, StateType >, ext::vector < ext::variant < SymbolType, StateType > > >, StateType > & transition : automaton.getTransitions ( ) )
        for ( const StateType & state : epsilonClosure [ transition.second ] )
            nonEpsilonTransitions.insert ( ext::make_pair ( transition.first, state ) );
 
    ArcFactoredNondeterministicZAutomaton < SymbolType, ext::vector < ext::variant < SymbolType, StateType > > > res;
 
    for ( const StateType & state : automaton.getStates ( ) )
        res.addState ( ext::vector < ext::variant < SymbolType, StateType > > ( 1, state ) );
 
    for ( const StateType & state : automaton.getFinalStates ( ) )
        res.addFinalState ( ext::vector < ext::variant < SymbolType, StateType > > ( 1, state ) );
 
    res.addInputSymbols ( automaton.getInputAlphabet ( ) );
 
    for ( const SymbolType & symbol : automaton.getInputAlphabet ( ) ) {
        auto state = ext::vector < ext::variant < SymbolType, StateType > > ( 1, symbol );
        res.addState ( state );
        res.addTransition ( symbol, state );
    }
 
    for ( const std::pair < const ext::pair < ext::variant < SymbolType, StateType >, ext::vector < ext::variant < SymbolType, StateType > > >, StateType > & transition : nonEpsilonTransitions ) {
        if ( ! transition.first.second.empty ( ) ) {
            ext::vector < ext::variant < SymbolType, StateType > > source = ext::vector < ext::variant < SymbolType, StateType > > ( 1, transition.first.first );
 
            for ( auto iter = transition.first.second.begin ( ); std::next ( iter ) != transition.first.second.end ( ); ++ iter ) {
                ext::vector < ext::variant < SymbolType, StateType > > newSource = ext::vector < ext::variant < SymbolType, StateType > > ( iter, transition.first.second.end ( ) );
                res.addState ( newSource );
                res.addTransition ( ext::make_pair ( source, ext::vector < ext::variant < SymbolType, StateType > > ( 1, * iter ) ), newSource );
                source = newSource;
            }
 
            res.addTransition ( ext::make_pair ( source, ext::vector < ext::variant < SymbolType, StateType > > ( 1, transition.first.second.back ( ) ) ), ext::vector < ext::variant < SymbolType, StateType > > ( 1, transition.second ) );
        }
    }
 
    // actually not in the paper
    for ( const std::pair < const ext::pair < ext::variant < SymbolType, StateType >, ext::vector < ext::variant < SymbolType, StateType > > >, StateType > & transition : nonEpsilonTransitions )
        if ( automaton.getInputAlphabet ( ).contains ( transition.first.first ) && transition.first.second.empty ( ) )
            res.addTransition ( transition.first.first.template get < SymbolType > ( ), ext::vector < ext::variant < SymbolType, StateType > > ( 1, transition.second ) );
 
    return res;
}
 
} /* namespace simplify */
 
} /* namespace automaton */