1f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// algo_test.h 2f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 3f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Licensed under the Apache License, Version 2.0 (the "License"); 4f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// you may not use this file except in compliance with the License. 5f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// You may obtain a copy of the License at 6f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 7f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// http://www.apache.org/licenses/LICENSE-2.0 8f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 9f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Unless required by applicable law or agreed to in writing, software 10f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// distributed under the License is distributed on an "AS IS" BASIS, 11f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// See the License for the specific language governing permissions and 13f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// limitations under the License. 14f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 15f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Copyright 2005-2010 Google, Inc. 16f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Author: riley@google.com (Michael Riley) 17f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 18f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// \file 19f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Regression test for various FST algorithms. 20f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 21f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include "./algo_test.h" 22f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 23f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// These determine which semirings are tested. Defining at least 24f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// TEST_TROPICAL and TEST_LOG is recommended. More increase the 25f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// comprehensiveness, but also increase the compilation time. 26f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 27f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#define TEST_TROPICAL 28f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#define TEST_LOG 29f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// #define TEST_MINMAX 30f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// #define TEST_LEFT_STRING 31f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// #define TEST_RIGHT_STRING 32f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// #define TEST_GALLIC 33f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// #define TEST_LEXICOGRAPHIC 34f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// #define TEST_POWER 35f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 36f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian HodsonDEFINE_int32(seed, -1, "random seed"); 37f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian HodsonDEFINE_int32(repeat, 25, "number of test repetitions"); 38f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 39f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing fst::StdArc; 40f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing fst::TropicalWeightGenerator; 41f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 42f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing fst::LogArc; 43f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing fst::LogWeightGenerator; 44f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 45f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing fst::MinMaxArc; 46f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing fst::MinMaxWeightGenerator; 47f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 48f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing fst::StringArc; 49f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing fst::StringWeightGenerator; 50f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing fst::STRING_LEFT; 51f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing fst::STRING_RIGHT; 52f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 53f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing fst::GallicArc; 54f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing fst::GallicWeightGenerator; 55f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 56f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing fst::LexicographicArc; 57f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing fst::TropicalWeight; 58f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing fst::LexicographicWeightGenerator; 59f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 60f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing fst::ArcTpl; 61f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing fst::PowerWeight; 62f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing fst::PowerWeightGenerator; 63f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 64f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing fst::AlgoTester; 65f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 66f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonint main(int argc, char **argv) { 67f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson FLAGS_fst_verify_properties = true; 68f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson std::set_new_handler(FailedNewHandler); 69dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin SET_FLAGS(argv[0], &argc, &argv, true); 70f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 71f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const int kCacheGcLimit = 20; 72f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 73f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson int seed = FLAGS_seed >= 0 ? FLAGS_seed : time(0); 74f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson srand(seed); 75f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson LOG(INFO) << "Seed = " << seed; 76f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 77f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson FLAGS_fst_default_cache_gc = rand() % 2; 78f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson FLAGS_fst_default_cache_gc_limit = rand() % kCacheGcLimit; 79f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "default_cache_gc:" << FLAGS_fst_default_cache_gc; 80f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "default_cache_gc_limit:" << FLAGS_fst_default_cache_gc_limit; 81f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 82f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#ifdef TEST_TROPICAL 83f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson TropicalWeightGenerator tropical_generator(seed, false); 84f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson AlgoTester<StdArc, TropicalWeightGenerator> 85f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson tropical_tester(tropical_generator, seed); 86f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson tropical_tester.Test(); 87f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#endif // TEST_TROPICAL 88f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 89f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#ifdef TEST_LOG 90f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson LogWeightGenerator log_generator(seed, false); 91f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson AlgoTester<LogArc, LogWeightGenerator> 92f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson log_tester(log_generator, seed); 93f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson log_tester.Test(); 94f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#endif // TEST_LOG 95f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 96f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#ifdef TEST_MINMAX 97f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson MinMaxWeightGenerator minmax_generator(seed, false); 98f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson AlgoTester<MinMaxArc, MinMaxWeightGenerator> 99f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson minmax_tester(minmax_generator, seed); 100f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson minmax_tester.Test(); 101f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#endif 102f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 103f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#ifdef TEST_LEFT_STRING 104f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StringWeightGenerator<int> left_string_generator(seed, false); 105f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson AlgoTester<StringArc<>, StringWeightGenerator<int> > 106f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson left_string_tester(left_string_generator, seed); 107f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson left_string_tester.Test(); 108f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#endif // TEST_LEFT_STRING 109f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 110f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#ifdef TEST_RIGHT_STRING 111f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StringWeightGenerator<int, STRING_RIGHT> right_string_generator(seed, false); 112f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson AlgoTester<StringArc<STRING_RIGHT>, 113f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StringWeightGenerator<int, STRING_RIGHT> > 114f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson right_string_tester(right_string_generator, seed); 115f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson right_string_tester.Test(); 116f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#endif // TEST_RIGHT_STRING 117f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 118f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#ifdef TEST_GALLIC 119f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef GallicArc<StdArc> StdGallicArc; 120f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef GallicWeightGenerator<int, TropicalWeightGenerator> 121f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson TropicalGallicWeightGenerator; 122f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 123f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson TropicalGallicWeightGenerator tropical_gallic_generator(seed, false); 124f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson AlgoTester<StdGallicArc, TropicalGallicWeightGenerator> 125f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson gallic_tester(tropical_gallic_generator, seed); 126f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson gallic_tester.Test(); 127f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#endif // TEST_GALLIC 128f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 129f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#ifdef TEST_LEXICOGRAPHIC 130f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef LexicographicArc<TropicalWeight, TropicalWeight> 131f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson TropicalLexicographicArc; 132f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef LexicographicWeightGenerator<TropicalWeightGenerator, 133f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson TropicalWeightGenerator> TropicalLexicographicWeightGenerator; 134f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson TropicalLexicographicWeightGenerator lexicographic_generator(seed, false); 135f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson AlgoTester<TropicalLexicographicArc, TropicalLexicographicWeightGenerator> 136f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson lexicographic_tester(lexicographic_generator, seed); 137f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson lexicographic_tester.Test(); 138f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#endif // TEST_LEXICOGRAPHIC 139f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 140f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#ifdef TEST_POWER 141f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef PowerWeight<TropicalWeight, 3> TropicalCubeWeight; 142f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef ArcTpl<TropicalCubeWeight> TropicalCubeArc; 143f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef PowerWeightGenerator<TropicalWeightGenerator, 3> 144f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson TropicalCubeWeightGenerator; 145f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 146f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson TropicalCubeWeightGenerator tropical_cube_generator(seed, false); 147f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson AlgoTester<TropicalCubeArc, TropicalCubeWeightGenerator> 148f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson tropical_cube_tester(tropical_cube_generator, seed); 149f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson tropical_cube_tester.Test(); 150f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#endif // TEST_POWER 151f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 152f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson cout << "PASS" << endl; 153f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 154f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return 0; 155f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 156