FST  openfst-1.8.2
OpenFst Library
state-reachable.h
Go to the documentation of this file.
1 // Copyright 2005-2020 Google LLC
2 //
3 // Licensed under the Apache License, Version 2.0 (the 'License');
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an 'AS IS' BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 //
15 // See www.openfst.org for extensive documentation on this weighted
16 // finite-state transducer library.
17 //
18 // Class to determine whether a given (final) state can be reached from some
19 // other given state.
20 
21 #ifndef FST_STATE_REACHABLE_H_
22 #define FST_STATE_REACHABLE_H_
23 
24 #include <vector>
25 
26 #include <fst/log.h>
27 
28 #include <fst/connect.h>
29 #include <fst/dfs-visit.h>
30 #include <fst/fst.h>
31 #include <fst/interval-set.h>
32 #include <fst/vector-fst.h>
33 
34 
35 namespace fst {
36 
37 // Computes the (final) states reachable from a given state in an FST. After
38 // this visitor has been called, a final state f can be reached from a state
39 // s iff (*isets)[s].Member(state2index[f]) is true, where (*isets[s]) is a
40 // set of half-open inteval of final state indices and state2index[f] maps from
41 // a final state to its index. If state2index is empty, it is filled-in with
42 // suitable indices. If it is non-empty, those indices are used; in this case,
43 // the final states must have out-degree 0.
44 template <class Arc, class I = typename Arc::StateId, class S = IntervalSet<I>>
46  public:
47  using Label = typename Arc::Label;
48  using StateId = typename Arc::StateId;
49  using Weight = typename Arc::Weight;
50 
51  using Index = I;
52  using ISet = S;
53  using Interval = typename ISet::Interval;
54 
55  IntervalReachVisitor(const Fst<Arc> &fst, std::vector<S> *isets,
56  std::vector<Index> *state2index)
57  : fst_(fst),
58  isets_(isets),
59  state2index_(state2index),
60  index_(state2index->empty() ? 1 : -1),
61  error_(false) {
62  isets_->clear();
63  }
64 
65  void InitVisit(const Fst<Arc> &) { error_ = false; }
66 
67  bool InitState(StateId s, StateId r) {
68  while (isets_->size() <= s) isets_->push_back(S());
69  while (state2index_->size() <= s) state2index_->push_back(-1);
70  if (fst_.Final(s) != Weight::Zero()) {
71  // Create tree interval.
72  auto *intervals = (*isets_)[s].MutableIntervals();
73  if (index_ < 0) { // Uses state2index_ map to set index.
74  if (fst_.NumArcs(s) > 0) {
75  FSTERROR() << "IntervalReachVisitor: state2index map must be empty "
76  << "for this FST";
77  error_ = true;
78  return false;
79  }
80  const auto index = (*state2index_)[s];
81  if (index < 0) {
82  FSTERROR() << "IntervalReachVisitor: state2index map incomplete";
83  error_ = true;
84  return false;
85  }
86  intervals->push_back(Interval(index, index + 1));
87  } else { // Use pre-order index.
88  intervals->push_back(Interval(index_, index_ + 1));
89  (*state2index_)[s] = index_++;
90  }
91  }
92  return true;
93  }
94 
95  constexpr bool TreeArc(StateId, const Arc &) const { return true; }
96 
97  bool BackArc(StateId s, const Arc &arc) {
98  FSTERROR() << "IntervalReachVisitor: Cyclic input";
99  error_ = true;
100  return false;
101  }
102 
103  bool ForwardOrCrossArc(StateId s, const Arc &arc) {
104  // Non-tree interval.
105  (*isets_)[s].Union((*isets_)[arc.nextstate]);
106  return true;
107  }
108 
109  void FinishState(StateId s, StateId p, const Arc *) {
110  if (index_ >= 0 && fst_.Final(s) != Weight::Zero()) {
111  auto *intervals = (*isets_)[s].MutableIntervals();
112  (*intervals)[0].end = index_; // Updates tree interval end.
113  }
114  (*isets_)[s].Normalize();
115  if (p != kNoStateId) {
116  (*isets_)[p].Union((*isets_)[s]); // Propagates intervals to parent.
117  }
118  }
119 
120  void FinishVisit() {}
121 
122  bool Error() const { return error_; }
123 
124  private:
125  const Fst<Arc> &fst_;
126  std::vector<ISet> *isets_;
127  std::vector<Index> *state2index_;
128  Index index_;
129  bool error_;
130 };
131 
132 // Tests reachability of final states from a given state. To test for
133 // reachability from a state s, first do SetState(s). Then a final state f can
134 // be reached from state s of FST iff Reach(f) is true. The input can be cyclic,
135 // but no cycle may contain a final state.
136 template <class Arc, class I = typename Arc::StateId, class S = IntervalSet<I>>
138  public:
139  using Label = typename Arc::Label;
140  using StateId = typename Arc::StateId;
141  using Weight = typename Arc::Weight;
142 
143  using Index = I;
144  using ISet = S;
145  using Interval = typename ISet::Interval;
146 
147  explicit StateReachable(const Fst<Arc> &fst) : error_(false) {
148  if (fst.Properties(kAcyclic, true)) {
149  AcyclicStateReachable(fst);
150  } else {
151  CyclicStateReachable(fst);
152  }
153  }
154 
155  explicit StateReachable(const StateReachable<Arc> &reachable) {
156  FSTERROR() << "Copy constructor for state reachable class "
157  << "not implemented.";
158  error_ = true;
159  }
160 
161  // Sets current state.
162  void SetState(StateId s) { s_ = s; }
163 
164  // Can reach this final state from current state?
165  bool Reach(StateId s) {
166  if (s >= state2index_.size()) return false;
167  const auto i = state2index_[s];
168  if (i < 0) {
169  FSTERROR() << "StateReachable: State non-final: " << s;
170  error_ = true;
171  return false;
172  }
173  return isets_[s_].Member(i);
174  }
175 
176  // Access to the state-to-index mapping. Unassigned states have index -1.
177  std::vector<Index> &State2Index() { return state2index_; }
178 
179  // Access to the interval sets. These specify the reachability to the final
180  // states as intervals of the final state indices.
181  const std::vector<ISet> &IntervalSets() { return isets_; }
182 
183  bool Error() const { return error_; }
184 
185  private:
186  void AcyclicStateReachable(const Fst<Arc> &fst) {
187  IntervalReachVisitor<Arc, StateId, ISet> reach_visitor(fst, &isets_,
188  &state2index_);
189  DfsVisit(fst, &reach_visitor);
190  if (reach_visitor.Error()) error_ = true;
191  }
192 
193  void CyclicStateReachable(const Fst<Arc> &fst) {
194  // Finds state reachability on the acyclic condensation FST.
195  VectorFst<Arc> cfst;
196  std::vector<StateId> scc;
197  Condense(fst, &cfst, &scc);
198  StateReachable reachable(cfst);
199  if (reachable.Error()) {
200  error_ = true;
201  return;
202  }
203  // Gets the number of states per SCC.
204  std::vector<size_t> nscc;
205  for (StateId s = 0; s < scc.size(); ++s) {
206  const auto c = scc[s];
207  while (c >= nscc.size()) nscc.push_back(0);
208  ++nscc[c];
209  }
210  // Constructs the interval sets and state index mapping for the original
211  // FST from the condensation FST.
212  state2index_.resize(scc.size(), -1);
213  isets_.resize(scc.size());
214  for (StateId s = 0; s < scc.size(); ++s) {
215  const auto c = scc[s];
216  isets_[s] = reachable.IntervalSets()[c];
217  state2index_[s] = reachable.State2Index()[c];
218  // Checks that each final state in an input FST is not contained in a
219  // cycle (i.e., not in a non-trivial SCC).
220  if (cfst.Final(c) != Weight::Zero() && nscc[c] > 1) {
221  FSTERROR() << "StateReachable: Final state contained in a cycle";
222  error_ = true;
223  return;
224  }
225  }
226  }
227 
228  StateId s_; // Current state.
229  std::vector<ISet> isets_; // Interval sets per state.
230  std::vector<Index> state2index_; // Finds index for a final state.
231  bool error_;
232 
233  StateReachable &operator=(const StateReachable &) = delete;
234 };
235 
236 } // namespace fst
237 
238 #endif // FST_STATE_REACHABLE_H_
bool InitState(StateId s, StateId r)
IntervalReachVisitor(const Fst< Arc > &fst, std::vector< S > *isets, std::vector< Index > *state2index)
void InitVisit(const Fst< Arc > &)
const std::vector< ISet > & IntervalSets()
virtual uint64_t Properties(uint64_t mask, bool test) const =0
StateReachable(const StateReachable< Arc > &reachable)
bool ForwardOrCrossArc(StateId s, const Arc &arc)
std::vector< Index > & State2Index()
virtual size_t NumArcs(StateId) const =0
bool BackArc(StateId s, const Arc &arc)
typename Arc::StateId StateId
void DfsVisit(const FST &fst, Visitor *visitor, ArcFilter filter, bool access_only=false)
Definition: dfs-visit.h:109
virtual Weight Final(StateId) const =0
typename ISet::Interval Interval
typename Arc::Weight Weight
constexpr int kNoStateId
Definition: fst.h:202
typename Arc::StateId StateId
constexpr bool TreeArc(StateId, const Arc &) const
#define FSTERROR()
Definition: util.h:53
typename ISet::Interval Interval
constexpr uint64_t kAcyclic
Definition: properties.h:110
typename Arc::Weight Weight
typename Arc::Label Label
void SetState(StateId s)
typename Arc::Label Label
bool Reach(StateId s)
Weight Final(StateId s) const override
Definition: fst.h:952
void Condense(const Fst< Arc > &ifst, MutableFst< Arc > *ofst, std::vector< typename Arc::StateId > *scc)
Definition: connect.h:298
StateReachable(const Fst< Arc > &fst)
void FinishState(StateId s, StateId p, const Arc *)