Determine.hh

Go to the documentation of this file.

#ifndef __DIADES__AUTOMATA__DETERMINE__HH
#define __DIADES__AUTOMATA__DETERMINE__HH

#include<list>
#include<diades/utils/Assertion.hh>
#include<diades/utils/Exceptions.hh>
#include<diades/graph/GraphNodeSetTable.hh>
#include<diades/automata/experimental/StateMachine.hh>
#include<diades/automata/experimental/StateCreation.hh>
#include<diades/automata/experimental/BeliefState.hh>


namespace Diades
{
  namespace Automata
  {
    namespace Experimental
    {
      template<typename Fsm>
      bool
      isDeterministic(const Fsm & machine) {
        using State = typename Fsm::State;
        using Transition = typename Fsm::Transition;
        return std::find_if(machine.stateBegin(), machine.stateEnd(),
                            [&](State s) {
                              return std::find_if(machine.outputTransitionBegin(s), machine.outputTransitionEnd(s),
                                                  [&](Transition t) {
                                                    auto evt = machine.getEvent(t);
                                                    return (++machine.outputEventTransitionBegin(s, evt)) !=
                                                      machine.outputEventTransitionEnd(s, evt);
                                                  }) != machine.outputTransitionEnd(s);
                            }) == machine.stateEnd();
      }

      template<typename Fsm, typename StateCreator>
      void
      determine(const Fsm & machine,
                Fsm & deterministicMachine,
                StateCreator & creator) 
      {
        require(Diades::Utils::FunctionException,
                &machine != &deterministicMachine,
                "determine: the determination algorithm cannot be applied on the current StateMachine");
        deterministicMachine.clear();
        deterministicMachine.setName("deterministic_" + machine.name());
        deterministicMachine.copyEventPropertyIds(machine);
        if (machine.isEmpty() || machine.numberOfInitialStates() == 0) {
          return;
        }
        typedef BeliefState<Fsm> FsmBs;
        typedef Diades::Graph::GraphNodeSetTable<typename Fsm::State> BeliefStateTable;
        BeliefStateTable bsTable;
        std::list<typename FsmBs::SharedPtr> bs;
        std::list<typename Fsm::State> states;
        bs.push_back(std::make_shared<FsmBs>(machine));
        bs.back()->insertStates(machine.initialStateBegin(), machine.initialStateEnd());
        bool found = !bs.back()->isEmpty();
                
        if (found) {
          bool result;
          typename Fsm::State initialState;
          std::tie(initialState,result) = creator.newState(*bs.back());
                    
                    
                    
                    
          states.push_back(bsTable.insertIfNotFound(*bs.back().get(), initialState, found));
          deterministicMachine.setInitial(initialState);
                      
              while (!bs.empty()) {
                auto currentBs = bs.front();
                auto sourceState = states.front();
                for (auto & event : machine.events()) {
                  typename FsmBs::SharedPtr newBs = currentBs->nextBeliefState(event);
                  if (newBs->isEmpty()) {
                    newBs.reset();
                  } else {
                    auto targetState = bsTable.getInfo(*newBs.get(),found);
                                if (!found) {
                                    std::tie(targetState,result) = creator.newState(*newBs.get()); 
                                    targetState = bsTable.insertIfNotFound(*newBs.get(),targetState,found);
                                    bs.push_back(newBs);
                                    states.push_back(targetState);
                                } else {
                                    newBs.reset();
                                }
                                deterministicMachine.newTransition(sourceState, targetState, event);
                            }
                        }
                        bs.front().reset();
                        bs.pop_front();
                        states.pop_front();
                    }
                }
            }
        }
    }
}



#endif /* __DIADES__AUTOMATA__DETERMINE__HH */