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