ComposableModelSearch.hh

Go to the documentation of this file.

#ifndef __DIADES__AUTOMATA__COMPOSABLEMODELSEARCH_HH_
#define __DIADES__AUTOMATA__COMPOSABLEMODELSEARCH_HH_

#include"Diagnosis.hh"
#include"ComposableModel.hh"
#include"FaultDiagProblem.hh"

namespace Diades
{
  namespace Automata
  {

        class DiagState
        {
        private:
          State _state;
          unordered_set<Event> _faults;
          unsigned _obsNb;
        public:
          DiagState(const State & state, const unordered_set<Event> & faults, unsigned obsNb):_state(state),_faults(faults),_obsNb(obsNb){}
          DiagState(const DiagState & dstate):_state(dstate.state()),_faults(dstate.faults()),_obsNb(dstate.obsNb()){}
          const State & state() const { return _state; }
          const unordered_set<Event> & faults() const { return _faults; }
          unsigned obsNb() const { return _obsNb; }
          void addFault(const Event & event) { _faults.insert(event); }
          unsigned incrObsNb() { return ++_obsNb; }
          void setState(const State & state) { _state = state; }
          bool operator==(const DiagState & dstate) const { return (state() == dstate.state()) && (obsNb() == dstate.obsNb()) && (faults().size() == dstate.faults().size()) && (faults() == dstate.faults()); }
          bool operator!=(const DiagState & dstate) const { return !(*this == dstate); }
  
        };


        inline ostream & operator << (ostream & os, const DiagState & dstate)
        {
          return os  << "(state= " << dstate.state() << ", nbObs=" << dstate.obsNb() << ", faults= " << toStream(dstate.faults().begin(), dstate.faults().end()) << ")";
        }

        class VisitedDiagState
        {
        public:
          typedef DiagState Node;
          typedef ComposableModel Graph;
          
        private:
          Diades::Graph::ConstNodeMap< vector< list< unordered_set<Event> > > > _visited;
        public:
          VisitedDiagState(const ComposableModel & model):_visited(model.component().behaviour()){}
          void mark(const Node & s)
          {
                if(_visited[s.state()].size() <= s.obsNb())
                  {
                        _visited[s.state()].resize(s.obsNb()+1);
                  }
                _visited[s.state()][s.obsNb()].push_back(s.faults());
          }

          bool isMarked(const Node & s)
          {
                if(_visited[s.state()].size() <= s.obsNb())
                  {
                        return false;
                  }
                return find(_visited[s.state()][s.obsNb()].begin(),
                                        _visited[s.state()][s.obsNb()].end(),s.faults()) != _visited[s.state()][s.obsNb()].end();
          }

          
          void unmark(const Node & s)
          {
                if(isMarked(s))
                  {
                        list< unordered_set<Event> >::iterator it = find(_visited[s.state()][s.obsNb()].begin(),
                                                                                                                         _visited[s.state()][s.obsNb()].end(),s.faults());
                        _visited[s.state()][s.obsNb()].erase(it);
                  }
          }
          
        };

        class IncorrectPath
        {
        public:
          typedef Transition Edge;
          typedef ComposableModel Graph;
        private:
          const Graph & _model;
          const unordered_set<Event> & _observables;
          const vector<EventOccurrence> & _observations;
  
        public:
          IncorrectPath(const Graph & model,
                                        const unordered_set<Event> & observables,
                                        const vector<EventOccurrence> & observations):_model(model),_observables(observables),_observations(observations){}
          bool noGood(unsigned nbObs, const Edge & t) const
          {
                if(_observables.find(_model.component().getEvent(t)) == _observables.end())
                  {
                        return false;
                  }
                return !(_observations[nbObs].second == _model.component().getEvent(t));
          }

        };


        class NextTransitions
        {
        public:
          typedef DiagState Node;
          typedef Transition Edge;
          typedef ComposableModel Graph;

        private:
          const Graph & _model;
          const Node & _dstate;
          const IncorrectPath & _cut;
        public:

          struct Iterator
          {
                typedef Iterator   self;
                typedef ptrdiff_t            difference_type;
                typedef std::forward_iterator_tag    iterator_category;
                typedef Edge   value_type;
                typedef Edge*  pointer;
                typedef Edge&  reference;
        
