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