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