                ComposableModel::OutputTransitionIterator _it;
                ComposableModel::OutputTransitionIterator _end;
                unsigned _nbObs;
                const IncorrectPath * _cut;
        
                Iterator(): _it(),_end(),_nbObs(0),_cut(nullptr){}
                
                explicit Iterator(const Graph::OutputTransitionIterator & it,const Graph::OutputTransitionIterator & end, unsigned nbObs, const IncorrectPath & cut) : _it(it), _end(end),_nbObs(nbObs),_cut(&cut)
                {
                  while((_it != _end) && (_cut->noGood(_nbObs,*_it)))
                        {
                          ++_it;
                        }
                }
         
        
                reference operator*() const
                {  
                  return *_it;
                }

                pointer operator->() const
                {
                  return &(*_it);
                }

                self & operator++()
                {
                  ++_it;
                  while((_it != _end) && (_cut->noGood(_nbObs,*_it)))
                        {
                          ++_it;
                        }
                  return *this;
                }

                self operator++(int)
                {
                  self tmp = *this;
                  ++_it;
                  while((_it != _end) && (_cut->noGood(_nbObs,*_it)))
                        {
                          ++_it;
                        }
                  return tmp;
                }

        

                bool operator==(const self & it) const
                {
                  return (_it == it._it) && (_end == it._end) && (_cut == it._cut) && (_nbObs == it._nbObs);
                }

                bool operator !=(const self & it) const
                {
                  return !(*this == it);
                }

          };


          NextTransitions(const Graph & model, const Node & dstate, const IncorrectPath & cut):
                _model(model), _dstate(dstate), _cut(cut){}
          Iterator begin() const { return Iterator(_model.outputTransitionBegin(_dstate.state()),_model.outputTransitionEnd(_dstate.state()),_dstate.obsNb(),_cut); }
          Iterator end() const { return Iterator(_model.outputTransitionEnd(_dstate.state()),_model.outputTransitionEnd(_dstate.state()),_dstate.obsNb(),_cut); }
        };


        class TargetDiagState
        {
        public:
          typedef DiagState Node;
          typedef Transition Edge;
          typedef ComposableModel Graph;
          
        private:
          const Graph & _model;
          const unordered_set<Event> & _observables;
          const unordered_set<Event> & _faults;
  
        public:
          TargetDiagState(const Graph & model,
                                          const unordered_set<Event> & observables,
                                          const unordered_set<Event> & faults):_model(model),_observables(observables),_faults(faults){}
  
          Node next(const Edge & t, const Node & s) const 
          {
                Node result = s;
                if(_faults.find(_model.component().getEvent(t)) != _faults.end())
                  {
                        result.addFault(_model.component().getEvent(t));
                  }
                if(_observables.find(_model.component().getEvent(t)) != _observables.end())
                  {
                        result.incrObsNb();
                  }
                result.setState(t.target());
                return result;
          }


        };

        class IsCandidate
        {
        public:
          typedef DiagState Node;
        private:
          const vector<EventOccurrence> & _observations;
        public:
          IsCandidate(const vector<EventOccurrence> & observations):_observations(observations){}
          bool isSolution(const Node & s){ if(s.obsNb() == _observations.size()) { cout << "Solution part: " << s << endl; }
                return s.obsNb() == _observations.size();
          }
          
        };


        template<class Algorithm>
        class ComposableModelSearch
        {
        private:
          list<typename Algorithm::Search::Node> _initialDiagStates;
          list<typename Algorithm::Search::Node> _results;
          typename Algorithm::Search::Solution * _isCandidate;
          typename Algorithm::Search::PathCut * _incorrectPath;
          typename Algorithm::Search::Opposite * _targetDiagState;
          Diagnosis _diagnosis;
          const FaultDiagProblem & _problem;
          ComposableModel *  _model;
          vector<const ComposableModel *> _compModels;
          Algorithm * _search;
          
