20 #ifndef FST_CONNECT_H_ 21 #define FST_CONNECT_H_ 48 : comps_(comps), cc_(nullptr), nstates_(0) {}
51 if (cc_)
delete comps_;
64 comps_->
Union(s, arc.nextstate);
69 comps_->
Union(s, arc.nextstate);
74 comps_->
Union(s, arc.nextstate);
90 for (
StateId s = 0; s < nstates_; ++s) {
91 const auto rep = comps_->
FindSet(s);
92 auto &comp = (*cc)[rep];
104 std::vector<StateId> *cc_;
125 SccVisitor(std::vector<StateId> *scc, std::vector<bool> *access,
126 std::vector<bool> *coaccess, uint64_t *props)
127 : scc_(scc), access_(access), coaccess_(coaccess), props_(props) {}
129 : scc_(nullptr), access_(nullptr), coaccess_(nullptr), props_(props) {}
138 const auto t = arc.nextstate;
139 if (dfnumber_[t] < lowlink_[s]) lowlink_[s] = dfnumber_[t];
140 if ((*coaccess_)[t]) (*coaccess_)[s] =
true;
151 const auto t = arc.nextstate;
152 if (dfnumber_[t] < dfnumber_[s] && onstack_[t] &&
153 dfnumber_[t] < lowlink_[s]) {
154 lowlink_[s] = dfnumber_[t];
156 if ((*coaccess_)[t]) (*coaccess_)[s] =
true;
166 for (
size_t s = 0; s < scc_->size(); ++s) {
167 (*scc_)[s] = nscc_ - 1 - (*scc_)[s];
170 if (coaccess_internal_)
delete coaccess_;
174 std::vector<StateId> *scc_;
175 std::vector<bool> *access_;
176 std::vector<bool> *coaccess_;
182 bool coaccess_internal_;
183 std::vector<StateId> dfnumber_;
186 std::vector<bool> onstack_;
187 std::vector<StateId> scc_stack_;
192 if (scc_) scc_->clear();
193 if (access_) access_->clear();
196 coaccess_internal_ =
false;
198 coaccess_ =
new std::vector<bool>;
199 coaccess_internal_ =
true;
204 start_ = fst.
Start();
215 scc_stack_.push_back(s);
216 if (static_cast<StateId>(dfnumber_.size()) <= s) {
217 if (scc_) scc_->resize(s + 1, -1);
218 if (access_) access_->resize(s + 1,
false);
219 coaccess_->resize(s + 1,
false);
220 dfnumber_.resize(s + 1, -1);
221 lowlink_.resize(s + 1, -1);
222 onstack_.resize(s + 1,
false);
224 dfnumber_[s] = nstates_;
225 lowlink_[s] = nstates_;
227 if (root == start_) {
228 if (access_) (*access_)[s] =
true;
230 if (access_) (*access_)[s] =
false;
240 if (fst_->Final(s) != Weight::Zero()) (*coaccess_)[s] =
true;
241 if (dfnumber_[s] == lowlink_[s]) {
242 bool scc_coaccess =
false;
243 auto i = scc_stack_.size();
247 if ((*coaccess_)[t]) scc_coaccess =
true;
250 t = scc_stack_.back();
251 if (scc_) (*scc_)[t] = nscc_;
252 if (scc_coaccess) (*coaccess_)[t] =
true;
254 scc_stack_.pop_back();
263 if ((*coaccess_)[s]) (*coaccess_)[p] =
true;
264 if (lowlink_[s] < lowlink_[p]) lowlink_[p] = lowlink_[s];
279 using StateId =
typename Arc::StateId;
280 std::vector<bool> access;
281 std::vector<bool> coaccess;
285 std::vector<StateId> dstates;
286 dstates.reserve(access.size());
287 for (
StateId s = 0; s < access.size(); ++s) {
288 if (!access[s] || !coaccess[s]) dstates.push_back(s);
299 std::vector<typename Arc::StateId> *scc) {
300 using StateId =
typename Arc::StateId;
305 const auto iter = std::max_element(scc->cbegin(), scc->cend());
306 if (iter == scc->cend())
return;
307 const StateId num_condensed_states = 1 + *iter;
309 for (
StateId c = 0; c < num_condensed_states; ++c) {
312 for (
StateId s = 0; s < scc->size(); ++s) {
313 const auto c = (*scc)[s];
315 const auto weight = ifst.
Final(s);
316 if (weight != Arc::Weight::Zero())
319 const auto &arc = aiter.Value();
320 const auto nextc = (*scc)[arc.nextstate];
322 Arc condensed_arc = arc;
323 condensed_arc.nextstate = nextc;
324 ofst->
AddArc(c, std::move(condensed_arc));
333 #endif // FST_CONNECT_H_
constexpr uint64_t kCyclic
SccVisitor(std::vector< StateId > *scc, std::vector< bool > *access, std::vector< bool > *coaccess, uint64_t *props)
void InitVisit(const Fst< Arc > &fst)
bool InitState(StateId s, StateId root)
bool BackArc(StateId s, const Arc &arc)
constexpr uint64_t kInitialCyclic
typename Arc::Weight Weight
ErrorWeight Plus(const ErrorWeight &, const ErrorWeight &)
constexpr uint64_t kCoAccessible
bool TreeArc(StateId s, const Arc &arc)
void FinishState(StateId s)
constexpr uint64_t kNotAccessible
void DfsVisit(const FST &fst, Visitor *visitor, ArcFilter filter, bool access_only=false)
constexpr uint64_t kInitialAcyclic
void InitVisit(const Fst< Arc > &fst)
bool GreyArc(StateId s, const Arc &arc)
SccVisitor(uint64_t *props)
virtual Weight Final(StateId) const =0
virtual void SetStart(StateId)=0
void Connect(MutableFst< Arc > *fst)
CcVisitor(std::vector< StateId > *cc)
typename Arc::StateId StateId
void FinishState(StateId state, StateId p, const Arc *)
bool WhiteArc(StateId s, const Arc &arc)
constexpr uint64_t kAcyclic
virtual void SetProperties(uint64_t props, uint64_t mask)=0
constexpr uint64_t kAccessible
int GetCcVector(std::vector< StateId > *cc)
virtual StateId Start() const =0
bool ForwardOrCrossArc(StateId s, const Arc &arc)
CcVisitor(UnionFind< StateId > *comps)
virtual void AddArc(StateId, const Arc &)=0
void Condense(const Fst< Arc > &ifst, MutableFst< Arc > *ofst, std::vector< typename Arc::StateId > *scc)
virtual StateId AddState()=0
virtual void ReserveStates(size_t)
virtual void SetFinal(StateId s, Weight weight=Weight::One())=0
virtual void DeleteStates(const std::vector< StateId > &)=0
constexpr uint64_t kNotCoAccessible
bool InitState(StateId s, StateId root)
bool BlackArc(StateId s, const Arc &arc)
typename Arc::StateId StateId
typename Arc::Weight Weight