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