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