1 // topsort.h 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 // 15 // 16 // \file 17 // Topological sort of FSTs 18 19 #ifndef FST_LIB_TOPSORT_H__ 20 #define FST_LIB_TOPSORT_H__ 21 22 #include <algorithm> 23 #include <vector> 24 25 #include "fst/lib/dfs-visit.h" 26 #include "fst/lib/fst.h" 27 #include "fst/lib/statesort.h" 28 29 namespace fst { 30 31 // DFS visitor class to return topological ordering. 32 template <class A> 33 class TopOrderVisitor { 34 public: 35 typedef A Arc; 36 typedef typename A::StateId StateId; 37 38 // If acyclic, ORDER[i] gives the topological position of state Id i; 39 // otherwise unchanged. ACYCLIC will be true iff the FST has 40 // no cycles. 41 TopOrderVisitor(vector<StateId> *order, bool *acyclic) 42 : order_(order), acyclic_(acyclic) {} 43 44 void InitVisit(const Fst<A> &fst) { 45 finish_ = new vector<StateId>; 46 *acyclic_ = true; 47 } 48 49 bool InitState(StateId s, StateId r) { return true; } 50 51 bool TreeArc(StateId s, const A &arc) { return true; } 52 53 bool BackArc(StateId s, const A &arc) { return (*acyclic_ = false); } 54 55 bool ForwardOrCrossArc(StateId s, const A &arc) { return true; } 56 57 void FinishState(StateId s, StateId p, const A *) { finish_->push_back(s); } 58 59 void FinishVisit() { 60 if (*acyclic_) { 61 order_->clear(); 62 for (StateId s = 0; s < (StateId)finish_->size(); ++s) 63 order_->push_back(kNoStateId); 64 for (StateId s = 0; s < (StateId)finish_->size(); ++s) 65 (*order_)[(*finish_)[finish_->size() - s - 1]] = s; 66 } 67 delete finish_; 68 } 69 70 private: 71 vector<StateId> *order_; 72 bool *acyclic_; 73 vector<StateId> *finish_; // states in finishing-time order 74 }; 75 76 77 // Topologically sorts its input if acyclic, modifying it. Otherwise, 78 // the input is unchanged. When sorted, all transitions are from 79 // lower to higher state IDs. 80 // 81 // Complexity: 82 // - Time: O(V + E) 83 // - Space: O(V + E) 84 // where V = # of states and E = # of arcs. 85 template <class Arc> 86 bool TopSort(MutableFst<Arc> *fst) { 87 typedef typename Arc::StateId StateId; 88 89 vector<StateId> order; 90 bool acyclic; 91 92 TopOrderVisitor<Arc> top_order_visitor(&order, &acyclic); 93 DfsVisit(*fst, &top_order_visitor); 94 95 if (acyclic) { 96 StateSort(fst, order); 97 fst->SetProperties(kAcyclic | kInitialAcyclic | kTopSorted, 98 kAcyclic | kInitialAcyclic | kTopSorted); 99 } else { 100 fst->SetProperties(kCyclic | kNotTopSorted, kCyclic | kNotTopSorted); 101 } 102 return acyclic; 103 } 104 105 } // namespace fst 106 107 #endif // FST_LIB_TOPSORT_H__ 108