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