AllEpsilonClosure.h

Go to the documentation of this file.

 
#pragma once
 
#include <set>
#include <map>
 
#include <automaton/FSM/ExtendedNFA.h>
#include <automaton/FSM/CompactNFA.h>
#include <automaton/FSM/EpsilonNFA.h>
#include <automaton/FSM/MultiInitialStateNFA.h>
#include <automaton/FSM/NFA.h>
#include <automaton/FSM/DFA.h>
 
#include <regexp/properties/RegExpEpsilon.h>
 
namespace automaton {
 
namespace properties {
 
namespace efficient {
 
class AllEpsilonClosure {
    template < class StateType >
    static void process(const ext::multimap<StateType, StateType>& epsilonTransitions, const StateType & state, ext::map<StateType, ext::set<StateType>>& closures, ext::set<StateType>& nonvisited);
public:
    template < class SymbolType, class StateType >
    static ext::map<StateType, ext::set<StateType>> allEpsilonClosure( const automaton::EpsilonNFA < SymbolType, StateType > & fsm);
    template < class SymbolType, class StateType >
    static ext::map<StateType, ext::set<StateType>> allEpsilonClosure( const automaton::MultiInitialStateNFA < SymbolType, StateType > & fsm);
    template < class SymbolType, class StateType >
    static ext::map<StateType, ext::set<StateType>> allEpsilonClosure( const automaton::NFA < SymbolType, StateType > & fsm);
    template < class SymbolType, class StateType >
    static ext::map<StateType, ext::set<StateType>> allEpsilonClosure( const automaton::DFA < SymbolType, StateType > & fsm);
    template < class SymbolType, class StateType >
    static ext::map<StateType, ext::set<StateType>> allEpsilonClosure( const automaton::ExtendedNFA < SymbolType, StateType > & fsm);
    template < class SymbolType, class StateType >
    static ext::map<StateType, ext::set<StateType>> allEpsilonClosure( const automaton::CompactNFA < SymbolType, StateType > & fsm);
};
 
template < class StateType >
void AllEpsilonClosure::process(const ext::multimap<StateType, StateType>& epsilonTransitions, const StateType & state, ext::map<StateType, ext::set<StateType>>& closures, ext::set<StateType>& nonvisited) {
    auto node = nonvisited.extract ( state );
    if ( ! static_cast < bool > ( node ) )
        return;
 
    for ( const auto & transition : epsilonTransitions.equal_range ( node.value ( ) ) ) {
        process ( epsilonTransitions, transition.second, closures, nonvisited );
        const auto & closure = closures [ transition.second ];
        closures [ node.value ( ) ].insert ( closure.begin ( ), closure.end ( ) );
    }
}
 
template < class SymbolType, class StateType >
ext::map<StateType, ext::set<StateType>> AllEpsilonClosure::allEpsilonClosure( const automaton::EpsilonNFA < SymbolType, StateType > & fsm) {
    ext::map<StateType, ext::set<StateType>> res;
 
    for(const StateType& state : fsm.getStates())
        res[state].insert(state);
 
    ext::set<StateType> nonvisited = fsm.getStates();
 
    ext::multimap<StateType, StateType> epsilonTransitions = fsm.getEpsilonTransitions();
 
    while(!nonvisited.empty ( )) {
        process(epsilonTransitions, *nonvisited.begin(), res, nonvisited);
    }
 
    nonvisited = fsm.getStates();
 
    while(!nonvisited.empty ( )) {
        process(epsilonTransitions, *nonvisited.begin(), res, nonvisited);
    }
 
    return res;
}
 
template < class SymbolType, class StateType >
ext::map<StateType, ext::set<StateType>> AllEpsilonClosure::allEpsilonClosure( const automaton::MultiInitialStateNFA < SymbolType, StateType > & fsm) {
    ext::map<StateType, ext::set<StateType>> closure;
    for(const StateType& state : fsm.getStates())
        closure[state].insert(state);
    return closure;
}
 
template < class SymbolType, class StateType >
ext::map<StateType, ext::set<StateType>> AllEpsilonClosure::allEpsilonClosure( const automaton::NFA < SymbolType, StateType > & fsm) {
    ext::map<StateType, ext::set<StateType>> closure;
    for(const StateType& state : fsm.getStates())
        closure[state].insert(state);
    return closure;
}
 
template < class SymbolType, class StateType >
ext::map<StateType, ext::set<StateType>> AllEpsilonClosure::allEpsilonClosure( const automaton::DFA < SymbolType, StateType > & fsm) {
    ext::map<StateType, ext::set<StateType>> closure;
    for(const StateType& state : fsm.getStates())
        closure[state].insert(state);
    return closure;
}
 
template < class SymbolType, class StateType >
ext::map<StateType, ext::set<StateType>> AllEpsilonClosure::allEpsilonClosure( const automaton::ExtendedNFA < SymbolType, StateType > & fsm) {
    ext::map<StateType, ext::set<StateType>> res;
 
    for(const StateType& state : fsm.getStates())
        res[state].insert(state);
 
    ext::set<StateType> nonvisited = fsm.getStates();
 
    ext::multimap<StateType, StateType> epsilonTransitions;
    for(const std::pair<const ext::pair<StateType, regexp::UnboundedRegExpStructure < SymbolType > >, StateType >& transition : fsm.getTransitions() )
        if( regexp::properties::RegExpEpsilon::languageContainsEpsilon( transition.first.second ) )
            epsilonTransitions.insert ( transition.first.first, transition.second );
 
    while(!nonvisited.empty ( )) {
        process(epsilonTransitions, *nonvisited.begin(), res, nonvisited);
    }
 
    nonvisited = fsm.getStates();
 
    while(!nonvisited.empty ( )) {
        process(epsilonTransitions, *nonvisited.begin(), res, nonvisited);
    }
 
    return res;
}
 
template < class SymbolType, class StateType >
ext::map<StateType, ext::set<StateType>> AllEpsilonClosure::allEpsilonClosure( const automaton::CompactNFA < SymbolType, StateType > & fsm) {
    ext::map<StateType, ext::set<StateType>> res;
 
    for(const StateType& state : fsm.getStates())
        res[state].insert(state);
 
    ext::set<StateType> nonvisited = fsm.getStates();
 
    ext::multimap<StateType, StateType > epsilonTransitions;
    for(const std::pair<const ext::pair<StateType, ext::vector < SymbolType > >, StateType >& transition : fsm.getTransitions() )
        if( transition.first.second.empty ( ) )
            epsilonTransitions.insert ( transition.first.first, transition.second );
 
    while(!nonvisited.empty ( )) {
        process(epsilonTransitions, *nonvisited.begin(), res, nonvisited);
    }
 
    nonvisited = fsm.getStates();
 
    while(!nonvisited.empty ( )) {
        process(epsilonTransitions, *nonvisited.begin(), res, nonvisited);
    }
 
    return res;
}
 
} /* namespace efficient */
 
} /* namespace properties */
 
} /* namespace automaton */