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.
TopOrderVisitor(vector<StateId> * order,bool * acyclic)41 TopOrderVisitor(vector<StateId> *order, bool *acyclic)
42 : order_(order), acyclic_(acyclic) {}
43
InitVisit(const Fst<A> & fst)44 void InitVisit(const Fst<A> &fst) {
45 finish_ = new vector<StateId>;
46 *acyclic_ = true;
47 }
48
InitState(StateId s,StateId r)49 bool InitState(StateId s, StateId r) { return true; }
50
TreeArc(StateId s,const A & arc)51 bool TreeArc(StateId s, const A &arc) { return true; }
52
BackArc(StateId s,const A & arc)53 bool BackArc(StateId s, const A &arc) { return (*acyclic_ = false); }
54
ForwardOrCrossArc(StateId s,const A & arc)55 bool ForwardOrCrossArc(StateId s, const A &arc) { return true; }
56
FinishState(StateId s,StateId p,const A *)57 void FinishState(StateId s, StateId p, const A *) { finish_->push_back(s); }
58
FinishVisit()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>
TopSort(MutableFst<Arc> * fst)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