• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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   SetFlags(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