1 // arc.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 //
20 // Commonly used Fst arc types.
21 
22 #ifndef FST_LIB_ARC_H__
23 #define FST_LIB_ARC_H__
24 
25 #include <string>
26 
27 
28 #include <fst/expectation-weight.h>
29 #include <fst/float-weight.h>
30 #include <fst/lexicographic-weight.h>
31 #include <fst/power-weight.h>
32 #include <fst/product-weight.h>
33 #include <fst/signed-log-weight.h>
34 #include <fst/sparse-power-weight.h>
35 #include <iostream>
36 #include <fstream>
37 #include <sstream>
38 #include <fst/string-weight.h>
39 
40 
41 namespace fst {
42 
43 template <class W>
44 class ArcTpl {
45  public:
46   typedef W Weight;
47   typedef int Label;
48   typedef int StateId;
49 
ArcTpl(Label i,Label o,const Weight & w,StateId s)50   ArcTpl(Label i, Label o, const Weight& w, StateId s)
51       : ilabel(i), olabel(o), weight(w), nextstate(s) {}
52 
ArcTpl()53   ArcTpl() {}
54 
Type(void)55   static const string &Type(void) {
56     static const string type =
57         (Weight::Type() == "tropical") ? "standard" : Weight::Type();
58     return type;
59   }
60 
61   Label ilabel;
62   Label olabel;
63   Weight weight;
64   StateId nextstate;
65 };
66 
67 typedef ArcTpl<TropicalWeight> StdArc;
68 typedef ArcTpl<LogWeight> LogArc;
69 typedef ArcTpl<Log64Weight> Log64Arc;
70 typedef ArcTpl<SignedLogWeight> SignedLogArc;
71 typedef ArcTpl<SignedLog64Weight> SignedLog64Arc;
72 typedef ArcTpl<MinMaxWeight> MinMaxArc;
73 
74 
75 // Arc with integer labels and state Ids and string weights.
76 template <StringType S = STRING_LEFT>
77 class StringArc {
78  public:
79   typedef int Label;
80   typedef StringWeight<int, S> Weight;
81   typedef int StateId;
82 
StringArc(Label i,Label o,Weight w,StateId s)83   StringArc(Label i, Label o, Weight w, StateId s)
84       : ilabel(i), olabel(o), weight(w), nextstate(s) {}
85 
StringArc()86   StringArc() {}
87 
Type()88   static const string &Type() {  // Arc type name
89     static const string type =
90         S == STRING_LEFT ? "standard_string" :
91         (S == STRING_RIGHT ? "right_standard_string" :
92          (S == STRING_LEFT_RESTRICT ? "restricted_string" :
93           "right_restricted_string"));
94     return type;
95   }
96 
97   Label ilabel;       // Transition input label
98   Label olabel;       // Transition output label
99   Weight weight;      // Transition weight
100   StateId nextstate;  // Transition destination state
101 };
102 
103 
104 // Arc with label and state Id type the same as template arg and with
105 // weights over the Gallic semiring w.r.t the output labels and weights of A.
106 template <class A, StringType S = STRING_LEFT>
107 struct GallicArc {
108   typedef A Arc;
109   typedef typename A::Label Label;
110   typedef typename A::StateId StateId;
111   typedef GallicWeight<Label, typename A::Weight, S> Weight;
112 
GallicArcGallicArc113   GallicArc() {}
114 
GallicArcGallicArc115   GallicArc(Label i, Label o, Weight w, StateId s)
116       : ilabel(i), olabel(o), weight(w), nextstate(s) {}
117 
GallicArcGallicArc118   GallicArc(const A &arc)
119       : ilabel(arc.ilabel), olabel(arc.ilabel),
120         weight(arc.olabel, arc.weight), nextstate(arc.nextstate) {}
121 
TypeGallicArc122   static const string &Type() {  // Arc type name
123     static const string type =
124         (S == STRING_LEFT ? "gallic_" :
125          (S == STRING_RIGHT ? "right_gallic_" :
126           (S == STRING_LEFT_RESTRICT ? "restricted_gallic_" :
127            "right_restricted_gallic_"))) + A::Type();
128     return type;
129   }
130 
131   Label ilabel;       // Transition input label
132   Label olabel;       // Transition output label
133   Weight weight;      // Transition weight
134   StateId nextstate;  // Transition destination state
135 };
136 
137 
138 // Arc with the reverse of the weight found in its template arg.
139 template <class A> struct ReverseArc {
140   typedef A Arc;
141   typedef typename A::Label Label;
142   typedef typename A::Weight AWeight;
143   typedef typename AWeight::ReverseWeight Weight;
144   typedef typename A::StateId StateId;
145 
ReverseArcReverseArc146   ReverseArc(Label i, Label o, Weight w, StateId s)
147       : ilabel(i), olabel(o), weight(w), nextstate(s) {}
148 
ReverseArcReverseArc149   ReverseArc() {}
150 
TypeReverseArc151   static const string &Type() {  // Arc type name
152     static const string type = "reverse_" + Arc::Type();
153     return type;
154   }
155 
156   Label ilabel;       // Transition input label
157   Label olabel;       // Transition output label
158   Weight weight;      // Transition weight
159   StateId nextstate;  // Transition destination state
160 };
161 
162 
163 // Arc with integer labels and state Ids and lexicographic weights.
164 template<class W1, class W2>
165 struct LexicographicArc {
166   typedef int Label;
167   typedef LexicographicWeight<W1, W2> Weight;
168   typedef int StateId;
169 
LexicographicArcLexicographicArc170   LexicographicArc(Label i, Label o, Weight w, StateId s)
171       : ilabel(i), olabel(o), weight(w), nextstate(s) {}
172 
LexicographicArcLexicographicArc173   LexicographicArc() {}
174 
TypeLexicographicArc175   static const string &Type() {  // Arc type name
176     static const string type = Weight::Type();
177     return type;
178   }
179 
180   Label ilabel;       // Transition input label
181   Label olabel;       // Transition output label
182   Weight weight;      // Transition weight
183   StateId nextstate;  // Transition destination state
184 };
185 
186 
187 // Arc with integer labels and state Ids and product weights.
188 template<class W1, class W2>
189 struct ProductArc {
190   typedef int Label;
191   typedef ProductWeight<W1, W2> Weight;
192   typedef int StateId;
193 
ProductArcProductArc194   ProductArc(Label i, Label o, Weight w, StateId s)
195       : ilabel(i), olabel(o), weight(w), nextstate(s) {}
196 
ProductArcProductArc197   ProductArc() {}
198 
TypeProductArc199   static const string &Type() {  // Arc type name
200     static const string type = Weight::Type();
201     return type;
202   }
203 
204   Label ilabel;       // Transition input label
205   Label olabel;       // Transition output label
206   Weight weight;      // Transition weight
207   StateId nextstate;  // Transition destination state
208 };
209 
210 
211 // Arc with label and state Id type the same as first template arg and with
212 // weights over the n-th cartesian power of the weight type of the
213 // template arg.
214 template <class A, unsigned int n>
215 struct PowerArc {
216   typedef A Arc;
217   typedef typename A::Label Label;
218   typedef typename A::StateId StateId;
219   typedef PowerWeight<typename A::Weight, n> Weight;
220 
PowerArcPowerArc221   PowerArc() {}
222 
PowerArcPowerArc223   PowerArc(Label i, Label o, Weight w, StateId s)
224       : ilabel(i), olabel(o), weight(w), nextstate(s) {}
225 
TypePowerArc226   static const string &Type() {  // Arc type name
227     static string type;
228     if (type.empty()) {
229       string power;
230       Int64ToStr(n, &power);
231       type = A::Type() + "_^" + power;
232     }
233     return type;
234   }
235 
236   Label ilabel;       // Transition input label
237   Label olabel;       // Transition output label
238   Weight weight;      // Transition weight
239   StateId nextstate;  // Transition destination state
240 };
241 
242 
243 // Arc with label and state Id type the same as first template arg and with
244 // weights over the arbitrary cartesian power of the weight type.
245 template <class A, class K = int>
246 struct SparsePowerArc {
247   typedef A Arc;
248   typedef typename A::Label Label;
249   typedef typename A::StateId StateId;
250   typedef SparsePowerWeight<typename A::Weight, K> Weight;
251 
SparsePowerArcSparsePowerArc252   SparsePowerArc() {}
253 
SparsePowerArcSparsePowerArc254   SparsePowerArc(Label i, Label o, Weight w, StateId s)
255       : ilabel(i), olabel(o), weight(w), nextstate(s) {}
256 
TypeSparsePowerArc257   static const string &Type() {  // Arc type name
258     static string type;
259     if (type.empty()) { type = A::Type() + "_^n"; }
260     if(sizeof(K) != sizeof(uint32)) {
261       string size;
262       Int64ToStr(8 * sizeof(K), &size);
263       type += "_" + size;
264     }
265     return type;
266   }
267 
268   Label ilabel;       // Transition input label
269   Label olabel;       // Transition output label
270   Weight weight;      // Transition weight
271   StateId nextstate;  // Transition destination state
272 };
273 
274 
275 // Arc with label and state Id type the same as first template arg and with
276 // expectation weight over the first template arg weight type and the
277 // second template arg.
278 template <class A, class X2>
279 struct ExpectationArc {
280   typedef A Arc;
281   typedef typename A::Label Label;
282   typedef typename A::StateId StateId;
283   typedef typename A::Weight X1;
284   typedef ExpectationWeight<X1, X2> Weight;
285 
ExpectationArcExpectationArc286   ExpectationArc() {}
287 
ExpectationArcExpectationArc288   ExpectationArc(Label i, Label o, Weight w, StateId s)
289       : ilabel(i), olabel(o), weight(w), nextstate(s) {}
290 
TypeExpectationArc291   static const string &Type() {  // Arc type name
292     static string type;
293     if (type.empty()) {
294       type = "expectation_" + A::Type() + "_" + X2::Type();
295     }
296     return type;
297   }
298 
299   Label ilabel;       // Transition input label
300   Label olabel;       // Transition output label
301   Weight weight;      // Transition weight
302   StateId nextstate;  // Transition destination state
303 };
304 
305 }  // namespace fst
306 
307 #endif  // FST_LIB_ARC_H__
308