automaton.h

Go to the documentation of this file.

// Copyright 2002-2018 CEA LIST
// SPDX-FileCopyrightText: 2022 CEA LIST <gael.de-chalendar@cea.fr>
//
// SPDX-License-Identifier: MIT
 
/************************************************************************
 *
 * @file       automaton.h
 * @author     besancon (besanconr@zoe.cea.fr)
 * @date       Fri Oct 04 2002
 * copyright   Copyright (C) 2002 by CEA LIST
 * Project     Automaton
 *
 * @brief      A class for the description of automata
 *
 *
 ***********************************************************************/
 
#ifndef AUTOMATON_H
#define AUTOMATON_H
 
#include "AutomatonExport.h"
#include "transitionUnit.h"
#include "searchGraph.h"
#include "transition.h"
#include "transitionSearchStructure.h"
#include "recognizerMatch.h"
#include "constraint.h"
#include "automatonReaderWriter.h"
#include "linguisticProcessing/core/LinguisticAnalysisStructure/AnalysisGraph.h"
 
#include <fstream>
#include <vector>
#include <set>
#include <string>
 
namespace Lima {
namespace LinguisticProcessing {
namespace Automaton {
 
class LIMA_AUTOMATON_EXPORT AutomatonControlParams {
 public:
  AutomatonControlParams();
  ~AutomatonControlParams();
 
  uint64_t getMaxDepthStack() const
    { return m_maxDepthStack; }
  uint64_t getMaxTransitionsExplored() const
    { return m_maxTransitionsExplored; }
  uint64_t getMaxNbResults() const
    { return m_maxNbResults; }
  uint64_t getMaxResultSize() const
    { return m_maxResultSize; }
 
  void setMaxDepthStack(const uint64_t val)
    { m_maxDepthStack=val; }
  void setMaxTransitionsExplored(const uint64_t val)
    { m_maxTransitionsExplored=val; }
  void setMaxNbResults(const uint64_t val)
    { m_maxNbResults=val; }
  void setMaxResultSize(const uint64_t val)
    { m_maxResultSize=val; }
 
 private:
  uint64_t m_maxDepthStack;
  uint64_t m_maxTransitionsExplored;
  uint64_t m_maxNbResults;
  uint64_t m_maxResultSize;
};
 
class LIMA_AUTOMATON_EXPORT Automaton
{
friend class AutomatonReader;
friend class AutomatonWriter;
 
public:
  Automaton( const std::string& automId = "" );
 
  Automaton(const Automaton& a);
 
  Automaton(const Tstate nbStates);
 
  ~Automaton();
 
  Automaton& operator= (const Automaton& a);
 
 
  //**********************************************************************
  Tstate numberOfStates() const;
 
  uint64_t numberOfTransitions() const;
 
  uint64_t numberOfTransitions(const Tstate state) const;
 
  Transition const& nthTransition(const Tstate state,
                  const uint64_t n) const;
 
  bool isFinalState(const Tstate state) const;
  std::vector<Tstate> finalStates() const;
  std::vector<Transition> const& getTransitionsState(const Tstate state) const;
 
  bool hasTransitionsState(const Tstate state) const;
 
  bool isDeterministic() const;
 
  void reinit();
 
   void setActionHash(const std::vector<std::pair<LimaString,Constraint> >& actionsWithOneArgument);
  typedef std::pair<RecognizerMatch,ConstraintCheckList> AutomatonMatch;
  class CompareAutomatonMatch {
  public:
    bool operator()(const AutomatonMatch& r1,
                    const AutomatonMatch& r2) const;
  };
  typedef std::set<AutomatonMatch,CompareAutomatonMatch>
    AutomatonMatchSet;
  bool getBestMatch(const LinguisticAnalysisStructure::AnalysisGraph& graph,
                    const LinguisticGraphVertex& begin,
                    const LinguisticGraphVertex& limit,
                    AnalysisContent& analysis,
                    RecognizerMatch& longestMatch,
                    ConstraintCheckList& checkList,
                    const SearchGraphSense sense,
                    const AutomatonControlParams& controlParams) const;
 
