1f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 2f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Licensed under the Apache License, Version 2.0 (the "License"); 3f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// you may not use this file except in compliance with the License. 4f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// You may obtain a copy of the License at 5f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 6f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// http://www.apache.org/licenses/LICENSE-2.0 7f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 8f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Unless required by applicable law or agreed to in writing, software 9f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// distributed under the License is distributed on an "AS IS" BASIS, 10f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 11f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// See the License for the specific language governing permissions and 12f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// limitations under the License. 13f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 14f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Copyright 2005-2010 Google, Inc. 15f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Author: jpr@google.com (Jake Ratkiewicz) 16f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 17f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#ifndef FST_SCRIPT_SHORTEST_PATH_H_ 18f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#define FST_SCRIPT_SHORTEST_PATH_H_ 19f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 20f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <vector> 21f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing std::vector; 22f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 23f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/script/arg-packs.h> 24f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/script/fst-class.h> 25f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/script/weight-class.h> 26f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/shortest-path.h> 27f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/script/shortest-distance.h> // for ShortestDistanceOptions 28f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 29f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonnamespace fst { 30f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonnamespace script { 31f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 32f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonstruct ShortestPathOptions 33f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : public fst::script::ShortestDistanceOptions { 34f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const size_t nshortest; 35f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const bool unique; 36f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const bool has_distance; 37f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const bool first_path; 38f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const WeightClass weight_threshold; 39f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const int64 state_threshold; 40f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 41f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestPathOptions(QueueType qt, size_t n = 1, 42f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool u = false, bool hasdist = false, 43f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson float d = fst::kDelta, bool fp = false, 44f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson WeightClass w = fst::script::WeightClass::Zero(), 45f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson int64 s = fst::kNoStateId) 46f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : ShortestDistanceOptions(qt, ANY_ARC_FILTER, kNoStateId, d), 47f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson nshortest(n), unique(u), has_distance(hasdist), first_path(fp), 48f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson weight_threshold(w), state_threshold(s) { } 49f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 50f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 51f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontypedef args::Package<const FstClass &, MutableFstClass *, 52f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<WeightClass> *, const ShortestPathOptions &> 53f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestPathArgs1; 54f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 55f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 56f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc> 57f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonvoid ShortestPath(ShortestPathArgs1 *args) { 58f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const Fst<Arc> &ifst = *(args->arg1.GetFst<Arc>()); 59f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson MutableFst<Arc> *ofst = args->arg2->GetMutableFst<Arc>(); 60f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const ShortestPathOptions &opts = args->arg4; 61f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::StateId StateId; 62f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::Weight Weight; 63f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef AnyArcFilter<Arc> ArcFilter; 64f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 65f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<typename Arc::Weight> weights; 66f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typename Arc::Weight weight_threshold = 67f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson *(opts.weight_threshold.GetWeight<Weight>()); 68f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 69f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson switch (opts.queue_type) { 70f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson case AUTO_QUEUE: { 71f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef AutoQueue<StateId> Queue; 72f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Queue *queue = QueueConstructor<Queue, Arc, 73f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcFilter>::Construct(ifst, &weights); 74f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst::ShortestPathOptions<Arc, Queue, ArcFilter> spopts( 75f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson queue, ArcFilter(), opts.nshortest, opts.unique, 76f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson opts.has_distance, opts.delta, opts.first_path, 77f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson weight_threshold, opts.state_threshold); 78f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestPath(ifst, ofst, &weights, spopts); 79f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delete queue; 80f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return; 81f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 82f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson case FIFO_QUEUE: { 83f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef FifoQueue<StateId> Queue; 84f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Queue *queue = QueueConstructor<Queue, Arc, 85f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcFilter>::Construct(ifst, &weights); 86f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst::ShortestPathOptions<Arc, Queue, ArcFilter> spopts( 87f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson queue, ArcFilter(), opts.nshortest, opts.unique, 88f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson opts.has_distance, opts.delta, opts.first_path, 89f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson weight_threshold, opts.state_threshold); 90f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestPath(ifst, ofst, &weights, spopts); 91f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delete queue; 92f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return; 93f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 94f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson case LIFO_QUEUE: { 95f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef LifoQueue<StateId> Queue; 96f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Queue *queue = QueueConstructor<Queue, Arc, 97f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcFilter >::Construct(ifst, &weights); 98f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst::ShortestPathOptions<Arc, Queue, ArcFilter> spopts( 99f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson queue, ArcFilter(), opts.nshortest, opts.unique, 100f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson opts.has_distance, opts.delta, opts.first_path, 101f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson weight_threshold, opts.state_threshold); 102f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestPath(ifst, ofst, &weights, spopts); 103f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delete queue; 104f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return; 105f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 106f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson case SHORTEST_FIRST_QUEUE: { 107f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef NaturalShortestFirstQueue<StateId, Weight> Queue; 108f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Queue *queue = QueueConstructor<Queue, Arc, 109f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcFilter>::Construct(ifst, &weights); 110f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst::ShortestPathOptions<Arc, Queue, ArcFilter> spopts( 111f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson queue, ArcFilter(), opts.nshortest, opts.unique, 112f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson opts.has_distance, opts.delta, opts.first_path, 113f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson weight_threshold, opts.state_threshold); 114f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestPath(ifst, ofst, &weights, spopts); 115f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delete queue; 116f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return; 117f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 118f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson case STATE_ORDER_QUEUE: { 119f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef StateOrderQueue<StateId> Queue; 120f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Queue *queue = QueueConstructor<Queue, Arc, 121f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcFilter>::Construct(ifst, &weights); 122f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst::ShortestPathOptions<Arc, Queue, ArcFilter> spopts( 123f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson queue, ArcFilter(), opts.nshortest, opts.unique, 124f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson opts.has_distance, opts.delta, opts.first_path, 125f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson weight_threshold, opts.state_threshold); 126f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestPath(ifst, ofst, &weights, spopts); 127f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delete queue; 128f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return; 129f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 130f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson case TOP_ORDER_QUEUE: { 131f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef TopOrderQueue<StateId> Queue; 132f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Queue *queue = QueueConstructor<Queue, Arc, 133f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcFilter>::Construct(ifst, &weights); 134f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst::ShortestPathOptions<Arc, Queue, ArcFilter> spopts( 135f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson queue, ArcFilter(), opts.nshortest, opts.unique, 136f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson opts.has_distance, opts.delta, opts.first_path, 137f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson weight_threshold, opts.state_threshold); 138f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestPath(ifst, ofst, &weights, spopts); 139f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delete queue; 140f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return; 141f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 142f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson default: 143f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson FSTERROR() << "Unknown queue type: " << opts.queue_type; 144f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ofst->SetProperties(kError, kError); 145f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 146f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 147f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Copy the weights back 148f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson args->arg3->resize(weights.size()); 149f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (unsigned i = 0; i < weights.size(); ++i) { 150f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson (*args->arg3)[i] = WeightClass(weights[i]); 151f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 152f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 153f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 154f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 2 155f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontypedef args::Package<const FstClass &, MutableFstClass *, 156f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson size_t, bool, bool, WeightClass, 157f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson int64> ShortestPathArgs2; 158f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 159f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc> 160f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonvoid ShortestPath(ShortestPathArgs2 *args) { 161f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const Fst<Arc> &ifst = *(args->arg1.GetFst<Arc>()); 162f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson MutableFst<Arc> *ofst = args->arg2->GetMutableFst<Arc>(); 163f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typename Arc::Weight weight_threshold = 164f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson *(args->arg6.GetWeight<typename Arc::Weight>()); 165f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 166f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestPath(ifst, ofst, args->arg3, args->arg4, args->arg5, 167f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson weight_threshold, args->arg7); 168f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 169f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 170f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 171f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 1 172f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonvoid ShortestPath(const FstClass &ifst, MutableFstClass *ofst, 173f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<WeightClass> *distance, 174f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const ShortestPathOptions &opts); 175f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 176f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 177f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 2 178f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonvoid ShortestPath(const FstClass &ifst, MutableFstClass *ofst, 179f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson size_t n = 1, bool unique = false, 180f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool first_path = false, 181f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson WeightClass weight_threshold = 182f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst::script::WeightClass::Zero(), 183f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson int64 state_threshold = fst::kNoStateId); 184f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 185f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} // namespace script 186f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} // namespace fst 187f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 188f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 189f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 190f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#endif // FST_SCRIPT_SHORTEST_PATH_H_ 191