| // dfs-visit.h |
| |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| // |
| // Copyright 2005-2010 Google, Inc. |
| // Author: riley@google.com (Michael Riley) |
| // |
| // \file |
| // Depth-first search visitation. See visit.h for more general |
| // search queue disciplines. |
| |
| #ifndef FST_LIB_DFS_VISIT_H__ |
| #define FST_LIB_DFS_VISIT_H__ |
| |
| #include <stack> |
| #include <vector> |
| using std::vector; |
| |
| #include <fst/arcfilter.h> |
| #include <fst/fst.h> |
| |
| |
| namespace fst { |
| |
| // Visitor Interface - class determines actions taken during a Dfs. |
| // If any of the boolean member functions return false, the DFS is |
| // aborted by first calling FinishState() on all currently grey states |
| // and then calling FinishVisit(). |
| // |
| // Note this is similar to the more general visitor interface in visit.h |
| // except that FinishState returns additional information appropriate only for |
| // a DFS and some methods names here are better suited to a DFS. |
| // |
| // template <class Arc> |
| // class Visitor { |
| // public: |
| // typedef typename Arc::StateId StateId; |
| // |
| // Visitor(T *return_data); |
| // // Invoked before DFS visit |
| // void InitVisit(const Fst<Arc> &fst); |
| // // Invoked when state discovered (2nd arg is DFS tree root) |
| // bool InitState(StateId s, StateId root); |
| // // Invoked when tree arc examined (to white/undiscovered state) |
| // bool TreeArc(StateId s, const Arc &a); |
| // // Invoked when back arc examined (to grey/unfinished state) |
| // bool BackArc(StateId s, const Arc &a); |
| // // Invoked when forward or cross arc examined (to black/finished state) |
| // bool ForwardOrCrossArc(StateId s, const Arc &a); |
| // // Invoked when state finished (PARENT is kNoStateID and ARC == NULL |
| // // when S is tree root) |
| // void FinishState(StateId s, StateId parent, const Arc *parent_arc); |
| // // Invoked after DFS visit |
| // void FinishVisit(); |
| // }; |
| |
| // An Fst state's DFS status |
| const int kDfsWhite = 0; // Undiscovered |
| const int kDfsGrey = 1; // Discovered & unfinished |
| const int kDfsBlack = 2; // Finished |
| |
| // An Fst state's DFS stack state |
| template <class Arc> |
| struct DfsState { |
| typedef typename Arc::StateId StateId; |
| |
| DfsState(const Fst<Arc> &fst, StateId s): state_id(s), arc_iter(fst, s) {} |
| |
| StateId state_id; // Fst state ... |
| ArcIterator< Fst<Arc> > arc_iter; // and its corresponding arcs |
| }; |
| |
| |
| // Performs depth-first visitation. Visitor class argument determines |
| // actions and contains any return data. ArcFilter determines arcs |
| // that are considered. |
| // |
| // Note this is similar to Visit() in visit.h called with a LIFO |
| // queue except this version has a Visitor class specialized and |
| // augmented for a DFS. |
| template <class Arc, class V, class ArcFilter> |
| void DfsVisit(const Fst<Arc> &fst, V *visitor, ArcFilter filter) { |
| typedef typename Arc::StateId StateId; |
| |
| visitor->InitVisit(fst); |
| |
| StateId start = fst.Start(); |
| if (start == kNoStateId) { |
| visitor->FinishVisit(); |
| return; |
| } |
| |
| vector<char> state_color; // Fst state DFS status |
| stack<DfsState<Arc> *> state_stack; // DFS execution stack |
| |
| StateId nstates = start + 1; // # of known states in general case |
| bool expanded = false; |
| if (fst.Properties(kExpanded, false)) { // tests if expanded case, then |
| nstates = CountStates(fst); // uses ExpandedFst::NumStates(). |
| expanded = true; |
| } |
| |
| state_color.resize(nstates, kDfsWhite); |
| StateIterator< Fst<Arc> > siter(fst); |
| |
| // Continue DFS while true |
| bool dfs = true; |
| |
| // Iterate over trees in DFS forest. |
| for (StateId root = start; dfs && root < nstates;) { |
| state_color[root] = kDfsGrey; |
| state_stack.push(new DfsState<Arc>(fst, root)); |
| dfs = visitor->InitState(root, root); |
| while (!state_stack.empty()) { |
| DfsState<Arc> *dfs_state = state_stack.top(); |
| StateId s = dfs_state->state_id; |
| if (s >= state_color.size()) { |
| nstates = s + 1; |
| state_color.resize(nstates, kDfsWhite); |
| } |
| ArcIterator< Fst<Arc> > &aiter = dfs_state->arc_iter; |
| if (!dfs || aiter.Done()) { |
| state_color[s] = kDfsBlack; |
| delete dfs_state; |
| state_stack.pop(); |
| if (!state_stack.empty()) { |
| DfsState<Arc> *parent_state = state_stack.top(); |
| StateId p = parent_state->state_id; |
| ArcIterator< Fst<Arc> > &piter = parent_state->arc_iter; |
| visitor->FinishState(s, p, &piter.Value()); |
| piter.Next(); |
| } else { |
| visitor->FinishState(s, kNoStateId, 0); |
| } |
| continue; |
| } |
| const Arc &arc = aiter.Value(); |
| if (arc.nextstate >= state_color.size()) { |
| nstates = arc.nextstate + 1; |
| state_color.resize(nstates, kDfsWhite); |
| } |
| if (!filter(arc)) { |
| aiter.Next(); |
| continue; |
| } |
| int next_color = state_color[arc.nextstate]; |
| switch (next_color) { |
| default: |
| case kDfsWhite: |
| dfs = visitor->TreeArc(s, arc); |
| if (!dfs) break; |
| state_color[arc.nextstate] = kDfsGrey; |
| state_stack.push(new DfsState<Arc>(fst, arc.nextstate)); |
| dfs = visitor->InitState(arc.nextstate, root); |
| break; |
| case kDfsGrey: |
| dfs = visitor->BackArc(s, arc); |
| aiter.Next(); |
| break; |
| case kDfsBlack: |
| dfs = visitor->ForwardOrCrossArc(s, arc); |
| aiter.Next(); |
| break; |
| } |
| } |
| |
| // Find next tree root |
| for (root = root == start ? 0 : root + 1; |
| root < nstates && state_color[root] != kDfsWhite; |
| ++root); |
| |
| // Check for a state beyond the largest known state |
| if (!expanded && root == nstates) { |
| for (; !siter.Done(); siter.Next()) { |
| if (siter.Value() == nstates) { |
| ++nstates; |
| state_color.push_back(kDfsWhite); |
| break; |
| } |
| } |
| } |
| } |
| visitor->FinishVisit(); |
| } |
| |
| |
| template <class Arc, class V> |
| void DfsVisit(const Fst<Arc> &fst, V *visitor) { |
| DfsVisit(fst, visitor, AnyArcFilter<Arc>()); |
| } |
| |
| } // namespace fst |
| |
| #endif // FST_LIB_DFS_VISIT_H__ |