summaryrefslogtreecommitdiff
path: root/kaldi_io/src/tools/openfst/include/fst/dfs-visit.h
diff options
context:
space:
mode:
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.h205
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: 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__
Powered by cgit, Themed by Ted Yin.