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> 27using std::vector; 28 29#include <fst/arcfilter.h> 30#include <fst/fst.h> 31 32 33namespace 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 68const int kDfsWhite = 0; // Undiscovered 69const int kDfsGrey = 1; // Discovered & unfinished 70const int kDfsBlack = 2; // Finished 71 72// An Fst state's DFS stack state 73template <class Arc> 74struct DfsState { 75 typedef typename Arc::StateId StateId; 76 77 DfsState(const Fst<Arc> &fst, StateId s): state_id(s), arc_iter(fst, s) {} 78 79 StateId state_id; // Fst state ... 80 ArcIterator< Fst<Arc> > arc_iter; // and its corresponding arcs 81}; 82 83 84// Performs depth-first visitation. Visitor class argument determines 85// actions and contains any return data. ArcFilter determines arcs 86// that are considered. 87// 88// Note this is similar to Visit() in visit.h called with a LIFO 89// queue except this version has a Visitor class specialized and 90// augmented for a DFS. 91template <class Arc, class V, class ArcFilter> 92void DfsVisit(const Fst<Arc> &fst, V *visitor, ArcFilter filter) { 93 typedef typename Arc::StateId StateId; 94 95 visitor->InitVisit(fst); 96 97 StateId start = fst.Start(); 98 if (start == kNoStateId) { 99 visitor->FinishVisit(); 100 return; 101 } 102 103 vector<char> state_color; // Fst state DFS status 104 stack<DfsState<Arc> *> state_stack; // DFS execution stack 105 106 StateId nstates = start + 1; // # of known states in general case 107 bool expanded = false; 108 if (fst.Properties(kExpanded, false)) { // tests if expanded case, then 109 nstates = CountStates(fst); // uses ExpandedFst::NumStates(). 110 expanded = true; 111 } 112 113 state_color.resize(nstates, kDfsWhite); 114 StateIterator< Fst<Arc> > siter(fst); 115 116 // Continue DFS while true 117 bool dfs = true; 118 119 // Iterate over trees in DFS forest. 120 for (StateId root = start; dfs && root < nstates;) { 121 state_color[root] = kDfsGrey; 122 state_stack.push(new DfsState<Arc>(fst, root)); 123 dfs = visitor->InitState(root, root); 124 while (!state_stack.empty()) { 125 DfsState<Arc> *dfs_state = state_stack.top(); 126 StateId s = dfs_state->state_id; 127 if (s >= state_color.size()) { 128 nstates = s + 1; 129 state_color.resize(nstates, kDfsWhite); 130 } 131 ArcIterator< Fst<Arc> > &aiter = dfs_state->arc_iter; 132 if (!dfs || aiter.Done()) { 133 state_color[s] = kDfsBlack; 134 delete dfs_state; 135 state_stack.pop(); 136 if (!state_stack.empty()) { 137 DfsState<Arc> *parent_state = state_stack.top(); 138 StateId p = parent_state->state_id; 139 ArcIterator< Fst<Arc> > &piter = parent_state->arc_iter; 140 visitor->FinishState(s, p, &piter.Value()); 141 piter.Next(); 142 } else { 143 visitor->FinishState(s, kNoStateId, 0); 144 } 145 continue; 146 } 147 const Arc &arc = aiter.Value(); 148 if (arc.nextstate >= state_color.size()) { 149 nstates = arc.nextstate + 1; 150 state_color.resize(nstates, kDfsWhite); 151 } 152 if (!filter(arc)) { 153 aiter.Next(); 154 continue; 155 } 156 int next_color = state_color[arc.nextstate]; 157 switch (next_color) { 158 default: 159 case kDfsWhite: 160 dfs = visitor->TreeArc(s, arc); 161 if (!dfs) break; 162 state_color[arc.nextstate] = kDfsGrey; 163 state_stack.push(new DfsState<Arc>(fst, arc.nextstate)); 164 dfs = visitor->InitState(arc.nextstate, root); 165 break; 166 case kDfsGrey: 167 dfs = visitor->BackArc(s, arc); 168 aiter.Next(); 169 break; 170 case kDfsBlack: 171 dfs = visitor->ForwardOrCrossArc(s, arc); 172 aiter.Next(); 173 break; 174 } 175 } 176 177 // Find next tree root 178 for (root = root == start ? 0 : root + 1; 179 root < nstates && state_color[root] != kDfsWhite; 180 ++root) { 181 } 182 183 // Check for a state beyond the largest known state 184 if (!expanded && root == nstates) { 185 for (; !siter.Done(); siter.Next()) { 186 if (siter.Value() == nstates) { 187 ++nstates; 188 state_color.push_back(kDfsWhite); 189 break; 190 } 191 } 192 } 193 } 194 visitor->FinishVisit(); 195} 196 197 198template <class Arc, class V> 199void DfsVisit(const Fst<Arc> &fst, V *visitor) { 200 DfsVisit(fst, visitor, AnyArcFilter<Arc>()); 201} 202 203} // namespace fst 204 205#endif // FST_LIB_DFS_VISIT_H__ 206