FST  openfst-1.8.2
OpenFst Library
dfs-visit.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 // Depth-first search visitation. See visit.h for more general search queue
19 // disciplines.
20 
21 #ifndef FST_DFS_VISIT_H_
22 #define FST_DFS_VISIT_H_
23 
24 #include <cstdint>
25 #include <stack>
26 #include <vector>
27 
28 #include <fst/arcfilter.h>
29 #include <fst/fst.h>
30 
31 
32 namespace fst {
33 
34 // Visitor Interface: class determining actions taken during a depth-first
35 // search-style visit. If any of the boolean member functions return false, the
36 // DFS is aborted by first calling FinishState() on all currently grey states
37 // and then calling FinishVisit().
38 //
39 // This is similar to the more general visitor interface in visit.h, except
40 // that FinishState returns additional information appropriate only for a DFS
41 // and some methods names here are better suited to a DFS.
42 //
43 // template <class Arc>
44 // class Visitor {
45 // public:
46 // using StateId = typename Arc::StateId;
47 //
48 // Visitor(T *return_data);
49 //
50 // // Invoked before DFS visit.
51 // void InitVisit(const Fst<Arc> &fst);
52 //
53 // // Invoked when state discovered (2nd arg is DFS tree root).
54 // bool InitState(StateId s, StateId root);
55 //
56 // // Invoked when tree arc to white/undiscovered state examined.
57 // bool TreeArc(StateId s, const Arc &arc);
58 //
59 // // Invoked when back arc to grey/unfinished state examined.
60 // bool BackArc(StateId s, const Arc &arc);
61 //
62 // // Invoked when forward or cross arc to black/finished state examined.
63 // bool ForwardOrCrossArc(StateId s, const Arc &arc);
64 //
65 // // Invoked when state finished ('s' is tree root, 'parent' is kNoStateId,
66 // // and 'arc' is nullptr).
67 // void FinishState(StateId s, StateId parent, const Arc *arc);
68 //
69 // // Invoked after DFS visit.
70 // void FinishVisit();
71 // };
72 
73 namespace internal {
74 
75 // An FST state's DFS stack state.
76 template <class FST>
77 struct DfsState {
78  using Arc = typename FST::Arc;
79  using StateId = typename Arc::StateId;
80 
81  DfsState(const FST &fst, StateId s) : state_id(s), arc_iter(fst, s) {}
82 
83  void *operator new(size_t size, MemoryPool<DfsState<FST>> *pool) {
84  return pool->Allocate();
85  }
86 
87  static void Destroy(DfsState<FST> *dfs_state,
88  MemoryPool<DfsState<FST>> *pool) {
89  if (dfs_state) {
90  dfs_state->~DfsState<FST>();
91  pool->Free(dfs_state);
92  }
93  }
94 
95  StateId state_id; // FST state.
96  ArcIterator<FST> arc_iter; // The corresponding arcs.
97 };
98 
99 } // namespace internal
100 
101 // Performs depth-first visitation. Visitor class argument determines actions
102 // and contains any return data. ArcFilter determines arcs that are considered.
103 // If 'access_only' is true, performs visitation only to states accessible from
104 // the initial state.
105 //
106 // Note this is similar to Visit() in visit.h called with a LIFO queue, except
107 // this version has a Visitor class specialized and augmented for a DFS.
108 template <class FST, class Visitor, class ArcFilter>
109 void DfsVisit(const FST &fst, Visitor *visitor, ArcFilter filter,
110  bool access_only = false) {
111  visitor->InitVisit(fst);
112  const auto start = fst.Start();
113  if (start == kNoStateId) {
114  visitor->FinishVisit();
115  return;
116  }
117  // An FST state's DFS status
118  enum class StateColor : uint8_t {
119  kWhite = 0, // Undiscovered.
120  kGrey = 1, // Discovered but unfinished.
121  kBlack = 2, // Finished.
122  };
123  std::vector<StateColor> state_color;
124  std::stack<internal::DfsState<FST> *> state_stack; // DFS execution stack.
125  MemoryPool<internal::DfsState<FST>> state_pool; // Pool for DFSStates.
126  auto nstates = start + 1; // Number of known states in general case.
127  bool expanded = false;
128  if (fst.Properties(kExpanded, false)) { // Tests if expanded case, then
129  nstates = CountStates(fst); // uses ExpandedFst::NumStates().
130  expanded = true;
131  }
132  state_color.resize(nstates, StateColor::kWhite);
133  StateIterator<FST> siter(fst);
134  // Continue DFS while true.
135  bool dfs = true;
136  // Iterate over trees in DFS forest.
137  for (auto root = start; dfs && root < nstates;) {
138  state_color[root] = StateColor::kGrey;
139  state_stack.push(new (&state_pool) internal::DfsState<FST>(fst, root));
140  dfs = visitor->InitState(root, root);
141  while (!state_stack.empty()) {
142  auto *dfs_state = state_stack.top();
143  const auto s = dfs_state->state_id;
144  if (s >= static_cast<decltype(s)>(state_color.size())) {
145  nstates = s + 1;
146  state_color.resize(nstates, StateColor::kWhite);
147  }
148  ArcIterator<FST> &aiter = dfs_state->arc_iter;
149  if (!dfs || aiter.Done()) {
150  state_color[s] = StateColor::kBlack;
151  internal::DfsState<FST>::Destroy(dfs_state, &state_pool);
152  state_stack.pop();
153  if (!state_stack.empty()) {
154  auto *parent_state = state_stack.top();
155  auto &piter = parent_state->arc_iter;
156  visitor->FinishState(s, parent_state->state_id, &piter.Value());
157  piter.Next();
158  } else {
159  visitor->FinishState(s, kNoStateId, nullptr);
160  }
161  continue;
162  }
163  const auto &arc = aiter.Value();
164  if (arc.nextstate >=
165  static_cast<decltype(arc.nextstate)>(state_color.size())) {
166  nstates = arc.nextstate + 1;
167  state_color.resize(nstates, StateColor::kWhite);
168  }
169  if (!filter(arc)) {
170  aiter.Next();
171  continue;
172  }
173  const auto next_color = state_color[arc.nextstate];
174  switch (next_color) {
175  case StateColor::kWhite:
176  dfs = visitor->TreeArc(s, arc);
177  if (!dfs) break;
178  state_color[arc.nextstate] = StateColor::kGrey;
179  state_stack.push(new (&state_pool)
180  internal::DfsState<FST>(fst, arc.nextstate));
181  dfs = visitor->InitState(arc.nextstate, root);
182  break;
183  case StateColor::kGrey:
184  dfs = visitor->BackArc(s, arc);
185  aiter.Next();
186  break;
187  case StateColor::kBlack:
188  dfs = visitor->ForwardOrCrossArc(s, arc);
189  aiter.Next();
190  break;
191  }
192  }
193  if (access_only) break;
194  // Finds next tree root.
195  for (root = root == start ? 0 : root + 1;
196  root < nstates && state_color[root] != StateColor::kWhite; ++root) {
197  }
198  // Checks for a state beyond the largest known state.
199  if (!expanded && root == nstates) {
200  for (; !siter.Done(); siter.Next()) {
201  if (siter.Value() == nstates) {
202  ++nstates;
203  state_color.push_back(StateColor::kWhite);
204  break;
205  }
206  }
207  }
208  }
209  visitor->FinishVisit();
210 }
211 
212 template <class Arc, class Visitor>
213 void DfsVisit(const Fst<Arc> &fst, Visitor *visitor) {
214  DfsVisit(fst, visitor, AnyArcFilter<Arc>());
215 }
216 
217 } // namespace fst
218 
219 #endif // FST_DFS_VISIT_H_
static void Destroy(DfsState< FST > *dfs_state, MemoryPool< DfsState< FST >> *pool)
Definition: dfs-visit.h:87
void DfsVisit(const FST &fst, Visitor *visitor, ArcFilter filter, bool access_only=false)
Definition: dfs-visit.h:109
constexpr int kNoStateId
Definition: fst.h:202
const Arc & Value() const
Definition: fst.h:537
DfsState(const FST &fst, StateId s)
Definition: dfs-visit.h:81
typename Arc::StateId StateId
Definition: dfs-visit.h:79
StateId Value() const
Definition: fst.h:419
bool Done() const
Definition: fst.h:533
ArcIterator< FST > arc_iter
Definition: dfs-visit.h:96
Arc::StateId CountStates(const Fst< Arc > &fst)
Definition: expanded-fst.h:169
void Next()
Definition: fst.h:421
bool Done() const
Definition: fst.h:415
typename FST::Arc Arc
Definition: dfs-visit.h:78
constexpr uint64_t kExpanded
Definition: properties.h:45
void Next()
Definition: fst.h:541