FST  openfst-1.7.2
OpenFst Library
statesort.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 // Function to sort states of an FST.
5 
6 #ifndef FST_STATESORT_H_
7 #define FST_STATESORT_H_
8 
9 #include <algorithm>
10 #include <vector>
11 
12 #include <fst/log.h>
13 
14 #include <fst/mutable-fst.h>
15 
16 
17 namespace fst {
18 
19 // Sorts the input states of an FST. order[i] gives the the state ID after
20 // sorting that corresponds to the state ID i before sorting; it must
21 // therefore be a permutation of the input FST's states ID sequence.
22 template <class Arc>
24  const std::vector<typename Arc::StateId> &order) {
25  using StateId = typename Arc::StateId;
26  using Weight = typename Arc::Weight;
27  if (order.size() != fst->NumStates()) {
28  FSTERROR() << "StateSort: Bad order vector size: " << order.size();
30  return;
31  }
32  if (fst->Start() == kNoStateId) return;
33  const auto props = fst->Properties(kStateSortProperties, false);
34  std::vector<bool> done(order.size(), false);
35  std::vector<Arc> arcsa;
36  std::vector<Arc> arcsb;
37  fst->SetStart(order[fst->Start()]);
38  for (StateIterator<MutableFst<Arc>> siter(*fst); !siter.Done();
39  siter.Next()) {
40  auto s1 = siter.Value();
41  StateId s2;
42  if (done[s1]) continue;
43  auto final1 = fst->Final(s1);
44  auto final2 = Weight::Zero();
45  arcsa.clear();
46  for (ArcIterator<MutableFst<Arc>> aiter(*fst, s1); !aiter.Done();
47  aiter.Next()) {
48  arcsa.push_back(aiter.Value());
49  }
50  for (; !done[s1]; s1 = s2, final1 = final2, std::swap(arcsa, arcsb)) {
51  s2 = order[s1];
52  if (!done[s2]) {
53  final2 = fst->Final(s2);
54  arcsb.clear();
55  for (ArcIterator<MutableFst<Arc>> aiter(*fst, s2); !aiter.Done();
56  aiter.Next()) {
57  arcsb.push_back(aiter.Value());
58  }
59  }
60  fst->SetFinal(s2, final1);
61  fst->DeleteArcs(s2);
62  for (auto arc : arcsa) { // Copy intended.
63  arc.nextstate = order[arc.nextstate];
64  fst->AddArc(s2, arc);
65  }
66  done[s1] = true;
67  }
68  }
69  fst->SetProperties(props, kFstProperties);
70 }
71 
72 } // namespace fst
73 
74 #endif // FST_STATESORT_H_
virtual void AddArc(StateId, const Arc &arc)=0
void StateSort(MutableFst< Arc > *fst, const std::vector< typename Arc::StateId > &order)
Definition: statesort.h:23
virtual Weight Final(StateId) const =0
virtual void SetStart(StateId)=0
constexpr uint64 kFstProperties
Definition: properties.h:301
constexpr int kNoStateId
Definition: fst.h:180
virtual uint64 Properties(uint64 mask, bool test) const =0
#define FSTERROR()
Definition: util.h:35
virtual void SetFinal(StateId, Weight)=0
constexpr uint64 kStateSortProperties
Definition: properties.h:216
virtual StateId Start() const =0
virtual void DeleteArcs(StateId, size_t n)=0
constexpr uint64 kError
Definition: properties.h:33
virtual StateId NumStates() const =0
virtual void SetProperties(uint64 props, uint64 mask)=0