1// algo_test.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// Regression test for various FST algorithms.
20
21#ifndef FST_TEST_ALGO_TEST_H__
22#define FST_TEST_ALGO_TEST_H__
23
24#include <fst/fstlib.h>
25#include <fst/random-weight.h>
26
27DECLARE_int32(repeat);  // defined in ./algo_test.cc
28
29namespace fst {
30
31// Mapper to change input and output label of every transition into
32// epsilons.
33template <class A>
34class EpsMapper {
35 public:
36  EpsMapper() {}
37
38  A operator()(const A &arc) const {
39    return A(0, 0, arc.weight, arc.nextstate);
40  }
41
42  uint64 Properties(uint64 props) const {
43    props &= ~kNotAcceptor;
44    props |= kAcceptor;
45    props &= ~kNoIEpsilons & ~kNoOEpsilons &  ~kNoEpsilons;
46    props |= kIEpsilons | kOEpsilons | kEpsilons;
47    props &= ~kNotILabelSorted & ~kNotOLabelSorted;
48    props |= kILabelSorted | kOLabelSorted;
49    return props;
50  }
51
52  MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }
53
54
55  MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS;}
56
57  MapSymbolsAction OutputSymbolsAction() const { return MAP_COPY_SYMBOLS;}
58};
59
60// This class tests a variety of identities and properties that must
61// hold for various algorithms on weighted FSTs.
62template <class Arc, class WeightGenerator>
63class WeightedTester {
64 public:
65  typedef typename Arc::Label Label;
66  typedef typename Arc::StateId StateId;
67  typedef typename Arc::Weight Weight;
68
69  WeightedTester(int seed, const Fst<Arc> &zero_fst, const Fst<Arc> &one_fst,
70                 const Fst<Arc> &univ_fst, WeightGenerator *weight_generator)
71      : seed_(seed), zero_fst_(zero_fst), one_fst_(one_fst),
72        univ_fst_(univ_fst), weight_generator_(weight_generator) {}
73
74  void Test(const Fst<Arc> &T1, const Fst<Arc> &T2, const Fst<Arc> &T3) {
75    TestRational(T1, T2, T3);
76    TestMap(T1);
77    TestCompose(T1, T2, T3);
78    TestSort(T1);
79    TestOptimize(T1);
80    TestSearch(T1);
81  }
82
83 private:
84  // Tests rational operations with identities
85  void TestRational(const Fst<Arc> &T1, const Fst<Arc> &T2,
86                    const Fst<Arc> &T3) {
87
88    {
89      VLOG(1) << "Check destructive and delayed union are equivalent.";
90      VectorFst<Arc> U1(T1);
91      Union(&U1,  T2);
92      UnionFst<Arc> U2(T1, T2);
93      CHECK(Equiv(U1, U2));
94    }
95
96
97    {
98      VLOG(1) << "Check destructive and delayed concatenation are equivalent.";
99      VectorFst<Arc> C1(T1);
100      Concat(&C1,  T2);
101      ConcatFst<Arc> C2(T1, T2);
102      CHECK(Equiv(C1, C2));
103      VectorFst<Arc> C3(T2);
104      Concat(T1, &C3);
105      CHECK(Equiv(C3, C2));
106    }
107
108    {
109      VLOG(1) << "Check destructive and delayed closure* are equivalent.";
110      VectorFst<Arc> C1(T1);
111      Closure(&C1, CLOSURE_STAR);
112      ClosureFst<Arc> C2(T1, CLOSURE_STAR);
113      CHECK(Equiv(C1, C2));
114    }
115
116    {
117      VLOG(1) << "Check destructive and delayed closure+ are equivalent.";
118      VectorFst<Arc> C1(T1);
119      Closure(&C1, CLOSURE_PLUS);
120      ClosureFst<Arc> C2(T1, CLOSURE_PLUS);
121      CHECK(Equiv(C1, C2));
122    }
123
124    {
125      VLOG(1)  << "Check union is associative (destructive).";
126      VectorFst<Arc> U1(T1);
127      Union(&U1, T2);
128      Union(&U1, T3);
129
130      VectorFst<Arc> U3(T2);
131      Union(&U3, T3);
132      VectorFst<Arc> U4(T1);
133      Union(&U4, U3);
134
135      CHECK(Equiv(U1, U4));
136    }
137
138    {
139      VLOG(1) << "Check union is associative (delayed).";
140      UnionFst<Arc> U1(T1, T2);
141      UnionFst<Arc> U2(U1, T3);
142
143      UnionFst<Arc> U3(T2, T3);
144      UnionFst<Arc> U4(T1, U3);
145
146      CHECK(Equiv(U2, U4));
147    }
148
149
150    {
151      VLOG(1) << "Check union is associative (destructive delayed).";
152      UnionFst<Arc> U1(T1, T2);
153      Union(&U1, T3);
154
155      UnionFst<Arc> U3(T2, T3);
156      UnionFst<Arc> U4(T1, U3);
157
158      CHECK(Equiv(U1, U4));
159    }
160
161    {
162      VLOG(1) << "Check concatenation is associative (destructive).";
163      VectorFst<Arc> C1(T1);
164      Concat(&C1, T2);
165      Concat(&C1, T3);
166
167      VectorFst<Arc> C3(T2);
168      Concat(&C3, T3);
169      VectorFst<Arc> C4(T1);
170      Concat(&C4, C3);
171
172      CHECK(Equiv(C1, C4));
173    }
174
175    {
176      VLOG(1) << "Check concatenation is associative (delayed).";
177      ConcatFst<Arc> C1(T1, T2);
178      ConcatFst<Arc> C2(C1, T3);
179
180      ConcatFst<Arc> C3(T2, T3);
181      ConcatFst<Arc> C4(T1, C3);
182
183      CHECK(Equiv(C2, C4));
184    }
185
186    {
187      VLOG(1) << "Check concatenation is associative (destructive delayed).";
188      ConcatFst<Arc> C1(T1, T2);
189      Concat(&C1, T3);
190
191      ConcatFst<Arc> C3(T2, T3);
192      ConcatFst<Arc> C4(T1, C3);
193
194      CHECK(Equiv(C1, C4));
195    }
196
197    if (Weight::Properties() & kLeftSemiring) {
198      VLOG(1) << "Check concatenation left distributes"
199              << " over union (destructive).";
200
201      VectorFst<Arc> U1(T1);
202      Union(&U1, T2);
203      VectorFst<Arc> C1(T3);
204      Concat(&C1, U1);
205
206      VectorFst<Arc> C2(T3);
207      Concat(&C2, T1);
208      VectorFst<Arc> C3(T3);
209      Concat(&C3, T2);
210      VectorFst<Arc> U2(C2);
211      Union(&U2, C3);
212
213      CHECK(Equiv(C1, U2));
214    }
215
216    if (Weight::Properties() & kRightSemiring) {
217      VLOG(1) << "Check concatenation right distributes"
218              <<  " over union (destructive).";
219      VectorFst<Arc> U1(T1);
220      Union(&U1, T2);
221      VectorFst<Arc> C1(U1);
222      Concat(&C1, T3);
223
224      VectorFst<Arc> C2(T1);
225      Concat(&C2, T3);
226      VectorFst<Arc> C3(T2);
227      Concat(&C3, T3);
228      VectorFst<Arc> U2(C2);
229      Union(&U2, C3);
230
231      CHECK(Equiv(C1, U2));
232    }
233
234    if (Weight::Properties() & kLeftSemiring) {
235      VLOG(1) << "Check concatenation left distributes over union (delayed).";
236      UnionFst<Arc> U1(T1, T2);
237      ConcatFst<Arc> C1(T3, U1);
238
239      ConcatFst<Arc> C2(T3, T1);
240      ConcatFst<Arc> C3(T3, T2);
241      UnionFst<Arc> U2(C2, C3);
242
243      CHECK(Equiv(C1, U2));
244    }
245
246    if (Weight::Properties() & kRightSemiring) {
247      VLOG(1) << "Check concatenation right distributes over union (delayed).";
248      UnionFst<Arc> U1(T1, T2);
249      ConcatFst<Arc> C1(U1, T3);
250
251      ConcatFst<Arc> C2(T1, T3);
252      ConcatFst<Arc> C3(T2, T3);
253      UnionFst<Arc> U2(C2, C3);
254
255      CHECK(Equiv(C1, U2));
256    }
257
258
259    if (Weight::Properties() & kLeftSemiring) {
260      VLOG(1) << "Check T T* == T+ (destructive).";
261      VectorFst<Arc> S(T1);
262      Closure(&S, CLOSURE_STAR);
263      VectorFst<Arc> C(T1);
264      Concat(&C, S);
265
266      VectorFst<Arc> P(T1);
267      Closure(&P, CLOSURE_PLUS);
268
269      CHECK(Equiv(C, P));
270    }
271
272
273    if (Weight::Properties() & kRightSemiring) {
274      VLOG(1) << "Check T* T == T+ (destructive).";
275      VectorFst<Arc> S(T1);
276      Closure(&S, CLOSURE_STAR);
277      VectorFst<Arc> C(S);
278      Concat(&C, T1);
279
280      VectorFst<Arc> P(T1);
281      Closure(&P, CLOSURE_PLUS);
282
283      CHECK(Equiv(C, P));
284   }
285
286    if (Weight::Properties() & kLeftSemiring) {
287      VLOG(1) << "Check T T* == T+ (delayed).";
288      ClosureFst<Arc> S(T1, CLOSURE_STAR);
289      ConcatFst<Arc> C(T1, S);
290
291      ClosureFst<Arc> P(T1, CLOSURE_PLUS);
292
293      CHECK(Equiv(C, P));
294    }
295
296    if (Weight::Properties() & kRightSemiring) {
297      VLOG(1) << "Check T* T == T+ (delayed).";
298      ClosureFst<Arc> S(T1, CLOSURE_STAR);
299      ConcatFst<Arc> C(S, T1);
300
301      ClosureFst<Arc> P(T1, CLOSURE_PLUS);
302
303      CHECK(Equiv(C, P));
304    }
305  }
306
307  // Tests map-based operations.
308  void TestMap(const Fst<Arc> &T) {
309
310    {
311      VLOG(1) << "Check destructive and delayed projection are equivalent.";
312      VectorFst<Arc> P1(T);
313      Project(&P1, PROJECT_INPUT);
314      ProjectFst<Arc> P2(T, PROJECT_INPUT);
315      CHECK(Equiv(P1, P2));
316    }
317
318
319    {
320      VLOG(1) << "Check destructive and delayed inversion are equivalent.";
321      VectorFst<Arc> I1(T);
322      Invert(&I1);
323      InvertFst<Arc> I2(T);
324      CHECK(Equiv(I1, I2));
325    }
326
327    {
328      VLOG(1) << "Check Pi_1(T) = Pi_2(T^-1) (destructive).";
329      VectorFst<Arc> P1(T);
330      VectorFst<Arc> I1(T);
331      Project(&P1, PROJECT_INPUT);
332      Invert(&I1);
333      Project(&I1, PROJECT_OUTPUT);
334      CHECK(Equiv(P1, I1));
335    }
336
337    {
338      VLOG(1) << "Check Pi_2(T) = Pi_1(T^-1) (destructive).";
339      VectorFst<Arc> P1(T);
340      VectorFst<Arc> I1(T);
341      Project(&P1, PROJECT_OUTPUT);
342      Invert(&I1);
343      Project(&I1, PROJECT_INPUT);
344      CHECK(Equiv(P1, I1));
345    }
346
347    {
348      VLOG(1) << "Check Pi_1(T) = Pi_2(T^-1) (delayed).";
349      ProjectFst<Arc> P1(T, PROJECT_INPUT);
350      InvertFst<Arc> I1(T);
351      ProjectFst<Arc> P2(I1, PROJECT_OUTPUT);
352      CHECK(Equiv(P1, P2));
353    }
354
355
356    {
357      VLOG(1) << "Check Pi_2(T) = Pi_1(T^-1) (delayed).";
358      ProjectFst<Arc> P1(T, PROJECT_OUTPUT);
359      InvertFst<Arc> I1(T);
360      ProjectFst<Arc> P2(I1, PROJECT_INPUT);
361      CHECK(Equiv(P1, P2));
362    }
363
364
365    {
366      VLOG(1) << "Check destructive relabeling";
367      static const int kNumLabels = 10;
368      // set up relabeling pairs
369      vector<Label> labelset(kNumLabels);
370      for (size_t i = 0; i < kNumLabels; ++i) labelset[i] = i;
371      for (size_t i = 0; i < kNumLabels; ++i) {
372        swap(labelset[i], labelset[rand() % kNumLabels]);
373      }
374
375      vector<pair<Label, Label> > ipairs1(kNumLabels);
376      vector<pair<Label, Label> > opairs1(kNumLabels);
377      for (size_t i = 0; i < kNumLabels; ++i) {
378        ipairs1[i] = make_pair(i, labelset[i]);
379        opairs1[i] = make_pair(labelset[i], i);
380      }
381      VectorFst<Arc> R(T);
382      Relabel(&R, ipairs1, opairs1);
383
384      vector<pair<Label, Label> > ipairs2(kNumLabels);
385      vector<pair<Label, Label> > opairs2(kNumLabels);
386      for (size_t i = 0; i < kNumLabels; ++i) {
387        ipairs2[i] = make_pair(labelset[i], i);
388        opairs2[i] = make_pair(i, labelset[i]);
389      }
390      Relabel(&R, ipairs2, opairs2);
391      CHECK(Equiv(R, T));
392
393      VLOG(1) << "Check on-the-fly relabeling";
394      RelabelFst<Arc> Rdelay(T, ipairs1, opairs1);
395
396      RelabelFst<Arc> RRdelay(Rdelay, ipairs2, opairs2);
397      CHECK(Equiv(RRdelay, T));
398    }
399
400    {
401      VLOG(1) << "Check encoding/decoding (destructive).";
402      VectorFst<Arc> D(T);
403      uint32 encode_props = 0;
404      if (rand() % 2)
405        encode_props |= kEncodeLabels;
406      if (rand() % 2)
407        encode_props |= kEncodeWeights;
408      EncodeMapper<Arc> encoder(encode_props, ENCODE);
409      Encode(&D, &encoder);
410      Decode(&D, encoder);
411      CHECK(Equiv(D, T));
412    }
413
414    {
415      VLOG(1) << "Check encoding/decoding (delayed).";
416      uint32 encode_props = 0;
417      if (rand() % 2)
418        encode_props |= kEncodeLabels;
419      if (rand() % 2)
420        encode_props |= kEncodeWeights;
421      EncodeMapper<Arc> encoder(encode_props, ENCODE);
422      EncodeFst<Arc> E(T, &encoder);
423      VectorFst<Arc> Encoded(E);
424      DecodeFst<Arc> D(Encoded, encoder);
425      CHECK(Equiv(D, T));
426    }
427
428    {
429      VLOG(1) << "Check gallic mappers (constructive).";
430      ToGallicMapper<Arc> to_mapper;
431      FromGallicMapper<Arc> from_mapper;
432      VectorFst< GallicArc<Arc> > G;
433      VectorFst<Arc> F;
434      ArcMap(T, &G, to_mapper);
435      ArcMap(G, &F, from_mapper);
436      CHECK(Equiv(T, F));
437    }
438
439    {
440      VLOG(1) << "Check gallic mappers (delayed).";
441      ToGallicMapper<Arc> to_mapper;
442      FromGallicMapper<Arc> from_mapper;
443      ArcMapFst<Arc, GallicArc<Arc>, ToGallicMapper<Arc> >
444        G(T, to_mapper);
445      ArcMapFst<GallicArc<Arc>, Arc, FromGallicMapper<Arc> >
446        F(G, from_mapper);
447      CHECK(Equiv(T, F));
448    }
449  }
450
451  // Tests compose-based operations.
452  void TestCompose(const Fst<Arc> &T1, const Fst<Arc> &T2,
453                   const Fst<Arc> &T3) {
454    if (!(Weight::Properties() & kCommutative))
455      return;
456
457    VectorFst<Arc> S1(T1);
458    VectorFst<Arc> S2(T2);
459    VectorFst<Arc> S3(T3);
460
461    ILabelCompare<Arc> icomp;
462    OLabelCompare<Arc> ocomp;
463
464    ArcSort(&S1, ocomp);
465    ArcSort(&S2, ocomp);
466    ArcSort(&S3, icomp);
467
468    {
469      VLOG(1) << "Check composition is associative.";
470      ComposeFst<Arc> C1(S1, S2);
471
472      ComposeFst<Arc> C2(C1, S3);
473      ComposeFst<Arc> C3(S2, S3);
474      ComposeFst<Arc> C4(S1, C3);
475
476      CHECK(Equiv(C2, C4));
477    }
478
479    {
480      VLOG(1) << "Check composition left distributes over union.";
481      UnionFst<Arc> U1(S2, S3);
482      ComposeFst<Arc> C1(S1, U1);
483
484      ComposeFst<Arc> C2(S1, S2);
485      ComposeFst<Arc> C3(S1, S3);
486      UnionFst<Arc> U2(C2, C3);
487
488      CHECK(Equiv(C1, U2));
489    }
490
491    {
492      VLOG(1) << "Check composition right distributes over union.";
493      UnionFst<Arc> U1(S1, S2);
494      ComposeFst<Arc> C1(U1, S3);
495
496      ComposeFst<Arc> C2(S1, S3);
497      ComposeFst<Arc> C3(S2, S3);
498      UnionFst<Arc> U2(C2, C3);
499
500      CHECK(Equiv(C1, U2));
501    }
502
503    VectorFst<Arc> A1(S1);
504    VectorFst<Arc> A2(S2);
505    VectorFst<Arc> A3(S3);
506    Project(&A1, PROJECT_OUTPUT);
507    Project(&A2, PROJECT_INPUT);
508    Project(&A3, PROJECT_INPUT);
509
510    {
511      VLOG(1) << "Check intersection is commutative.";
512      IntersectFst<Arc> I1(A1, A2);
513      IntersectFst<Arc> I2(A2, A1);
514      CHECK(Equiv(I1, I2));
515    }
516
517    {
518      VLOG(1) << "Check all epsilon filters leads to equivalent results.";
519      typedef Matcher< Fst<Arc> > M;
520      ComposeFst<Arc> C1(S1, S2);
521      ComposeFst<Arc> C2(
522          S1, S2,
523          ComposeFstOptions<Arc, M, AltSequenceComposeFilter<M> >());
524      ComposeFst<Arc> C3(
525          S1, S2,
526          ComposeFstOptions<Arc, M, MatchComposeFilter<M> >());
527
528      CHECK(Equiv(C1, C2));
529      CHECK(Equiv(C1, C3));
530    }
531  }
532
533  // Tests sorting operations
534  void TestSort(const Fst<Arc> &T) {
535    ILabelCompare<Arc> icomp;
536    OLabelCompare<Arc> ocomp;
537
538    {
539      VLOG(1) << "Check arc sorted Fst is equivalent to its input.";
540      VectorFst<Arc> S1(T);
541      ArcSort(&S1, icomp);
542      CHECK(Equiv(T, S1));
543    }
544
545    {
546      VLOG(1) << "Check destructive and delayed arcsort are equivalent.";
547      VectorFst<Arc> S1(T);
548      ArcSort(&S1, icomp);
549      ArcSortFst< Arc, ILabelCompare<Arc> > S2(T, icomp);
550      CHECK(Equiv(S1, S2));
551    }
552
553    {
554      VLOG(1) << "Check ilabel sorting vs. olabel sorting with inversions.";
555      VectorFst<Arc> S1(T);
556      VectorFst<Arc> S2(T);
557      ArcSort(&S1, icomp);
558      Invert(&S2);
559      ArcSort(&S2, ocomp);
560      Invert(&S2);
561      CHECK(Equiv(S1, S2));
562    }
563
564    {
565      VLOG(1) << "Check topologically sorted Fst is equivalent to its input.";
566      VectorFst<Arc> S1(T);
567      TopSort(&S1);
568      CHECK(Equiv(T, S1));
569    }
570
571    {
572      VLOG(1) << "Check reverse(reverse(T)) = T";
573      VectorFst< ReverseArc<Arc> > R1;
574      VectorFst<Arc> R2;
575      Reverse(T, &R1);
576      Reverse(R1, &R2);
577      CHECK(Equiv(T, R2));
578    }
579  }
580
581  // Tests optimization operations
582  void TestOptimize(const Fst<Arc> &T) {
583    uint64 tprops = T.Properties(kFstProperties, true);
584    uint64 wprops = Weight::Properties();
585
586    VectorFst<Arc> A(T);
587    Project(&A, PROJECT_INPUT);
588
589    {
590      VLOG(1) << "Check connected FST is equivalent to its input.";
591      VectorFst<Arc> C1(T);
592      Connect(&C1);
593      CHECK(Equiv(T, C1));
594    }
595
596    if ((wprops & kSemiring) == kSemiring &&
597        (tprops & kAcyclic || wprops & kIdempotent)) {
598      VLOG(1) << "Check epsilon-removed FST is equivalent to its input.";
599      VectorFst<Arc> R1(T);
600      RmEpsilon(&R1);
601      CHECK(Equiv(T, R1));
602
603      VLOG(1) << "Check destructive and delayed epsilon removal"
604              << "are equivalent.";
605      RmEpsilonFst<Arc> R2(T);
606      CHECK(Equiv(R1, R2));
607
608      VLOG(1) << "Check an FST with a large proportion"
609              << " of epsilon transitions:";
610      // Maps all transitions of T to epsilon-transitions and append
611      // a non-epsilon transition.
612      VectorFst<Arc> U;
613      ArcMap(T, &U, EpsMapper<Arc>());
614      VectorFst<Arc> V;
615      V.SetStart(V.AddState());
616      Arc arc(1, 1, Weight::One(), V.AddState());
617      V.AddArc(V.Start(), arc);
618      V.SetFinal(arc.nextstate, Weight::One());
619      Concat(&U, V);
620      // Check that epsilon-removal preserves the shortest-distance
621      // from the initial state to the final states.
622      vector<Weight> d;
623      ShortestDistance(U, &d, true);
624      Weight w = U.Start() < d.size() ? d[U.Start()] : Weight::Zero();
625      VectorFst<Arc> U1(U);
626      RmEpsilon(&U1);
627      ShortestDistance(U1, &d, true);
628      Weight w1 = U1.Start() < d.size() ? d[U1.Start()] : Weight::Zero();
629      CHECK(ApproxEqual(w, w1, kTestDelta));
630      RmEpsilonFst<Arc> U2(U);
631      ShortestDistance(U2, &d, true);
632      Weight w2 = U2.Start() < d.size() ? d[U2.Start()] : Weight::Zero();
633      CHECK(ApproxEqual(w, w2, kTestDelta));
634    }
635
636    if ((wprops & kSemiring) == kSemiring && tprops & kAcyclic) {
637      VLOG(1) << "Check determinized FSA is equivalent to its input.";
638      DeterminizeFst<Arc> D(A);
639      CHECK(Equiv(A, D));
640
641
642      int n;
643      {
644        VLOG(1) << "Check size(min(det(A))) <= size(det(A))"
645                << " and  min(det(A)) equiv det(A)";
646        VectorFst<Arc> M(D);
647        n = M.NumStates();
648        Minimize(&M);
649        CHECK(Equiv(D, M));
650        CHECK(M.NumStates() <= n);
651        n = M.NumStates();
652      }
653
654      if (n && (wprops & kIdempotent) == kIdempotent &&
655          A.Properties(kNoEpsilons, true)) {
656        VLOG(1) << "Check that Revuz's algorithm leads to the"
657                << " same number of states as Brozozowski's algorithm";
658
659        // Skip test if A is the empty machine or contains epsilons or
660        // if the semiring is not idempotent (to avoid floating point
661        // errors)
662        VectorFst<Arc> R;
663        Reverse(A, &R);
664        RmEpsilon(&R);
665        DeterminizeFst<Arc> DR(R);
666        VectorFst<Arc> RD;
667        Reverse(DR, &RD);
668        DeterminizeFst<Arc> DRD(RD);
669        VectorFst<Arc> M(DRD);
670        CHECK_EQ(n + 1, M.NumStates());  // Accounts for the epsilon transition
671                                         // to the initial state
672      }
673    }
674
675    if (Arc::Type() == LogArc::Type() || Arc::Type() == StdArc::Type()) {
676      VLOG(1) << "Check reweight(T) equiv T";
677      vector<Weight> potential;
678      VectorFst<Arc> RI(T);
679      VectorFst<Arc> RF(T);
680      while (potential.size() < RI.NumStates())
681        potential.push_back((*weight_generator_)());
682
683      Reweight(&RI, potential, REWEIGHT_TO_INITIAL);
684      CHECK(Equiv(T, RI));
685
686      Reweight(&RF, potential, REWEIGHT_TO_FINAL);
687      CHECK(Equiv(T, RF));
688    }
689
690    if ((wprops & kIdempotent) || (tprops & kAcyclic)) {
691      VLOG(1) << "Check pushed FST is equivalent to input FST.";
692      // Pushing towards the final state.
693      if (wprops & kRightSemiring) {
694        VectorFst<Arc> P1;
695        Push<Arc, REWEIGHT_TO_FINAL>(T, &P1, kPushLabels);
696        CHECK(Equiv(T, P1));
697
698        VectorFst<Arc> P2;
699        Push<Arc, REWEIGHT_TO_FINAL>(T, &P2, kPushWeights);
700        CHECK(Equiv(T, P2));
701
702        VectorFst<Arc> P3;
703        Push<Arc, REWEIGHT_TO_FINAL>(T, &P3, kPushLabels | kPushWeights);
704        CHECK(Equiv(T, P3));
705      }
706
707      // Pushing towards the initial state.
708      if (wprops & kLeftSemiring) {
709        VectorFst<Arc> P1;
710        Push<Arc, REWEIGHT_TO_INITIAL>(T, &P1, kPushLabels);
711        CHECK(Equiv(T, P1));
712
713        VectorFst<Arc> P2;
714        Push<Arc, REWEIGHT_TO_INITIAL>(T, &P2, kPushWeights);
715        CHECK(Equiv(T, P2));
716        VectorFst<Arc> P3;
717        Push<Arc, REWEIGHT_TO_INITIAL>(T, &P3, kPushLabels | kPushWeights);
718        CHECK(Equiv(T, P3));
719      }
720    }
721
722    if ((wprops & (kPath | kCommutative)) == (kPath | kCommutative)) {
723      VLOG(1) << "Check pruning algorithm";
724      {
725        VLOG(1) << "Check equiv. of constructive and destructive algorithms";
726        Weight thresold = (*weight_generator_)();
727        VectorFst<Arc> P1(T);
728        Prune(&P1, thresold);
729        VectorFst<Arc> P2;
730        Prune(T, &P2, thresold);
731        CHECK(Equiv(P1,P2));
732      }
733
734      {
735        VLOG(1) << "Check prune(reverse) equiv reverse(prune)";
736        Weight thresold = (*weight_generator_)();
737        VectorFst< ReverseArc<Arc> > R;
738        VectorFst<Arc> P1(T);
739        VectorFst<Arc> P2;
740        Prune(&P1, thresold);
741        Reverse(T, &R);
742        Prune(&R, thresold.Reverse());
743        Reverse(R, &P2);
744        CHECK(Equiv(P1, P2));
745      }
746      {
747        VLOG(1) << "Check: ShortestDistance(T- prune(T))"
748                << " > ShortestDistance(T) times Thresold";
749        Weight thresold = (*weight_generator_)();
750        VectorFst<Arc> P;
751        Prune(A, &P, thresold);
752        DifferenceFst<Arc> C(A, DeterminizeFst<Arc>
753                             (RmEpsilonFst<Arc>
754                              (ArcMapFst<Arc, Arc,
755                               RmWeightMapper<Arc> >
756                               (P, RmWeightMapper<Arc>()))));
757        Weight sum1 = Times(ShortestDistance(A), thresold);
758        Weight sum2 = ShortestDistance(C);
759        CHECK(Plus(sum1, sum2) == sum1);
760      }
761    }
762    if (tprops & kAcyclic) {
763      VLOG(1) << "Check synchronize(T) equiv T";
764      SynchronizeFst<Arc> S(T);
765      CHECK(Equiv(T, S));
766    }
767  }
768
769  // Tests search operations
770  void TestSearch(const Fst<Arc> &T) {
771    uint64 wprops = Weight::Properties();
772
773    VectorFst<Arc> A(T);
774    Project(&A, PROJECT_INPUT);
775
776    if ((wprops & (kPath | kRightSemiring)) == (kPath | kRightSemiring)) {
777      VLOG(1) << "Check 1-best weight.";
778      VectorFst<Arc> path;
779      ShortestPath(T, &path);
780      Weight tsum = ShortestDistance(T);
781      Weight psum = ShortestDistance(path);
782      CHECK(ApproxEqual(tsum, psum, kTestDelta));
783    }
784
785    if ((wprops & (kPath | kSemiring)) == (kPath | kSemiring)) {
786      VLOG(1) << "Check n-best weights";
787      VectorFst<Arc> R(A);
788      RmEpsilon(&R);
789      int nshortest = rand() % kNumRandomShortestPaths + 2;
790      VectorFst<Arc> paths;
791      ShortestPath(R, &paths, nshortest, true, false,
792                   Weight::Zero(), kNumShortestStates);
793      vector<Weight> distance;
794      ShortestDistance(paths, &distance, true);
795      StateId pstart = paths.Start();
796      if (pstart != kNoStateId) {
797        ArcIterator< Fst<Arc> > piter(paths, pstart);
798        for (; !piter.Done(); piter.Next()) {
799          StateId s = piter.Value().nextstate;
800          Weight nsum = s < distance.size() ?
801              Times(piter.Value().weight, distance[s]) : Weight::Zero();
802          VectorFst<Arc> path;
803          ShortestPath(R, &path);
804          Weight dsum = ShortestDistance(path);
805          CHECK(ApproxEqual(nsum, dsum, kTestDelta));
806          ArcMap(&path, RmWeightMapper<Arc>());
807          VectorFst<Arc> S;
808          Difference(R, path, &S);
809          R = S;
810        }
811      }
812    }
813  }
814
815  // Tests if two FSTS are equivalent by checking if random
816  // strings from one FST are transduced the same by both FSTs.
817  bool Equiv(const Fst<Arc> &fst1, const Fst<Arc> &fst2) {
818    VLOG(1) << "Check FSTs for sanity (including property bits).";
819    CHECK(Verify(fst1));
820    CHECK(Verify(fst2));
821
822    UniformArcSelector<Arc> uniform_selector(seed_);
823    RandGenOptions< UniformArcSelector<Arc> >
824        opts(uniform_selector, kRandomPathLength);
825    return RandEquivalent(fst1, fst2, kNumRandomPaths, kTestDelta, opts);
826  }
827
828  // Random seed
829  int seed_;
830
831  // FST with no states
832  VectorFst<Arc> zero_fst_;
833
834  // FST with one state that accepts epsilon.
835  VectorFst<Arc> one_fst_;
836
837  // FST with one state that accepts all strings.
838  VectorFst<Arc> univ_fst_;
839
840  // Generates weights used in testing.
841  WeightGenerator *weight_generator_;
842
843  // Maximum random path length.
844  static const int kRandomPathLength;
845
846  // Number of random paths to explore.
847  static const int kNumRandomPaths;
848
849  // Maximum number of nshortest paths.
850  static const int kNumRandomShortestPaths;
851
852  // Maximum number of nshortest states.
853  static const int kNumShortestStates;
854
855  // Delta for equivalence tests.
856  static const float kTestDelta;
857
858  DISALLOW_COPY_AND_ASSIGN(WeightedTester);
859};
860
861
862template <class A, class WG>
863const int WeightedTester<A, WG>::kRandomPathLength = 25;
864
865template <class A, class WG>
866const int WeightedTester<A, WG>::kNumRandomPaths = 100;
867
868template <class A, class WG>
869const int WeightedTester<A, WG>::kNumRandomShortestPaths = 100;
870
871template <class A, class WG>
872const int WeightedTester<A, WG>::kNumShortestStates = 10000;
873
874template <class A, class WG>
875const float WeightedTester<A, WG>::kTestDelta = .05;
876
877// This class tests a variety of identities and properties that must
878// hold for various algorithms on unweighted FSAs and that are not tested
879// by WeightedTester. Only the specialization does anything interesting.
880template <class Arc>
881class UnweightedTester {
882 public:
883  UnweightedTester(const Fst<Arc> &zero_fsa, const Fst<Arc> &one_fsa,
884                   const Fst<Arc> &univ_fsa) {}
885
886  void Test(const Fst<Arc> &A1, const Fst<Arc> &A2, const Fst<Arc> &A3) {}
887};
888
889
890// Specialization for StdArc. This should work for any commutative,
891// idempotent semiring when restricted to the unweighted case
892// (being isomorphic to the boolean semiring).
893template <>
894class UnweightedTester<StdArc> {
895 public:
896  typedef StdArc Arc;
897  typedef Arc::Label Label;
898  typedef Arc::StateId StateId;
899  typedef Arc::Weight Weight;
900
901  UnweightedTester(const Fst<Arc> &zero_fsa, const Fst<Arc> &one_fsa,
902                   const Fst<Arc> &univ_fsa)
903      : zero_fsa_(zero_fsa), one_fsa_(one_fsa), univ_fsa_(univ_fsa) {}
904
905  void Test(const Fst<Arc> &A1, const Fst<Arc> &A2, const Fst<Arc> &A3) {
906    TestRational(A1, A2, A3);
907    TestIntersect(A1, A2, A3);
908    TestOptimize(A1);
909  }
910
911 private:
912  // Tests rational operations with identities
913  void TestRational(const Fst<Arc> &A1, const Fst<Arc> &A2,
914                    const Fst<Arc> &A3) {
915
916    {
917      VLOG(1) << "Check the union contains its arguments (destructive).";
918      VectorFst<Arc> U(A1);
919      Union(&U, A2);
920
921      CHECK(Subset(A1, U));
922      CHECK(Subset(A2, U));
923    }
924
925    {
926      VLOG(1) << "Check the union contains its arguments (delayed).";
927      UnionFst<Arc> U(A1, A2);
928
929      CHECK(Subset(A1, U));
930      CHECK(Subset(A2, U));
931    }
932
933    {
934      VLOG(1) << "Check if A^n c A* (destructive).";
935      VectorFst<Arc> C(one_fsa_);
936      int n = rand() % 5;
937      for (int i = 0; i < n; ++i)
938        Concat(&C, A1);
939
940      VectorFst<Arc> S(A1);
941      Closure(&S, CLOSURE_STAR);
942      CHECK(Subset(C, S));
943    }
944
945    {
946      VLOG(1) << "Check if A^n c A* (delayed).";
947      int n = rand() % 5;
948      Fst<Arc> *C = new VectorFst<Arc>(one_fsa_);
949      for (int i = 0; i < n; ++i) {
950        ConcatFst<Arc> *F = new ConcatFst<Arc>(*C, A1);
951        delete C;
952        C = F;
953      }
954      ClosureFst<Arc> S(A1, CLOSURE_STAR);
955      CHECK(Subset(*C, S));
956      delete C;
957    }
958  }
959
960  // Tests intersect-based operations.
961  void TestIntersect(const Fst<Arc> &A1, const Fst<Arc> &A2,
962                   const Fst<Arc> &A3) {
963    VectorFst<Arc> S1(A1);
964    VectorFst<Arc> S2(A2);
965    VectorFst<Arc> S3(A3);
966
967    ILabelCompare<Arc> comp;
968
969    ArcSort(&S1, comp);
970    ArcSort(&S2, comp);
971    ArcSort(&S3, comp);
972
973    {
974      VLOG(1) << "Check the intersection is contained in its arguments.";
975      IntersectFst<Arc> I1(S1, S2);
976      CHECK(Subset(I1, S1));
977      CHECK(Subset(I1, S2));
978    }
979
980    {
981      VLOG(1) << "Check union distributes over intersection.";
982      IntersectFst<Arc> I1(S1, S2);
983      UnionFst<Arc> U1(I1, S3);
984
985      UnionFst<Arc> U2(S1, S3);
986      UnionFst<Arc> U3(S2, S3);
987      ArcSortFst< Arc, ILabelCompare<Arc> > S4(U3, comp);
988      IntersectFst<Arc> I2(U2, S4);
989
990      CHECK(Equiv(U1, I2));
991    }
992
993    VectorFst<Arc> C1;
994    VectorFst<Arc> C2;
995    Complement(S1, &C1);
996    Complement(S2, &C2);
997    ArcSort(&C1, comp);
998    ArcSort(&C2, comp);
999
1000
1001    {
1002      VLOG(1) << "Check S U S' = Sigma*";
1003      UnionFst<Arc> U(S1, C1);
1004      CHECK(Equiv(U, univ_fsa_));
1005    }
1006
1007    {
1008      VLOG(1) << "Check S n S' = {}";
1009      IntersectFst<Arc> I(S1, C1);
1010      CHECK(Equiv(I, zero_fsa_));
1011    }
1012
1013    {
1014      VLOG(1) << "Check (S1' U S2') == (S1 n S2)'";
1015      UnionFst<Arc> U(C1, C2);
1016
1017      IntersectFst<Arc> I(S1, S2);
1018      VectorFst<Arc> C3;
1019      Complement(I, &C3);
1020      CHECK(Equiv(U, C3));
1021    }
1022
1023    {
1024      VLOG(1) << "Check (S1' n S2') == (S1 U S2)'";
1025      IntersectFst<Arc> I(C1, C2);
1026
1027      UnionFst<Arc> U(S1, S2);
1028      VectorFst<Arc> C3;
1029      Complement(U, &C3);
1030      CHECK(Equiv(I, C3));
1031    }
1032  }
1033
1034  // Tests optimization operations
1035  void TestOptimize(const Fst<Arc> &A) {
1036    {
1037      VLOG(1) << "Check determinized FSA is equivalent to its input.";
1038      DeterminizeFst<Arc> D(A);
1039      CHECK(Equiv(A, D));
1040    }
1041
1042    {
1043      VLOG(1) << "Check minimized FSA is equivalent to its input.";
1044      int n;
1045      {
1046        RmEpsilonFst<Arc> R(A);
1047        DeterminizeFst<Arc> D(R);
1048        VectorFst<Arc> M(D);
1049        Minimize(&M);
1050        CHECK(Equiv(A, M));
1051        n = M.NumStates();
1052      }
1053
1054      if (n) {  // Skip test if A is the empty machine
1055        VLOG(1) << "Check that Hopcroft's and Revuz's algorithms lead to the"
1056                << " same number of states as Brozozowski's algorithm";
1057        VectorFst<Arc> R;
1058        Reverse(A, &R);
1059        RmEpsilon(&R);
1060        DeterminizeFst<Arc> DR(R);
1061        VectorFst<Arc> RD;
1062        Reverse(DR, &RD);
1063        DeterminizeFst<Arc> DRD(RD);
1064        VectorFst<Arc> M(DRD);
1065        CHECK_EQ(n + 1, M.NumStates());  // Accounts for the epsilon transition
1066                                         // to the initial state
1067      }
1068    }
1069  }
1070
1071  // Tests if two FSAS are equivalent.
1072  bool Equiv(const Fst<Arc> &fsa1, const Fst<Arc> &fsa2) {
1073    VLOG(1) << "Check FSAs for sanity (including property bits).";
1074    CHECK(Verify(fsa1));
1075    CHECK(Verify(fsa2));
1076
1077    VectorFst<Arc> vfsa1(fsa1);
1078    VectorFst<Arc> vfsa2(fsa2);
1079    RmEpsilon(&vfsa1);
1080    RmEpsilon(&vfsa2);
1081    DeterminizeFst<Arc> dfa1(vfsa1);
1082    DeterminizeFst<Arc> dfa2(vfsa2);
1083
1084    // Test equivalence using union-find algorithm
1085    bool equiv1 = Equivalent(dfa1, dfa2);
1086
1087    // Test equivalence by checking if (S1 - S2) U (S2 - S1) is empty
1088    ILabelCompare<Arc> comp;
1089    VectorFst<Arc> sdfa1(dfa1);
1090    ArcSort(&sdfa1, comp);
1091    VectorFst<Arc> sdfa2(dfa2);
1092    ArcSort(&sdfa2, comp);
1093
1094    DifferenceFst<Arc> dfsa1(sdfa1, sdfa2);
1095    DifferenceFst<Arc> dfsa2(sdfa2, sdfa1);
1096
1097    VectorFst<Arc> ufsa(dfsa1);
1098    Union(&ufsa, dfsa2);
1099    Connect(&ufsa);
1100    bool equiv2 = ufsa.NumStates() == 0;
1101
1102    // Check two equivalence tests match
1103    CHECK((equiv1 && equiv2) || (!equiv1 && !equiv2));
1104
1105    return equiv1;
1106  }
1107
1108  // Tests if FSA1 is a subset of FSA2 (disregarding weights).
1109  bool Subset(const Fst<Arc> &fsa1, const Fst<Arc> &fsa2) {
1110    VLOG(1) << "Check FSAs (incl. property bits) for sanity";
1111    CHECK(Verify(fsa1));
1112    CHECK(Verify(fsa2));
1113
1114    VectorFst<StdArc> vfsa1;
1115    VectorFst<StdArc> vfsa2;
1116    RmEpsilon(&vfsa1);
1117    RmEpsilon(&vfsa2);
1118    ILabelCompare<StdArc> comp;
1119    ArcSort(&vfsa1, comp);
1120    ArcSort(&vfsa2, comp);
1121    IntersectFst<StdArc> ifsa(vfsa1, vfsa2);
1122    DeterminizeFst<StdArc> dfa1(vfsa1);
1123    DeterminizeFst<StdArc> dfa2(ifsa);
1124    return Equivalent(dfa1, dfa2);
1125  }
1126
1127  // Returns complement Fsa
1128  void Complement(const Fst<Arc> &ifsa, MutableFst<Arc> *ofsa) {
1129    RmEpsilonFst<Arc> rfsa(ifsa);
1130    DeterminizeFst<Arc> dfa(rfsa);
1131    DifferenceFst<Arc> cfsa(univ_fsa_, dfa);
1132    *ofsa = cfsa;
1133  }
1134
1135  // FSA with no states
1136  VectorFst<Arc> zero_fsa_;
1137
1138  // FSA with one state that accepts epsilon.
1139  VectorFst<Arc> one_fsa_;
1140
1141  // FSA with one state that accepts all strings.
1142  VectorFst<Arc> univ_fsa_;
1143
1144  DISALLOW_COPY_AND_ASSIGN(UnweightedTester);
1145};
1146
1147
1148// This class tests a variety of identities and properties that must
1149// hold for various FST algorithms. It randomly generates FSTs, using
1150// function object 'weight_generator' to select weights. 'WeightTester'
1151// and 'UnweightedTester' are then called.
1152template <class Arc, class WeightGenerator>
1153class AlgoTester {
1154 public:
1155  typedef typename Arc::Label Label;
1156  typedef typename Arc::StateId StateId;
1157  typedef typename Arc::Weight Weight;
1158
1159  AlgoTester(WeightGenerator generator, int seed) :
1160      weight_generator_(generator), seed_(seed) {
1161      one_fst_.AddState();
1162      one_fst_.SetStart(0);
1163      one_fst_.SetFinal(0, Weight::One());
1164
1165      univ_fst_.AddState();
1166      univ_fst_.SetStart(0);
1167      univ_fst_.SetFinal(0, Weight::One());
1168      for (int i = 0; i < kNumRandomLabels; ++i)
1169        univ_fst_.AddArc(0, Arc(i, i, Weight::One(), 0));
1170  }
1171
1172  void Test() {
1173    VLOG(1) << "weight type = " << Weight::Type();
1174
1175    for (int i = 0; i < FLAGS_repeat; ++i) {
1176      // Random transducers
1177      VectorFst<Arc> T1;
1178      VectorFst<Arc> T2;
1179      VectorFst<Arc> T3;
1180      RandFst(&T1);
1181      RandFst(&T2);
1182      RandFst(&T3);
1183      WeightedTester<Arc, WeightGenerator>
1184        weighted_tester(seed_, zero_fst_, one_fst_,
1185                        univ_fst_, &weight_generator_);
1186      weighted_tester.Test(T1, T2, T3);
1187
1188      VectorFst<Arc> A1(T1);
1189      VectorFst<Arc> A2(T2);
1190      VectorFst<Arc> A3(T3);
1191      Project(&A1, PROJECT_OUTPUT);
1192      Project(&A2, PROJECT_INPUT);
1193      Project(&A3, PROJECT_INPUT);
1194      ArcMap(&A1, rm_weight_mapper);
1195      ArcMap(&A2, rm_weight_mapper);
1196      ArcMap(&A3, rm_weight_mapper);
1197      UnweightedTester<Arc> unweighted_tester(zero_fst_, one_fst_, univ_fst_);
1198      unweighted_tester.Test(A1, A2, A3);
1199    }
1200  }
1201
1202 private:
1203  // Generates a random FST.
1204  void RandFst(MutableFst<Arc> *fst) {
1205    // Determines direction of the arcs wrt state numbering. This way we
1206    // can force acyclicity when desired.
1207    enum ArcDirection { ANY_DIRECTION = 0, FORWARD_DIRECTION = 1,
1208                        REVERSE_DIRECTION = 2, NUM_DIRECTIONS = 3 };
1209
1210    ArcDirection arc_direction = ANY_DIRECTION;
1211    if (rand()/(RAND_MAX  + 1.0) < kAcyclicProb)
1212      arc_direction =  rand() % 2 ? FORWARD_DIRECTION : REVERSE_DIRECTION;
1213
1214    fst->DeleteStates();
1215    StateId ns = rand() % kNumRandomStates;
1216
1217    if (ns == 0)
1218      return;
1219    for (StateId s = 0; s < ns; ++s)
1220      fst->AddState();
1221
1222    StateId start = rand() % ns;
1223    fst->SetStart(start);
1224
1225    size_t na = rand() % kNumRandomArcs;
1226    for (size_t n = 0; n < na; ++n) {
1227      StateId s = rand() % ns;
1228      Arc arc;
1229      arc.ilabel = rand() % kNumRandomLabels;
1230      arc.olabel = rand() % kNumRandomLabels;
1231      arc.weight = weight_generator_();
1232      arc.nextstate = rand() % ns;
1233
1234      if (arc_direction == ANY_DIRECTION ||
1235          (arc_direction == FORWARD_DIRECTION && arc.ilabel > arc.olabel) ||
1236          (arc_direction == REVERSE_DIRECTION && arc.ilabel < arc.olabel))
1237        fst->AddArc(s, arc);
1238    }
1239
1240    StateId nf = rand() % (ns + 1);
1241    for (StateId n = 0; n < nf; ++n) {
1242      StateId s = rand() % ns;
1243      Weight final = weight_generator_();
1244      fst->SetFinal(s, final);
1245    }
1246    VLOG(1) << "Check FST for sanity (including property bits).";
1247    CHECK(Verify(*fst));
1248
1249    // Get/compute all properties.
1250    uint64 props = fst->Properties(kFstProperties, true);
1251
1252    // Select random set of properties to be unknown.
1253    uint64 mask = 0;
1254    for (int n = 0; n < 8; ++n) {
1255      mask |= rand() & 0xff;
1256      mask <<= 8;
1257    }
1258    mask &= ~kTrinaryProperties;
1259    fst->SetProperties(props & ~mask, mask);
1260  }
1261
1262  // Generates weights used in testing.
1263  WeightGenerator weight_generator_;
1264
1265  // Random seed
1266  int seed_;
1267
1268  // FST with no states
1269  VectorFst<Arc> zero_fst_;
1270
1271  // FST with one state that accepts epsilon.
1272  VectorFst<Arc> one_fst_;
1273
1274  // FST with one state that accepts all strings.
1275  VectorFst<Arc> univ_fst_;
1276
1277  // Mapper to remove weights from an Fst
1278  RmWeightMapper<Arc> rm_weight_mapper;
1279
1280  // Maximum number of states in random test Fst.
1281  static const int kNumRandomStates;
1282
1283  // Maximum number of arcs in random test Fst.
1284  static const int kNumRandomArcs;
1285
1286  // Number of alternative random labels.
1287  static const int kNumRandomLabels;
1288
1289  // Probability to force an acyclic Fst
1290  static const float kAcyclicProb;
1291
1292  // Maximum random path length.
1293  static const int kRandomPathLength;
1294
1295  // Number of random paths to explore.
1296  static const int kNumRandomPaths;
1297
1298  DISALLOW_COPY_AND_ASSIGN(AlgoTester);
1299};
1300
1301template <class A, class G> const int AlgoTester<A, G>::kNumRandomStates = 10;
1302
1303template <class A, class G> const int AlgoTester<A, G>::kNumRandomArcs = 25;
1304
1305template <class A, class G> const int AlgoTester<A, G>::kNumRandomLabels = 5;
1306
1307template <class A, class G> const float AlgoTester<A, G>::kAcyclicProb = .25;
1308
1309template <class A, class G> const int AlgoTester<A, G>::kRandomPathLength = 25;
1310
1311template <class A, class G> const int AlgoTester<A, G>::kNumRandomPaths = 100;
1312
1313}  // namespace fst
1314
1315#endif  // FST_TEST_ALGO_TEST_H__
1316