diff options
author | Determinant <[email protected]> | 2015-08-14 11:51:42 +0800 |
---|---|---|
committer | Determinant <[email protected]> | 2015-08-14 11:51:42 +0800 |
commit | 96a32415ab43377cf1575bd3f4f2980f58028209 (patch) | |
tree | 30a2d92d73e8f40ac87b79f6f56e227bfc4eea6e /kaldi_io/src/tools/openfst/include/fst/topsort.h | |
parent | c177a7549bd90670af4b29fa813ddea32cfe0f78 (diff) |
add implementation for kaldi io (by ymz)
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, 112 insertions, 0 deletions
diff --git a/kaldi_io/src/tools/openfst/include/fst/topsort.h b/kaldi_io/src/tools/openfst/include/fst/topsort.h new file mode 100644 index 0000000..53735e5 --- /dev/null +++ b/kaldi_io/src/tools/openfst/include/fst/topsort.h @@ -0,0 +1,112 @@ +// 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__ |