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>
21 using 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
29 namespace fst {
30 namespace script {
31
32 struct 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)
ShortestDistanceOptionsShortestPathOptions46 : 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
51 typedef args::Package<const FstClass &, MutableFstClass *,
52 vector<WeightClass> *, const ShortestPathOptions &>
53 ShortestPathArgs1;
54
55
56 template<class Arc>
ShortestPath(ShortestPathArgs1 * args)57 void 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
155 typedef args::Package<const FstClass &, MutableFstClass *,
156 size_t, bool, bool, WeightClass,
157 int64> ShortestPathArgs2;
158
159 template<class Arc>
ShortestPath(ShortestPathArgs2 * args)160 void 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
172 void ShortestPath(const FstClass &ifst, MutableFstClass *ofst,
173 vector<WeightClass> *distance,
174 const ShortestPathOptions &opts);
175
176
177 // 2
178 void 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