FST  openfst-1.8.3
OpenFst Library
cc-visitors.h
Go to the documentation of this file.
1 // Copyright 2005-2024 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 // Classes to visit connected components of an FST.
19 
20 #ifndef FST_CC_VISITORS_H_
21 #define FST_CC_VISITORS_H_
22 
23 #include <cstdint>
24 #include <vector>
25 
26 #include <fst/fst.h>
27 #include <fst/union-find.h>
28 
29 namespace fst {
30 
31 // Finds and returns connected components. Use with Visit().
32 template <class Arc>
33 class CcVisitor {
34  public:
35  using Weight = typename Arc::Weight;
36  using StateId = typename Arc::StateId;
37 
38  // cc[i]: connected component number for state i.
39  explicit CcVisitor(std::vector<StateId> *cc)
40  : comps_(new UnionFind<StateId>(0, kNoStateId)), cc_(cc), nstates_(0) {}
41 
42  // comps: connected components equiv classes.
43  explicit CcVisitor(UnionFind<StateId> *comps)
44  : comps_(comps), cc_(nullptr), nstates_(0) {}
45 
47  if (cc_) delete comps_;
48  }
49 
50  void InitVisit(const Fst<Arc> &fst) {}
51 
52  bool InitState(StateId s, StateId root) {
53  ++nstates_;
54  if (comps_->FindSet(s) == kNoStateId) comps_->MakeSet(s);
55  return true;
56  }
57 
58  bool WhiteArc(StateId s, const Arc &arc) {
59  comps_->MakeSet(arc.nextstate);
60  comps_->Union(s, arc.nextstate);
61  return true;
62  }
63 
64  bool GreyArc(StateId s, const Arc &arc) {
65  comps_->Union(s, arc.nextstate);
66  return true;
67  }
68 
69  bool BlackArc(StateId s, const Arc &arc) {
70  comps_->Union(s, arc.nextstate);
71  return true;
72  }
73 
74  void FinishState(StateId s) {}
75 
76  void FinishVisit() {
77  if (cc_) GetCcVector(cc_);
78  }
79 
80  // Returns number of components.
81  // cc[i]: connected component number for state i.
82  int GetCcVector(std::vector<StateId> *cc) {
83  cc->clear();
84  cc->resize(nstates_, kNoStateId);
85  StateId ncomp = 0;
86  for (StateId s = 0; s < nstates_; ++s) {
87  const auto rep = comps_->FindSet(s);
88  auto &comp = (*cc)[rep];
89  if (comp == kNoStateId) {
90  comp = ncomp;
91  ++ncomp;
92  }
93  (*cc)[s] = comp;
94  }
95  return ncomp;
96  }
97 
98  private:
99  UnionFind<StateId> *comps_; // Components.
100  std::vector<StateId> *cc_; // State's cc number.
101  StateId nstates_; // State count.
102 };
103 
104 // Finds and returns strongly-connected components, accessible and
105 // coaccessible states and related properties. Uses Tarjan's single
106 // DFS SCC algorithm (see Aho, et al, "Design and Analysis of Computer
107 // Algorithms", 189pp). Use with DfsVisit();
108 template <class Arc>
109 class SccVisitor {
110  public:
111  using StateId = typename Arc::StateId;
112  using Weight = typename Arc::Weight;
113 
114  // scc[i]: strongly-connected component number for state i.
115  // SCC numbers will be in topological order for acyclic input.
116  // access[i]: accessibility of state i.
117  // coaccess[i]: coaccessibility of state i.
118  // Any of above can be NULL.
119  // props: related property bits (cyclicity, initial cyclicity,
120  // accessibility, coaccessibility) set/cleared (o.w. unchanged).
121  SccVisitor(std::vector<StateId> *scc, std::vector<bool> *access,
122  std::vector<bool> *coaccess, uint64_t *props)
123  : scc_(scc), access_(access), coaccess_(coaccess), props_(props) {}
124  explicit SccVisitor(uint64_t *props)
125  : scc_(nullptr), access_(nullptr), coaccess_(nullptr), props_(props) {}
126 
127  void InitVisit(const Fst<Arc> &fst);
128 
129  bool InitState(StateId s, StateId root);
130 
131  bool TreeArc(StateId s, const Arc &arc) { return true; }
132 
133  bool BackArc(StateId s, const Arc &arc) {
134  const auto t = arc.nextstate;
135  if (dfnumber_[t] < lowlink_[s]) lowlink_[s] = dfnumber_[t];
136  if ((*coaccess_)[t]) (*coaccess_)[s] = true;
137  *props_ |= kCyclic;
138  *props_ &= ~kAcyclic;
139  if (t == start_) {
140  *props_ |= kInitialCyclic;
141  *props_ &= ~kInitialAcyclic;
142  }
143  return true;
144  }
145 
146  bool ForwardOrCrossArc(StateId s, const Arc &arc) {
147  const auto t = arc.nextstate;
148  if (dfnumber_[t] < dfnumber_[s] /* cross edge */ && onstack_[t] &&
149  dfnumber_[t] < lowlink_[s]) {
150  lowlink_[s] = dfnumber_[t];
151  }
152  if ((*coaccess_)[t]) (*coaccess_)[s] = true;
153  return true;
154  }
155 
156  // Last argument always ignored, but required by the interface.
157  void FinishState(StateId state, StateId p, const Arc *);
158 
159  void FinishVisit() {
160  // Numbers SCCs in topological order when acyclic.
161  if (scc_) {
162  for (size_t s = 0; s < scc_->size(); ++s) {
163  (*scc_)[s] = nscc_ - 1 - (*scc_)[s];
164  }
165  }
166  if (coaccess_internal_) delete coaccess_;
167  }
168 
169  private:
170  std::vector<StateId> *scc_; // State's scc number.
171  std::vector<bool> *access_; // State's accessibility.
172  std::vector<bool> *coaccess_; // State's coaccessibility.
173  uint64_t *props_;
174  const Fst<Arc> *fst_;
175  StateId start_;
176  StateId nstates_; // State count.
177  StateId nscc_; // SCC count.
178  bool coaccess_internal_;
179  std::vector<StateId> dfnumber_; // State discovery times.
180  std::vector<StateId>
181  lowlink_; // lowlink[state] == dfnumber[state] => SCC root
182  std::vector<bool> onstack_; // Is a state on the SCC stack?
183  std::vector<StateId> scc_stack_; // SCC stack, with random access.
184 };
185 
186 template <class Arc>
188  if (scc_) scc_->clear();
189  if (access_) access_->clear();
190  if (coaccess_) {
191  coaccess_->clear();
192  coaccess_internal_ = false;
193  } else {
194  coaccess_ = new std::vector<bool>;
195  coaccess_internal_ = true;
196  }
199  fst_ = &fst;
200  start_ = fst.Start();
201  nstates_ = 0;
202  nscc_ = 0;
203  dfnumber_.clear();
204  lowlink_.clear();
205  onstack_.clear();
206  scc_stack_.clear();
207 }
208 
209 template <class Arc>
211  scc_stack_.push_back(s);
212  if (static_cast<StateId>(dfnumber_.size()) <= s) {
213  if (scc_) scc_->resize(s + 1, -1);
214  if (access_) access_->resize(s + 1, false);
215  coaccess_->resize(s + 1, false);
216  dfnumber_.resize(s + 1, -1);
217  lowlink_.resize(s + 1, -1);
218  onstack_.resize(s + 1, false);
219  }
220  dfnumber_[s] = nstates_;
221  lowlink_[s] = nstates_;
222  onstack_[s] = true;
223  if (root == start_) {
224  if (access_) (*access_)[s] = true;
225  } else {
226  if (access_) (*access_)[s] = false;
227  *props_ |= kNotAccessible;
228  *props_ &= ~kAccessible;
229  }
230  ++nstates_;
231  return true;
232 }
233 
234 template <class Arc>
235 inline void SccVisitor<Arc>::FinishState(StateId s, StateId p, const Arc *) {
236  if (fst_->Final(s) != Weight::Zero()) (*coaccess_)[s] = true;
237  if (dfnumber_[s] == lowlink_[s]) { // Root of new SCC.
238  bool scc_coaccess = false;
239  auto i = scc_stack_.size();
240  StateId t;
241  do {
242  t = scc_stack_[--i];
243  if ((*coaccess_)[t]) scc_coaccess = true;
244  } while (s != t);
245  do {
246  t = scc_stack_.back();
247  if (scc_) (*scc_)[t] = nscc_;
248  if (scc_coaccess) (*coaccess_)[t] = true;
249  onstack_[t] = false;
250  scc_stack_.pop_back();
251  } while (s != t);
252  if (!scc_coaccess) {
253  *props_ |= kNotCoAccessible;
254  *props_ &= ~kCoAccessible;
255  }
256  ++nscc_;
257  }
258  if (p != kNoStateId) {
259  if ((*coaccess_)[s]) (*coaccess_)[p] = true;
260  if (lowlink_[s] < lowlink_[p]) lowlink_[p] = lowlink_[s];
261  }
262 }
263 
264 } // namespace fst
265 
266 #endif // FST_CC_VISITORS_H_
void FinishVisit()
Definition: cc-visitors.h:76
constexpr uint64_t kCyclic
Definition: properties.h:109
SccVisitor(std::vector< StateId > *scc, std::vector< bool > *access, std::vector< bool > *coaccess, uint64_t *props)
Definition: cc-visitors.h:121
void InitVisit(const Fst< Arc > &fst)
Definition: cc-visitors.h:50
bool InitState(StateId s, StateId root)
Definition: cc-visitors.h:52
bool BackArc(StateId s, const Arc &arc)
Definition: cc-visitors.h:133
constexpr uint64_t kInitialCyclic
Definition: properties.h:114
typename Arc::Weight Weight
Definition: cc-visitors.h:35
constexpr uint64_t kCoAccessible
Definition: properties.h:129
bool TreeArc(StateId s, const Arc &arc)
Definition: cc-visitors.h:131
void FinishState(StateId s)
Definition: cc-visitors.h:74
constexpr uint64_t kNotAccessible
Definition: properties.h:126
constexpr uint64_t kInitialAcyclic
Definition: properties.h:116
void InitVisit(const Fst< Arc > &fst)
Definition: cc-visitors.h:187
bool GreyArc(StateId s, const Arc &arc)
Definition: cc-visitors.h:64
SccVisitor(uint64_t *props)
Definition: cc-visitors.h:124
CcVisitor(std::vector< StateId > *cc)
Definition: cc-visitors.h:39
constexpr int kNoStateId
Definition: fst.h:196
typename Arc::StateId StateId
Definition: cc-visitors.h:111
void FinishState(StateId state, StateId p, const Arc *)
Definition: cc-visitors.h:235
bool WhiteArc(StateId s, const Arc &arc)
Definition: cc-visitors.h:58
void FinishVisit()
Definition: cc-visitors.h:159
constexpr uint64_t kAcyclic
Definition: properties.h:111
constexpr uint64_t kAccessible
Definition: properties.h:124
int GetCcVector(std::vector< StateId > *cc)
Definition: cc-visitors.h:82
virtual StateId Start() const =0
bool ForwardOrCrossArc(StateId s, const Arc &arc)
Definition: cc-visitors.h:146
CcVisitor(UnionFind< StateId > *comps)
Definition: cc-visitors.h:43
void Union(T x, T y)
Definition: union-find.h:56
T MakeSet(T item)
Definition: union-find.h:60
constexpr uint64_t kNotCoAccessible
Definition: properties.h:131
bool InitState(StateId s, StateId root)
Definition: cc-visitors.h:210
bool BlackArc(StateId s, const Arc &arc)
Definition: cc-visitors.h:69
T FindSet(T item)
Definition: union-find.h:39
typename Arc::StateId StateId
Definition: cc-visitors.h:36
typename Arc::Weight Weight
Definition: cc-visitors.h:112