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 //
16 // \file
17 // Depth-first search visitation
18
19 #ifndef FST_LIB_DFS_VISIT_H__
20 #define FST_LIB_DFS_VISIT_H__
21
22 #include <stack>
23
24 #include "fst/lib/arcfilter.h"
25 #include "fst/lib/expanded-fst.h"
26
27 namespace fst {
28
29 // Visitor Interface - class determines actions taken during a Dfs.
30 // If any of the boolean member functions return false, the DFS is
31 // aborted by first calling FinishState() on all currently grey states
32 // and then calling FinishVisit().
33 //
34 // template <class Arc>
35 // class Visitor {
36 // public:
37 // typedef typename Arc::StateId StateId;
38 //
39 // Visitor(T *return_data);
40 // // Invoked before DFS visit
41 // void InitVisit(const Fst<Arc> &fst);
42 // // Invoked when state discovered (2nd arg is DFS tree root)
43 // bool InitState(StateId s, StateId root);
44 // // Invoked when tree arc examined (to white/undiscovered state)
45 // bool TreeArc(StateId s, const Arc &a);
46 // // Invoked when back arc examined (to grey/unfinished state)
47 // bool BackArc(StateId s, const Arc &a);
48 // // Invoked when forward or cross arc examined (to black/finished state)
49 // bool ForwardOrCrossArc(StateId s, const Arc &a);
50 // // Invoked when state finished (PARENT is kNoStateID and ARC == NULL
51 // // when S is tree root)
52 // void FinishState(StateId s, StateId parent, const Arc *parent_arc);
53 // // Invoked after DFS visit
54 // void FinishVisit();
55 // };
56
57 // An Fst state's DFS status
58 const int kDfsWhite = 0; // Undiscovered
59 const int kDfsGrey = 1; // Discovered & unfinished
60 const int kDfsBlack = 2; // Finished
61
62 // An Fst state's DFS stack state
63 template <class Arc>
64 struct DfsState {
65 typedef typename Arc::StateId StateId;
66
DfsStateDfsState67 DfsState(const Fst<Arc> &fst, StateId s): state_id(s), arc_iter(fst, s) {}
68
69 StateId state_id; // Fst state ...
70 ArcIterator< Fst<Arc> > arc_iter; // and its corresponding arcs
71 };
72
73
74 // Performs depth-first visitation. Visitor class argument determines actions
75 // and contains any return data. ArcFilter determines arcs that are considered.
76 template <class Arc, class V, class ArcFilter>
DfsVisit(const Fst<Arc> & fst,V * visitor,ArcFilter filter)77 void DfsVisit(const Fst<Arc> &fst, V *visitor, ArcFilter filter) {
78 typedef typename Arc::StateId StateId;
79
80 visitor->InitVisit(fst);
81
82 StateId start = fst.Start();
83 if (start == kNoStateId) {
84 visitor->FinishVisit();
85 return;
86 }
87
88 vector<char> state_color; // Fst state DFS status
89 stack<DfsState<Arc> *> state_stack; // DFS execution stack
90
91 StateId nstates = CountStates(fst);
92
93 while ((StateId)state_color.size() < nstates)
94 state_color.push_back(kDfsWhite);
95
96 // Continue DFS while true
97 bool dfs = true;
98
99 // Iterate over trees in DFS forest.
100 for (StateId root = start; dfs && root < nstates;) {
101 state_color[root] = kDfsGrey;
102 state_stack.push(new DfsState<Arc>(fst, root));
103 dfs = visitor->InitState(root, root);
104 while (!state_stack.empty()) {
105 DfsState<Arc> *dfs_state = state_stack.top();
106 StateId s = dfs_state->state_id;
107 ArcIterator< Fst<Arc> > &aiter = dfs_state->arc_iter;
108 if (!dfs || aiter.Done()) {
109 state_color[s] = kDfsBlack;
110 delete dfs_state;
111 state_stack.pop();
112 if (!state_stack.empty()) {
113 DfsState<Arc> *parent_state = state_stack.top();
114 StateId p = parent_state->state_id;
115 ArcIterator< Fst<Arc> > &piter = parent_state->arc_iter;
116 visitor->FinishState(s, p, &piter.Value());
117 piter.Next();
118 } else {
119 visitor->FinishState(s, kNoStateId, 0);
120 }
121 continue;
122 }
123 const Arc &arc = aiter.Value();
124 if (!filter(arc)) {
125 aiter.Next();
126 continue;
127 }
128 int next_color = state_color[arc.nextstate];
129 switch (next_color) {
130 default:
131 case kDfsWhite:
132 dfs = visitor->TreeArc(s, arc);
133 if (!dfs) break;
134 state_color[arc.nextstate] = kDfsGrey;
135 state_stack.push(new DfsState<Arc>(fst, arc.nextstate));
136 dfs = visitor->InitState(arc.nextstate, root);
137 break;
138 case kDfsGrey:
139 dfs = visitor->BackArc(s, arc);
140 aiter.Next();
141 break;
142 case kDfsBlack:
143 dfs = visitor->ForwardOrCrossArc(s, arc);
144 aiter.Next();
145 break;
146 }
147 }
148 // Find next tree root
149 for (root = root == start ? 0 : root + 1;
150 root < nstates && state_color[root] != kDfsWhite;
151 ++root);
152 }
153 visitor->FinishVisit();
154 }
155
156
157 template <class Arc, class V>
DfsVisit(const Fst<Arc> & fst,V * visitor)158 void DfsVisit(const Fst<Arc> &fst, V *visitor) {
159 DfsVisit(fst, visitor, AnyArcFilter<Arc>());
160 }
161
162 } // namespace fst
163
164 #endif // FST_LIB_DFS_VISIT_H__
165