src/include/fst/state-reachable.h

// state-reachable.h

// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// Copyright 2005-2010 Google, Inc.
// Author: riley@google.com (Michael Riley)
//
// \file
// Class to determine whether a given (final) state can be reached from some
// other given state.

#ifndef FST_LIB_STATE_REACHABLE_H__
#define FST_LIB_STATE_REACHABLE_H__

#include <vector>
using std::vector;

#include <fst/dfs-visit.h>
#include <fst/fst.h>
#include <fst/interval-set.h>


namespace fst {

// Computes the (final) states reachable from a given state in an FST.
// After this visitor has been called, a final state f can be reached
// from a state s iff (*isets)[s].Member(state2index[f]) is true, where
// (*isets[s]) is a set of half-open inteval of final state indices
// and state2index[f] maps from a final state to its index.
//
// If state2index is empty, it is filled-in with suitable indices.
// If it is non-empty, those indices are used; in this case, the
// final states must have out-degree 0.
template <class A, typename I = typename A::StateId>
class IntervalReachVisitor {
 public:
  typedef typename A::StateId StateId;
  typedef typename A::Label Label;
  typedef typename A::Weight Weight;
  typedef typename IntervalSet<I>::Interval Interval;

  IntervalReachVisitor(const Fst<A> &fst,
                       vector< IntervalSet<I> > *isets,
                       vector<I> *state2index)
      : fst_(fst),
        isets_(isets),
        state2index_(state2index),
        index_(state2index->empty() ? 1 : -1),
        error_(false) {
    isets_->clear();
  }

  void InitVisit(const Fst<A> &fst) { error_ = false; }

  bool InitState(StateId s, StateId r) {
    while (isets_->size() <= s)
      isets_->push_back(IntervalSet<Label>());
    while (state2index_->size() <= s)
      state2index_->push_back(-1);

    if (fst_.Final(s) != Weight::Zero()) {
      // Create tree interval
      vector<Interval> *intervals = (*isets_)[s].Intervals();
      if (index_ < 0) {  // Use state2index_ map to set index
        if (fst_.NumArcs(s) > 0) {
          FSTERROR() << "IntervalReachVisitor: state2index map must be empty "
                     << "for this FST";
          error_ = true;
          return false;
        }
        I index = (*state2index_)[s];
        if (index < 0) {
          FSTERROR() << "IntervalReachVisitor: state2index map incomplete";
          error_ = true;
          return false;
        }
        intervals->push_back(Interval(index, index + 1));
      } else {           // Use pre-order index
        intervals->push_back(Interval(index_, index_ + 1));
        (*state2index_)[s] = index_++;
      }
    }
    return true;
  }

  bool TreeArc(StateId s, const A &arc) {
    return true;
  }

  bool BackArc(StateId s, const A &arc) {
    FSTERROR() << "IntervalReachVisitor: cyclic input";
    error_ = true;
    return false;
  }

  bool ForwardOrCrossArc(StateId s, const A &arc) {
    // Non-tree interval
    (*isets_)[s].Union((*isets_)[arc.nextstate]);
    return true;
  }

  void FinishState(StateId s, StateId p, const A *arc) {
    if (index_ >= 0 && fst_.Final(s) != Weight::Zero()) {
      vector<Interval> *intervals = (*isets_)[s].Intervals();
      (*intervals)[0].end = index_;      // Update tree interval end
    }
    (*isets_)[s].Normalize();
    if (p != kNoStateId)
      (*isets_)[p].Union((*isets_)[s]);  // Propagate intervals to parent
  }

  void FinishVisit() {}

  bool Error() const { return error_; }

 private:
  const Fst<A> &fst_;
  vector< IntervalSet<I> > *isets_;
  vector<I> *state2index_;
  I index_;
  bool error_;
};


// Tests reachability of final states from a given state. To test for
// reachability from a state s, first do SetState(s). Then a final
// state f can be reached from state s of FST iff Reach(f) is true.
template <class A, typename I = typename A::StateId>
class StateReachable {
 public:
  typedef A Arc;
  typedef I Index;
  typedef typename A::StateId StateId;
  typedef typename A::Label Label;
  typedef typename A::Weight Weight;
  typedef typename IntervalSet<I>::Interval Interval;

  StateReachable(const Fst<A> &fst)
      : error_(false) {
    IntervalReachVisitor<Arc> reach_visitor(fst, &isets_, &state2index_);
    DfsVisit(fst, &reach_visitor);
    if (reach_visitor.Error()) error_ = true;
  }

  StateReachable(const StateReachable<A> &reachable) {
    FSTERROR() << "Copy constructor for state reachable class "
               << "not yet implemented.";
    error_ = true;
  }

  // Set current state.
  void SetState(StateId s) { s_ = s; }

  // Can reach this label from current state?
  bool Reach(StateId s) {
    if (s >= state2index_.size())
      return false;

    I i =  state2index_[s];
    if (i < 0) {
      FSTERROR() << "StateReachable: state non-final: " << s;
      error_ = true;
      return false;
    }
    return isets_[s_].Member(i);
  }

  // Access to the state-to-index mapping. Unassigned states have index -1.
  vector<I> &State2Index() { return state2index_; }

  // Access to the interval sets. These specify the reachability
  // to the final states as intervals of the final state indices.
  const vector< IntervalSet<I> > &IntervalSets() { return isets_; }

  bool Error() const { return error_; }

 private:
  StateId s_;                                 // Current state
  vector< IntervalSet<I> > isets_;            // Interval sets per state
  vector<I> state2index_;                     // Finds index for a final state
  bool error_;

  void operator=(const StateReachable<A> &);  // Disallow
};

}  // namespace fst

#endif  // FST_LIB_STATE_REACHABLE_H__