14a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// topsort.h 24a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 34a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Licensed under the Apache License, Version 2.0 (the "License"); 44a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// you may not use this file except in compliance with the License. 54a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// You may obtain a copy of the License at 64a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 74a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// http://www.apache.org/licenses/LICENSE-2.0 84a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 94a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Unless required by applicable law or agreed to in writing, software 104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// distributed under the License is distributed on an "AS IS" BASIS, 114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// See the License for the specific language governing permissions and 134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// limitations under the License. 144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// \file 174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Topological sort of FSTs 184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#ifndef FST_LIB_TOPSORT_H__ 204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#define FST_LIB_TOPSORT_H__ 214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include <algorithm> 234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include <vector> 244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/dfs-visit.h" 264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/fst.h" 274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/statesort.h" 284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectnamespace fst { 304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// DFS visitor class to return topological ordering. 324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass TopOrderVisitor { 344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef A Arc; 364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // If acyclic, ORDER[i] gives the topological position of state Id i; 394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // otherwise unchanged. ACYCLIC will be true iff the FST has 404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // no cycles. 414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project TopOrderVisitor(vector<StateId> *order, bool *acyclic) 424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : order_(order), acyclic_(acyclic) {} 434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void InitVisit(const Fst<A> &fst) { 454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project finish_ = new vector<StateId>; 464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *acyclic_ = true; 474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool InitState(StateId s, StateId r) { return true; } 504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool TreeArc(StateId s, const A &arc) { return true; } 524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool BackArc(StateId s, const A &arc) { return (*acyclic_ = false); } 544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool ForwardOrCrossArc(StateId s, const A &arc) { return true; } 564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void FinishState(StateId s, StateId p, const A *) { finish_->push_back(s); } 584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void FinishVisit() { 604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (*acyclic_) { 614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project order_->clear(); 624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (StateId s = 0; s < (StateId)finish_->size(); ++s) 634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project order_->push_back(kNoStateId); 644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (StateId s = 0; s < (StateId)finish_->size(); ++s) 654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (*order_)[(*finish_)[finish_->size() - s - 1]] = s; 664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete finish_; 684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<StateId> *order_; 724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool *acyclic_; 734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<StateId> *finish_; // states in finishing-time order 744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Topologically sorts its input if acyclic, modifying it. Otherwise, 784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// the input is unchanged. When sorted, all transitions are from 794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// lower to higher state IDs. 804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Complexity: 824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Time: O(V + E) 834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Space: O(V + E) 844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// where V = # of states and E = # of arcs. 854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class Arc> 864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectbool TopSort(MutableFst<Arc> *fst) { 874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::StateId StateId; 884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<StateId> order; 904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool acyclic; 914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project TopOrderVisitor<Arc> top_order_visitor(&order, &acyclic); 934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DfsVisit(*fst, &top_order_visitor); 944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (acyclic) { 964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateSort(fst, order); 974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst->SetProperties(kAcyclic | kInitialAcyclic | kTopSorted, 984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project kAcyclic | kInitialAcyclic | kTopSorted); 994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 1004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst->SetProperties(kCyclic | kNotTopSorted, kCyclic | kNotTopSorted); 1014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return acyclic; 1034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 1044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} // namespace fst 1064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif // FST_LIB_TOPSORT_H__ 108