FST  openfst-1.8.2
OpenFst Library
topsort.h
Go to the documentation of this file.
1 // Copyright 2005-2020 Google LLC
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 // See www.openfst.org for extensive documentation on this weighted
16 // finite-state transducer library.
17 //
18 // Topological sort of FSTs.
19 
20 #ifndef FST_TOPSORT_H_
21 #define FST_TOPSORT_H_
22 
23 #include <vector>
24 
25 
26 #include <fst/dfs-visit.h>
27 #include <fst/fst.h>
28 #include <fst/statesort.h>
29 
30 
31 namespace fst {
32 
33 // DFS visitor class to return topological ordering.
34 template <class Arc>
36  public:
37  using StateId = typename Arc::StateId;
38 
39  // If acyclic, order[i] gives the topological position of StateId i;
40  // otherwise it is unchanged. acyclic_ will be true iff the FST has no
41  // cycles. The caller retains ownership of the state order vector.
42  TopOrderVisitor(std::vector<StateId> *order, bool *acyclic)
43  : order_(order), acyclic_(acyclic) {}
44 
45  void InitVisit(const Fst<Arc> &fst) {
46  finish_.clear();
47  *acyclic_ = true;
48  }
49 
50  constexpr bool InitState(StateId, StateId) const { return true; }
51 
52  constexpr bool TreeArc(StateId, const Arc &) const { return true; }
53 
54  bool BackArc(StateId, const Arc &) { return (*acyclic_ = false); }
55 
56  constexpr bool ForwardOrCrossArc(StateId, const Arc &) const { return true; }
57 
58  void FinishState(StateId s, StateId, const Arc *) { finish_.push_back(s); }
59 
60  void FinishVisit() {
61  if (*acyclic_) {
62  order_->clear();
63  for (StateId s = 0; s < finish_.size(); ++s) {
64  order_->push_back(kNoStateId);
65  }
66  for (StateId s = 0; s < finish_.size(); ++s) {
67  (*order_)[finish_[finish_.size() - s - 1]] = s;
68  }
69  }
70  }
71 
72  private:
73  std::vector<StateId> *order_;
74  bool *acyclic_;
75  // States in finish-time order.
76  std::vector<StateId> finish_;
77 };
78 
79 // Topologically sorts its input if acyclic, modifying it. Otherwise, the input
80 // is unchanged. When sorted, all transitions are from lower to higher state
81 // IDs.
82 //
83 // Complexity:
84 //
85 // Time: O(V + E)
86 // Space: O(V + E)
87 //
88 // where V is the number of states and E is the number of arcs.
89 template <class Arc>
91  std::vector<typename Arc::StateId> order;
92  bool acyclic;
93  TopOrderVisitor<Arc> top_order_visitor(&order, &acyclic);
94  DfsVisit(*fst, &top_order_visitor);
95  if (acyclic) {
96  StateSort(fst, order);
99  } else {
101  }
102  return acyclic;
103 }
104 
105 } // namespace fst
106 
107 #endif // FST_TOPSORT_H_
constexpr uint64_t kCyclic
Definition: properties.h:108
void FinishVisit()
Definition: topsort.h:60
constexpr uint64_t kNotTopSorted
Definition: properties.h:120
void DfsVisit(const FST &fst, Visitor *visitor, ArcFilter filter, bool access_only=false)
Definition: dfs-visit.h:109
constexpr uint64_t kInitialAcyclic
Definition: properties.h:115
bool TopSort(MutableFst< Arc > *fst)
Definition: topsort.h:90
constexpr uint64_t kTopSorted
Definition: properties.h:118
constexpr int kNoStateId
Definition: fst.h:202
bool BackArc(StateId, const Arc &)
Definition: topsort.h:54
constexpr bool TreeArc(StateId, const Arc &) const
Definition: topsort.h:52
constexpr uint64_t kAcyclic
Definition: properties.h:110
virtual void SetProperties(uint64_t props, uint64_t mask)=0
constexpr bool ForwardOrCrossArc(StateId, const Arc &) const
Definition: topsort.h:56
constexpr bool InitState(StateId, StateId) const
Definition: topsort.h:50
TopOrderVisitor(std::vector< StateId > *order, bool *acyclic)
Definition: topsort.h:42
void InitVisit(const Fst< Arc > &fst)
Definition: topsort.h:45
void FinishState(StateId s, StateId, const Arc *)
Definition: topsort.h:58
bool StateSort(std::vector< IntervalSet< Label >> *interval_sets, const std::vector< StateId > &order)
typename Arc::StateId StateId
Definition: topsort.h:37