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