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 27namespace 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 58const int kDfsWhite = 0; // Undiscovered 59const int kDfsGrey = 1; // Discovered & unfinished 60const int kDfsBlack = 2; // Finished 61 62// An Fst state's DFS stack state 63template <class Arc> 64struct DfsState { 65 typedef typename Arc::StateId StateId; 66 67 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. 76template <class Arc, class V, class ArcFilter> 77void 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 157template <class Arc, class V> 158void 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