  bool getAllMatches(const LinguisticAnalysisStructure::AnalysisGraph& graph,
                     const LinguisticGraphVertex& begin,
                     const LinguisticGraphVertex& limit,
                     AnalysisContent& analysis,
                     AutomatonMatchSet& allMatches,
                     ConstraintCheckList& checkList,
                     ForwardSearch& forward,
                     BackwardSearch& backward,
                     const SearchGraphSense sense,
                     const AutomatonControlParams& controlParams) const;
 
 
  //----------------------------------------------------------------------
  // to build the automaton
  //----------------------------------------------------------------------
 
  Tstate addState(bool is_final=false);
  bool addTransition(Tstate initialState, Tstate finalState,
             TransitionUnit* transition);
 
  void removeState(const Tstate state);
  void removeTransition(const Tstate initialState,
            const TransitionUnit& transition);
  void makeFinal(const Tstate state);
  void unMakeFinal(const Tstate state);
  void setDeterministic(const bool det);
  Automaton subsets() const;
 
  Automaton reverse() const;
 
 
  Automaton brzozowskiMinimize() const;
 
  // for the output
  friend LIMA_AUTOMATON_EXPORT std::ostream& operator << (std::ostream& os, const Automaton& a);
  friend LIMA_AUTOMATON_EXPORT QDebug& operator << (QDebug& os, const Automaton& a);
 
  void initializeSearchStructures(MediaId language);
  bool getMatchingTransitions(const LinguisticAnalysisStructure::AnalysisGraph& graph,
                              const LinguisticGraphVertex& vertex,
                              AnalysisContent& analysis,
                              const SearchGraph* searchGraph,
                              const Tstate& state,
                              std::vector<std::pair<std::deque<LinguisticGraphVertex>,const Transition*> >& matchingTransitions,
                              const LinguisticGraphVertex& limit) const;
 
 protected:
  Tstate m_numberStates;    
  std::vector<bool> m_finalStates;  
  std::vector< std::vector<Transition> > m_transitions; 
  std::vector< TransitionSearchStructure<Transition>* > m_searchStructures;
  bool m_deterministic;        
  std::string m_id;         
  //private methods
  //**********************************************************************
  // helper functions for constructors and destructors
  void init();
  void copy(const Automaton& a);
  void freeMem();
 
  class DFSStack;
  friend LIMA_AUTOMATON_EXPORT std::ostream& operator << (std::ostream& os, const DFSStack& x);
  friend LIMA_AUTOMATON_EXPORT QDebug& operator << (QDebug& os, const DFSStack& x);
 
  bool testFromState(const Tstate firstState,
                     const LinguisticAnalysisStructure::AnalysisGraph& graph,
                     const LinguisticGraphVertex& begin,
                     const LinguisticGraphVertex& limit,
                     AnalysisContent& analysis,
                     AutomatonMatchSet& results,
                     ConstraintCheckList& checkList,
                     DFSStack& stack,
                     const AutomatonControlParams& controlParams) const;
 
  //************************************************************
  // helper functions for automaton construction and
  // determinization
  typedef std::set<Tstate> SubSet;
 
  bool existsEpsilonPathToFinal(const Tstate state) const;
  std::vector<TransitionUnit*> collectTransitions() const;
  bool isFinalSubset (const SubSet& v) const;
  void reachableStates(const SubSet& states,
                       const TransitionUnit& t,
                       SubSet& reachable) const;
  void reachableStates(const Tstate& state,
                       const TransitionUnit& t,
                       SubSet& reachable) const;
  std::string subsetString(const SubSet& subset) const; // for debug
};
/***********************************************************************/
// inline access functions
/***********************************************************************/
inline Tstate Automaton::numberOfStates() const {
  return m_numberStates;
}
 
inline uint64_t Automaton::numberOfTransitions(const Tstate state) const {
  return m_transitions[state].size();
}
 
inline Transition const&  Automaton::nthTransition(const Tstate state,
                           const uint64_t n) const {
  return m_transitions[state][n];
}
 
inline bool Automaton::isFinalState(const Tstate state) const {
  if (state >= m_numberStates) { return false; }
  return m_finalStates[state];
}
 
 
inline bool Automaton::isDeterministic() const {
  return m_deterministic;
}
 
inline std::vector<Transition> const&
Automaton::getTransitionsState(const Tstate state) const {
  return m_transitions[state];
}
 
} // end namespace
} // end namespace
} // end namespace
 
#endif