UsefulStates.h

Go to the documentation of this file.

 
#pragma once
 
#include <algorithm>
#include <deque>
#include <set>
#include <map>
 
#include <automaton/FSM/ExtendedNFA.h>
#include <automaton/FSM/CompactNFA.h>
#include <automaton/FSM/EpsilonNFA.h>
#include <automaton/FSM/NFA.h>
#include <automaton/FSM/DFA.h>
 
namespace automaton {
 
namespace properties {
 
namespace efficient {
 
class UsefulStates {
public:
    template < class T >
    static ext::set < typename T::StateType > usefulStates( const T & fsm );
};
 
template < class T >
ext::set < typename T::StateType > UsefulStates::usefulStates( const T & fsm ) {
    using StateType = typename T::StateType;
 
    ext::map<StateType, ext::set<StateType>> reversedTransitions;
    for(const auto& transition : fsm.getTransitions())
        reversedTransitions [ transition.second ].insert(transition.first.first);
 
    ext::deque<StateType> queue ( fsm.getFinalStates( ).begin(), fsm.getFinalStates().end() );
    ext::set<StateType> visited = fsm.getFinalStates( );
 
    while( !queue.empty() ) {
        const ext::set<StateType>& to = reversedTransitions[queue.front()];
        queue.pop_front();
 
        for(const StateType& process : to)
            if(visited.insert(process).second) {
                queue.push_back(std::move(const_cast<StateType&>(process)));
            }
    }
 
    return visited;
}
 
} /* namespace efficient */
 
} /* namespace properties */
 
} /* namespace automaton */