diff options
Diffstat (limited to 'kaldi_io/src/tools/openfst/include/fst/state-reachable.h')
| -rw-r--r-- | kaldi_io/src/tools/openfst/include/fst/state-reachable.h | 198 |
1 files changed, 0 insertions, 198 deletions
diff --git a/kaldi_io/src/tools/openfst/include/fst/state-reachable.h b/kaldi_io/src/tools/openfst/include/fst/state-reachable.h deleted file mode 100644 index 6d0c971..0000000 --- a/kaldi_io/src/tools/openfst/include/fst/state-reachable.h +++ /dev/null @@ -1,198 +0,0 @@ -// 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: [email protected] (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__ |