7 #ifndef FST_STATE_REACHABLE_H_ 8 #define FST_STATE_REACHABLE_H_ 30 template <
class Arc,
class I =
typename Arc::StateId,
class S = IntervalSet<I>>
33 using Label =
typename Arc::Label;
42 std::vector<Index> *state2index)
45 state2index_(state2index),
46 index_(state2index->empty() ? 1 : -1),
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()) {
58 auto *intervals = (*isets_)[s].MutableIntervals();
61 FSTERROR() <<
"IntervalReachVisitor: state2index map must be empty " 66 const auto index = (*state2index_)[s];
68 FSTERROR() <<
"IntervalReachVisitor: state2index map incomplete";
72 intervals->push_back(
Interval(index, index + 1));
74 intervals->push_back(
Interval(index_, index_ + 1));
75 (*state2index_)[s] = index_++;
84 FSTERROR() <<
"IntervalReachVisitor: Cyclic input";
91 (*isets_)[s].Union((*isets_)[arc.nextstate]);
96 if (index_ >= 0 && fst_.
Final(s) != Weight::Zero()) {
97 auto *intervals = (*isets_)[s].MutableIntervals();
98 (*intervals)[0].end = index_;
100 (*isets_)[s].Normalize();
102 (*isets_)[p].Union((*isets_)[s]);
108 bool Error()
const {
return error_; }
112 std::vector<ISet> *isets_;
113 std::vector<Index> *state2index_;
122 template <
class Arc,
class I =
typename Arc::StateId,
class S = IntervalSet<I>>
135 AcyclicStateReachable(fst);
137 CyclicStateReachable(fst);
142 FSTERROR() <<
"Copy constructor for state reachable class " 143 <<
"not implemented.";
152 if (s >= state2index_.size())
return false;
153 const auto i = state2index_[s];
155 FSTERROR() <<
"StateReachable: State non-final: " << s;
159 return isets_[s_].Member(i);
169 bool Error()
const {
return error_; }
176 if (reach_visitor.
Error()) error_ =
true;
179 void CyclicStateReachable(
const Fst<Arc> &fst) {
182 std::vector<StateId> scc;
185 if (reachable.
Error()) {
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);
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];
206 if (cfst.
Final(c) != Weight::Zero() && nscc[c] > 1) {
207 FSTERROR() <<
"StateReachable: Final state contained in a cycle";
215 std::vector<ISet> isets_;
216 std::vector<Index> state2index_;
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)
virtual Weight Final(StateId) const =0
typename ISet::Interval Interval
typename Arc::Weight Weight
typename Arc::StateId StateId
constexpr bool TreeArc(StateId, const Arc &) const
virtual uint64 Properties(uint64 mask, bool test) const =0
typename ISet::Interval Interval
typename Arc::Weight Weight
typename Arc::Label Label
typename Arc::Label Label
constexpr uint64 kAcyclic
Weight Final(StateId s) const override
void Condense(const Fst< Arc > &ifst, MutableFst< Arc > *ofst, std::vector< typename Arc::StateId > *scc)
StateReachable(const Fst< Arc > &fst)
void FinishState(StateId s, StateId p, const Arc *)