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