diff options
author | Ted Yin <[email protected]> | 2015-08-14 17:42:26 +0800 |
---|---|---|
committer | Ted Yin <[email protected]> | 2015-08-14 17:42:26 +0800 |
commit | c3cffb58b9921d78753336421b52b9ffdaa5515c (patch) | |
tree | bfea20e97c200cf734021e3756d749c892e658a4 /kaldi_io/src/tools/openfst/include/fst/dfs-visit.h | |
parent | 10cce5f6a5c9e2f8e00d5a2a4d87c9cb7c26bf4c (diff) | |
parent | dfdd17afc2e984ec6c32ea01290f5c76309a456a (diff) |
Merge pull request #2 from yimmon/master
remove needless files
Diffstat (limited to 'kaldi_io/src/tools/openfst/include/fst/dfs-visit.h')
-rw-r--r-- | kaldi_io/src/tools/openfst/include/fst/dfs-visit.h | 205 |
1 files changed, 0 insertions, 205 deletions
diff --git a/kaldi_io/src/tools/openfst/include/fst/dfs-visit.h b/kaldi_io/src/tools/openfst/include/fst/dfs-visit.h deleted file mode 100644 index 4d93a39..0000000 --- a/kaldi_io/src/tools/openfst/include/fst/dfs-visit.h +++ /dev/null @@ -1,205 +0,0 @@ -// 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: [email protected] (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__ |