00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021 #ifndef FST_LIB_DFS_VISIT_H__
00022 #define FST_LIB_DFS_VISIT_H__
00023
00024 #include <stack>
00025 #include <vector>
00026 #include <fst/arcfilter.h>
00027 #include <fst/fst.h>
00028
00029 namespace fst {
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064 const int kDfsWhite = 0;
00065 const int kDfsGrey = 1;
00066 const int kDfsBlack = 2;
00067
00068
00069 template <class Arc>
00070 struct DfsState {
00071 typedef typename Arc::StateId StateId;
00072
00073 DfsState(const Fst<Arc> &fst, StateId s): state_id(s), arc_iter(fst, s) {}
00074
00075 StateId state_id;
00076 ArcIterator< Fst<Arc> > arc_iter;
00077 };
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087 template <class Arc, class V, class ArcFilter>
00088 void DfsVisit(const Fst<Arc> &fst, V *visitor, ArcFilter filter) {
00089 typedef typename Arc::StateId StateId;
00090
00091 visitor->InitVisit(fst);
00092
00093 StateId start = fst.Start();
00094 if (start == kNoStateId) {
00095 visitor->FinishVisit();
00096 return;
00097 }
00098
00099 vector<char> state_color;
00100 stack<DfsState<Arc> *> state_stack;
00101
00102 StateId nstates = CountStates(fst);
00103
00104 while (state_color.size() < nstates)
00105 state_color.push_back(kDfsWhite);
00106
00107
00108 bool dfs = true;
00109
00110
00111 for (StateId root = start; dfs && root < nstates;) {
00112 state_color[root] = kDfsGrey;
00113 state_stack.push(new DfsState<Arc>(fst, root));
00114 dfs = visitor->InitState(root, root);
00115 while (!state_stack.empty()) {
00116 DfsState<Arc> *dfs_state = state_stack.top();
00117 StateId s = dfs_state->state_id;
00118 ArcIterator< Fst<Arc> > &aiter = dfs_state->arc_iter;
00119 if (!dfs || aiter.Done()) {
00120 state_color[s] = kDfsBlack;
00121 delete dfs_state;
00122 state_stack.pop();
00123 if (!state_stack.empty()) {
00124 DfsState<Arc> *parent_state = state_stack.top();
00125 StateId p = parent_state->state_id;
00126 ArcIterator< Fst<Arc> > &piter = parent_state->arc_iter;
00127 visitor->FinishState(s, p, &piter.Value());
00128 piter.Next();
00129 } else {
00130 visitor->FinishState(s, kNoStateId, 0);
00131 }
00132 continue;
00133 }
00134 const Arc &arc = aiter.Value();
00135 if (!filter(arc)) {
00136 aiter.Next();
00137 continue;
00138 }
00139 int next_color = state_color[arc.nextstate];
00140 switch (next_color) {
00141 default:
00142 case kDfsWhite:
00143 dfs = visitor->TreeArc(s, arc);
00144 if (!dfs) break;
00145 state_color[arc.nextstate] = kDfsGrey;
00146 state_stack.push(new DfsState<Arc>(fst, arc.nextstate));
00147 dfs = visitor->InitState(arc.nextstate, root);
00148 break;
00149 case kDfsGrey:
00150 dfs = visitor->BackArc(s, arc);
00151 aiter.Next();
00152 break;
00153 case kDfsBlack:
00154 dfs = visitor->ForwardOrCrossArc(s, arc);
00155 aiter.Next();
00156 break;
00157 }
00158 }
00159
00160 for (root = root == start ? 0 : root + 1;
00161 root < nstates && state_color[root] != kDfsWhite;
00162 ++root);
00163 }
00164 visitor->FinishVisit();
00165 }
00166
00167
00168 template <class Arc, class V>
00169 void DfsVisit(const Fst<Arc> &fst, V *visitor) {
00170 DfsVisit(fst, visitor, AnyArcFilter<Arc>());
00171 }
00172
00173 }
00174
00175 #endif // FST_LIB_DFS_VISIT_H__