Home | History | Annotate | Download | only in bin
      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 (at) google.com (Cyril Allauzen)
     17 // Modified: jpr (at) 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 
     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