/usr/include/fst/reverse.h is in libfst-dev 1.5.3+r3-2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 | // See www.openfst.org for extensive documentation on this weighted
// finite-state transducer library.
//
// Functions and classes to sort arcs in an FST.
#ifndef FST_LIB_REVERSE_H_
#define FST_LIB_REVERSE_H_
#include <algorithm>
#include <vector>
#include <fst/cache.h>
namespace fst {
// Reverses an FST. The reversed result is written to an output
// MutableFst. If A transduces string x to y with weight a, then the
// reverse of A transduces the reverse of x to the reverse of y with
// weight a.Reverse().
//
// Typically, a = a.Reverse() and Arc = RevArc (e.g. for
// TropicalWeight or LogWeight). In general, e.g. when the weights
// only form a left or right semiring, the output arc type must match
// the input arc type except having the reversed Weight type.
//
// When 'require_superinitial == false', a superinitial state is
// *not* created in the reversed Fst iff the input Fst has exactly
// 1 final state (which becomes the initial state of the reversed Fst)
// that has a final weight of Weight::One() *or* does not belong to
// any cycle.
// When 'require_superinitial == true', a superinitial state is
// always created.
template <class Arc, class RevArc>
void Reverse(const Fst<Arc> &ifst, MutableFst<RevArc> *ofst,
bool require_superinitial = true) {
typedef typename Arc::StateId StateId;
typedef typename Arc::Weight Weight;
typedef typename RevArc::Weight RevWeight;
ofst->DeleteStates();
ofst->SetInputSymbols(ifst.InputSymbols());
ofst->SetOutputSymbols(ifst.OutputSymbols());
if (ifst.Properties(kExpanded, false))
ofst->ReserveStates(CountStates(ifst) + 1);
StateId istart = ifst.Start();
StateId ostart = kNoStateId;
StateId offset = 0;
uint64 dfs_iprops = 0, dfs_oprops = 0;
if (!require_superinitial) {
for (StateIterator<Fst<Arc>> siter(ifst); !siter.Done(); siter.Next()) {
StateId is = siter.Value();
if (ifst.Final(is) == Weight::Zero()) continue;
if (ostart != kNoStateId) {
ostart = kNoStateId;
break;
} else {
ostart = is;
}
}
if (ostart != kNoStateId && ifst.Final(ostart) != Weight::One()) {
std::vector<StateId> scc;
SccVisitor<Arc> scc_visitor(&scc, 0, 0, &dfs_iprops);
DfsVisit(ifst, &scc_visitor);
if (count(scc.begin(), scc.end(), scc[ostart]) > 1) {
ostart = kNoStateId;
} else {
for (ArcIterator<Fst<Arc>> aiter(ifst, ostart); !aiter.Done();
aiter.Next()) {
if (aiter.Value().nextstate == ostart) {
ostart = kNoStateId;
break;
}
}
}
if (ostart != kNoStateId) dfs_oprops = kInitialAcyclic;
}
}
if (ostart == kNoStateId) { // Super-initial requested or needed.
ostart = ofst->AddState();
offset = 1;
}
for (StateIterator<Fst<Arc>> siter(ifst); !siter.Done(); siter.Next()) {
StateId is = siter.Value();
StateId os = is + offset;
while (ofst->NumStates() <= os) ofst->AddState();
if (is == istart) ofst->SetFinal(os, RevWeight::One());
Weight final = ifst.Final(is);
if ((final != Weight::Zero()) && (offset == 1)) {
RevArc oarc(0, 0, final.Reverse(), os);
ofst->AddArc(0, oarc);
}
for (ArcIterator<Fst<Arc>> aiter(ifst, is); !aiter.Done(); aiter.Next()) {
const Arc &iarc = aiter.Value();
StateId nos = iarc.nextstate + offset;
typename RevArc::Weight weight = iarc.weight.Reverse();
if (!offset && (nos == ostart))
weight = Times(ifst.Final(ostart).Reverse(), weight);
RevArc oarc(iarc.ilabel, iarc.olabel, weight, os);
while (ofst->NumStates() <= nos) ofst->AddState();
ofst->AddArc(nos, oarc);
}
}
ofst->SetStart(ostart);
if (offset == 0 && ostart == istart)
ofst->SetFinal(ostart, ifst.Final(ostart).Reverse());
uint64 iprops = ifst.Properties(kCopyProperties, false) | dfs_iprops;
uint64 oprops = ofst->Properties(kFstProperties, false) | dfs_oprops;
ofst->SetProperties(ReverseProperties(iprops, offset == 1) | oprops,
kFstProperties);
}
} // namespace fst
#endif // FST_LIB_REVERSE_H_
|