        public:
          ComposableModelSearch(const FaultDiagProblem & problem):_initialDiagStates(),_results(),_isCandidate(nullptr),
                                                                                         _incorrectPath(nullptr),_targetDiagState(nullptr),
                                                                                         _diagnosis(),_problem(problem),_model(nullptr),
                                                                                         _compModels(),_search(nullptr){}


          ~ComposableModelSearch() { destroy(); }

          
          void destroy()
          {
                _results.clear();
                _initialDiagStates.clear();
                if(_search != nullptr)
                  {
                        delete _search; _search = nullptr;
                  }
                if(_isCandidate != nullptr)
                  {
                        delete _isCandidate; _isCandidate = nullptr;
                  }
                if(_incorrectPath != nullptr)
                  {
                        delete _incorrectPath; _incorrectPath = nullptr;
                  }
                if(_targetDiagState != nullptr)
                  {
                        delete _targetDiagState; _targetDiagState = nullptr;
                  }
                if(_model != nullptr)
                  {
                        delete _model;
                        _model=nullptr;
                  }
                if(!_compModels.empty())
                  {
                        for(unsigned i = 0; i < _compModels.size(); ++i)
                          {
                                if(_compModels[i] != nullptr)
                                  {
                                        delete _compModels[i];
                                        _compModels[i]=nullptr;
                                  }
                          }
                        _compModels.clear();
                  }
          }
          void initialize()
          {
                destroy();

                if(problem().components().size() == 1)
                  {
                        _compModels.push_back(new ComposableModel(*problem().components().begin(),problem().rules()));
                        _model =new ComposableModel(*problem().components().begin(),problem().rules());
                  }
                else
                  {
                        // initialise the component models
                        for(const ObservableComponent & comp : problem().components())
                          {
                                _compModels.push_back(new ComposableModel(comp,problem().rules()));
                          }
                
                        // initialise the search by creating a composable model that will be
                        // computed on the fly
                        _model = new ComposableModel(_compModels,problem().rules(),true);
                  }
                
                _isCandidate = new typename Algorithm::Search::Solution(problem().observations());
                _incorrectPath = new typename Algorithm::Search::PathCut(*_model,problem().observables(),problem().observations());
                _targetDiagState = new typename Algorithm::Search::Opposite(*_model,problem().observables(), problem().faults());
                
                for(ComposableModel::InitialStateIterator it = _model->beginOfInitialStates();
                        it != _model->endOfInitialStates();
                        ++it)
                  {
                        _initialDiagStates.push_back(typename Algorithm::Search::Node(*it,unordered_set<Event>(),0));
                  }
                
                // create and initialise the BFS
                _search = new Algorithm(*_model,_initialDiagStates,*_targetDiagState,*_isCandidate,*_incorrectPath,_results);
                _search->initialize();
          }

          bool finished() const { return (_search != nullptr) && _search->finished(); }
          void next() { _search->next(); }
          bool updated() const { return (_search != nullptr) && _search->updated(); }
          const Diagnosis & diagnosis()
          {
                if(updated())
                  {
                        _diagnosis.clear();
                        for(const typename Algorithm::Search::Node & state : _search->currentResults())
                          {
                                vector< set<Event> > faults(max((int) _model->models().size(), 1));
                                if(_model->models().size() == 0)
                                  {
                                        faults[0].insert(state.faults().begin(),state.faults().end());
                                  }
                                else
                                  {
                                        for(const Event & fault: state.faults())
                                          {
                                                unsigned i = 0;
                                                bool found =false;
                                                while(!found && (i < _model->models().size()))
                                                  {
                                                        found = _model->models().operator[](i)->component().containsEvent(fault);
                                                        if(found)
                                                          {
                                                                faults[i].insert(fault);
                                                          }
                                                        ++i;
                                                  }
                                          }
                                  }
                                vector<Diades::Graph::Node::NodeId> stateIds;
                                for(unsigned i = 0; i < _model->vectorStateOf(state.state()).size(); ++i)
                                  {
                                        stateIds.push_back(_model->vectorStateOf(state.state()).operator[](i).id());
                                  }
                                _diagnosis.addCandidate(Candidate(stateIds,faults));
                          }
                  }
                return _diagnosis;
          }

          const FaultDiagProblem & problem() const
          {
                return _problem;
          }
        };





        
  };
};

#endif