diff options
Diffstat (limited to 'kaldi_io/src/tools/openfst/include/fst/topsort.h')
-rw-r--r-- | kaldi_io/src/tools/openfst/include/fst/topsort.h | 112 |
1 files changed, 0 insertions, 112 deletions
diff --git a/kaldi_io/src/tools/openfst/include/fst/topsort.h b/kaldi_io/src/tools/openfst/include/fst/topsort.h deleted file mode 100644 index 53735e5..0000000 --- a/kaldi_io/src/tools/openfst/include/fst/topsort.h +++ /dev/null @@ -1,112 +0,0 @@ -// topsort.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 -// Topological sort of FSTs - -#ifndef FST_LIB_TOPSORT_H__ -#define FST_LIB_TOPSORT_H__ - -#include <algorithm> -#include <vector> -using std::vector; - - -#include <fst/dfs-visit.h> -#include <fst/fst.h> -#include <fst/statesort.h> - - -namespace fst { - -// DFS visitor class to return topological ordering. -template <class A> -class TopOrderVisitor { - public: - typedef A Arc; - typedef typename A::StateId StateId; - - // If acyclic, ORDER[i] gives the topological position of state Id i; - // otherwise unchanged. ACYCLIC will be true iff the FST has - // no cycles. - TopOrderVisitor(vector<StateId> *order, bool *acyclic) - : order_(order), acyclic_(acyclic) {} - - void InitVisit(const Fst<A> &fst) { - finish_ = new vector<StateId>; - *acyclic_ = true; - } - - bool InitState(StateId s, StateId r) { return true; } - - bool TreeArc(StateId s, const A &arc) { return true; } - - bool BackArc(StateId s, const A &arc) { return (*acyclic_ = false); } - - bool ForwardOrCrossArc(StateId s, const A &arc) { return true; } - - void FinishState(StateId s, StateId p, const A *) { finish_->push_back(s); } - - void FinishVisit() { - if (*acyclic_) { - order_->clear(); - for (StateId s = 0; s < finish_->size(); ++s) - order_->push_back(kNoStateId); - for (StateId s = 0; s < finish_->size(); ++s) - (*order_)[(*finish_)[finish_->size() - s - 1]] = s; - } - delete finish_; - } - - private: - vector<StateId> *order_; - bool *acyclic_; - vector<StateId> *finish_; // states in finishing-time order -}; - - -// Topologically sorts its input if acyclic, modifying it. Otherwise, -// the input is unchanged. When sorted, all transitions are from -// lower to higher state IDs. -// -// Complexity: -// - Time: O(V + E) -// - Space: O(V + E) -// where V = # of states and E = # of arcs. -template <class Arc> -bool TopSort(MutableFst<Arc> *fst) { - typedef typename Arc::StateId StateId; - - vector<StateId> order; - bool acyclic; - - TopOrderVisitor<Arc> top_order_visitor(&order, &acyclic); - DfsVisit(*fst, &top_order_visitor); - - if (acyclic) { - StateSort(fst, order); - fst->SetProperties(kAcyclic | kInitialAcyclic | kTopSorted, - kAcyclic | kInitialAcyclic | kTopSorted); - } else { - fst->SetProperties(kCyclic | kNotTopSorted, kCyclic | kNotTopSorted); - } - return acyclic; -} - -} // namespace fst - -#endif // FST_LIB_TOPSORT_H__ |