1 // reverse.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 // Copyright 2005-2010 Google, Inc.
16 // Author: riley@google.com (Michael Riley)
17 //
18 // \file
19 // Functions and classes to sort arcs in an FST.
20 
21 #ifndef FST_LIB_REVERSE_H__
22 #define FST_LIB_REVERSE_H__
23 
24 #include <algorithm>
25 #include <vector>
26 using std::vector;
27 
28 #include <fst/cache.h>
29 
30 
31 namespace fst {
32 
33 // Reverses an FST. The reversed result is written to an output
34 // MutableFst.  If A transduces string x to y with weight a, then the
35 // reverse of A transduces the reverse of x to the reverse of y with
36 // weight a.Reverse().
37 //
38 // Typically, a = a.Reverse() and Arc = RevArc (e.g. for
39 // TropicalWeight or LogWeight).  In general, e.g. when the weights
40 // only form a left or right semiring, the output arc type must match
41 // the input arc type except having the reversed Weight type.
42 //
43 // When 'require_superinitial == false', a superinitial state is
44 // *not* created in the reversed Fst iff the input Fst has exactly
45 // 1 final state (which becomes the initial state of the reversed Fst)
46 // that has a final weight of Weight::One() *or* does not belong to
47 // any cycle.
48 // When 'require_superinitial == true', a superinitial state is
49 // always created.
50 template<class Arc, class RevArc>
51 void Reverse(const Fst<Arc> &ifst, MutableFst<RevArc> *ofst,
52              bool require_superinitial = true) {
53   typedef typename Arc::StateId StateId;
54   typedef typename Arc::Weight Weight;
55   typedef typename RevArc::Weight RevWeight;
56 
57   ofst->DeleteStates();
58   ofst->SetInputSymbols(ifst.InputSymbols());
59   ofst->SetOutputSymbols(ifst.OutputSymbols());
60   if (ifst.Properties(kExpanded, false))
61     ofst->ReserveStates(CountStates(ifst) + 1);
62   StateId istart = ifst.Start();
63   StateId ostart = kNoStateId;
64   StateId offset = 0;
65   uint64 dfs_iprops = 0, dfs_oprops = 0;
66 
67   if (!require_superinitial) {
68     for (StateIterator<Fst<Arc> > siter(ifst);
69          !siter.Done();
70          siter.Next()) {
71       StateId is = siter.Value();
72       if (ifst.Final(is) == Weight::Zero()) continue;
73       if (ostart != kNoStateId) {
74         ostart = kNoStateId;
75         break;
76       } else {
77         ostart = is;
78       }
79     }
80 
81     if (ostart != kNoStateId && ifst.Final(ostart) != Weight::One()) {
82       vector<StateId> scc;
83       SccVisitor<Arc> scc_visitor(&scc, 0, 0, &dfs_iprops);
84       DfsVisit(ifst, &scc_visitor);
85       if (count(scc.begin(), scc.end(), scc[ostart]) > 1) {
86         ostart = kNoStateId;
87       } else {
88         for (ArcIterator<Fst<Arc> > aiter(ifst, ostart);
89              !aiter.Done(); aiter.Next()) {
90           if (aiter.Value().nextstate == ostart) {
91             ostart = kNoStateId;
92             break;
93           }
94         }
95       }
96       if (ostart != kNoStateId)
97         dfs_oprops = kInitialAcyclic;
98     }
99   }
100 
101   if (ostart == kNoStateId) {  // Super-initial requested or needed.
102     ostart = ofst->AddState();
103     offset = 1;
104   }
105 
106   for (StateIterator<Fst<Arc> > siter(ifst);
107        !siter.Done();
108        siter.Next()) {
109     StateId is = siter.Value();
110     StateId os = is + offset;
111     while (ofst->NumStates() <= os)
112       ofst->AddState();
113     if (is == istart)
114       ofst->SetFinal(os, RevWeight::One());
115 
116     Weight final = ifst.Final(is);
117     if ((final != Weight::Zero()) && (offset == 1)) {
118       RevArc oarc(0, 0, final.Reverse(), os);
119       ofst->AddArc(0, oarc);
120     }
121 
122     for (ArcIterator<Fst<Arc> > aiter(ifst, is);
123          !aiter.Done();
124          aiter.Next()) {
125       const Arc &iarc = aiter.Value();
126       StateId nos = iarc.nextstate + offset;
127       typename RevArc::Weight weight = iarc.weight.Reverse();
128       if (!offset && (nos == ostart))
129         weight = Times(ifst.Final(ostart).Reverse(), weight);
130       RevArc oarc(iarc.ilabel, iarc.olabel, weight, os);
131       while (ofst->NumStates() <= nos)
132         ofst->AddState();
133       ofst->AddArc(nos, oarc);
134     }
135   }
136   ofst->SetStart(ostart);
137   if (offset == 0 && ostart == istart)
138     ofst->SetFinal(ostart, ifst.Final(ostart).Reverse());
139 
140   uint64 iprops = ifst.Properties(kCopyProperties, false) | dfs_iprops;
141   uint64 oprops = ofst->Properties(kFstProperties, false) | dfs_oprops;
142   ofst->SetProperties(ReverseProperties(iprops, offset == 1) | oprops,
143                       kFstProperties);
144 }
145 
146 }  // namespace fst
147 
148 #endif  // FST_LIB_REVERSE_H__
149