1f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// fstshortestpath.cc 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: allauzen@google.com (Cyril Allauzen) 17f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Modified: jpr@google.com (Jake Ratkiewicz) to use FstClass 18f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 19f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// \file 20f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Find shortest path(s) in an FST. 21f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 22f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/script/shortest-path.h> 23f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 24f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian HodsonDEFINE_double(delta, fst::kDelta, "Comparison/quantization delta"); 25f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian HodsonDEFINE_int64(nshortest, 1, "Return N-shortest paths"); 26f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian HodsonDEFINE_bool(unique, false, "Return unique strings"); 27f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian HodsonDEFINE_string(weight, "", "Weight threshold"); 28f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian HodsonDEFINE_int64(nstate, fst::kNoStateId, "State number threshold"); 29f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian HodsonDEFINE_string(queue_type, "auto", "Queue type: one of \"auto\", " 30f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson "\"fifo\", \"lifo\", \"shortest\', \"state\", \"top\""); 31f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 32f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonint main(int argc, char **argv) { 33f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson namespace s = fst::script; 34f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using fst::script::FstClass; 35f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using fst::script::MutableFstClass; 36f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using fst::script::VectorFstClass; 37f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using fst::script::WeightClass; 38f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 39f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson string usage = "Finds shortest path(s) in an FST.\n\n Usage: "; 40f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson usage += argv[0]; 41f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson usage += " [in.fst [out.fst]]\n"; 42f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 43f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 44f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson std::set_new_handler(FailedNewHandler); 45dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin SET_FLAGS(usage.c_str(), &argc, &argv, true); 46f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (argc > 3) { 47f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShowUsage(); 48f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return 1; 49f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 50f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 51f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson string in_fname = (argc > 1 && (strcmp(argv[1], "-") != 0)) ? argv[1] : ""; 52f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson string out_fname = argc > 2 ? argv[2] : ""; 53f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 54f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson FstClass *ifst = FstClass::Read(in_fname); 55f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!ifst) return 1; 56f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 57f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson WeightClass weight_threshold = FLAGS_weight.empty() ? 58f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson WeightClass::Zero() : 59f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson WeightClass(ifst->WeightType(), FLAGS_weight); 60f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 61f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFstClass ofst(ifst->ArcType()); 62f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<WeightClass> distance; 63f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 64f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst::QueueType qt; 65f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 66f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (FLAGS_queue_type == "auto") { 67f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson qt = fst::AUTO_QUEUE; 68f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else if (FLAGS_queue_type == "fifo") { 69f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson qt = fst::FIFO_QUEUE; 70f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else if (FLAGS_queue_type == "lifo") { 71f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson qt = fst::LIFO_QUEUE; 72f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else if (FLAGS_queue_type == "shortest") { 73f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson qt = fst::SHORTEST_FIRST_QUEUE; 74f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else if (FLAGS_queue_type == "state") { 75f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson qt = fst::STATE_ORDER_QUEUE; 76f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else if (FLAGS_queue_type == "top") { 77f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson qt = fst::TOP_ORDER_QUEUE; 78f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else { 79f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson LOG(ERROR) << "Unknown or unsupported queue type: " << FLAGS_queue_type; 80f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return 1; 81f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 82f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 83f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson s::ShortestPathOptions opts( 84f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson qt, FLAGS_nshortest, FLAGS_unique, false, FLAGS_delta, 85f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson false, weight_threshold, FLAGS_nstate); 86f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 87f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson s::ShortestPath(*ifst, &ofst, &distance, opts); 88f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 89f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ofst.Write(out_fname); 90f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 91f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return 0; 92f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 93