FST  openfst-1.7.2
OpenFst Library
shortest-distance.h
Go to the documentation of this file.
1 // See www.openfst.org for extensive documentation on this weighted
2 // finite-state transducer library.
3 
4 #ifndef FST_SCRIPT_SHORTEST_DISTANCE_H_
5 #define FST_SCRIPT_SHORTEST_DISTANCE_H_
6 
7 #include <tuple>
8 #include <vector>
9 
10 #include <fst/queue.h>
11 #include <fst/shortest-distance.h>
12 #include <fst/script/fst-class.h>
13 #include <fst/script/prune.h>
14 #include <fst/script/script-impl.h>
16 
17 namespace fst {
18 namespace script {
19 
25 };
26 
30  const int64 source;
31  const float delta;
32 
33  ShortestDistanceOptions(QueueType queue_type, ArcFilterType arc_filter_type,
34  int64 source, float delta)
35  : queue_type(queue_type),
36  arc_filter_type(arc_filter_type),
37  source(source),
38  delta(delta) {}
39 };
40 
41 namespace internal {
42 
43 // Code to implement switching on queue and arc filter types.
44 
45 template <class Arc, class Queue, class ArcFilter>
47  using Weight = typename Arc::Weight;
48 
49  static Queue *Construct(const Fst<Arc> &, const std::vector<Weight> *) {
50  return new Queue();
51  }
52 };
53 
54 // Specializations to support queues with different constructors.
55 
56 template <class Arc, class ArcFilter>
57 struct QueueConstructor<Arc, AutoQueue<typename Arc::StateId>, ArcFilter> {
58  using StateId = typename Arc::StateId;
59  using Weight = typename Arc::Weight;
60 
61  // template<class Arc, class ArcFilter>
63  const std::vector<Weight> *distance) {
64  return new AutoQueue<StateId>(fst, distance, ArcFilter());
65  }
66 };
67 
68 template <class Arc, class ArcFilter>
70  Arc, NaturalShortestFirstQueue<typename Arc::StateId, typename Arc::Weight>,
71  ArcFilter> {
72  using StateId = typename Arc::StateId;
73  using Weight = typename Arc::Weight;
74 
76  const Fst<Arc> &, const std::vector<Weight> *distance) {
77  return new NaturalShortestFirstQueue<StateId, Weight>(*distance);
78  }
79 };
80 
81 template <class Arc, class ArcFilter>
82 struct QueueConstructor<Arc, TopOrderQueue<typename Arc::StateId>, ArcFilter> {
83  using StateId = typename Arc::StateId;
84  using Weight = typename Arc::Weight;
85 
87  const std::vector<Weight> *) {
88  return new TopOrderQueue<StateId>(fst, ArcFilter());
89  }
90 };
91 
92 template <class Arc, class Queue, class ArcFilter>
94  std::vector<typename Arc::Weight> *distance,
95  const ShortestDistanceOptions &opts) {
96  std::unique_ptr<Queue> queue(
99  queue.get(), ArcFilter(), opts.source, opts.delta);
100  ShortestDistance(fst, distance, sopts);
101 }
102 
103 template <class Arc, class Queue>
105  std::vector<typename Arc::Weight> *distance,
106  const ShortestDistanceOptions &opts) {
107  switch (opts.arc_filter_type) {
108  case ANY_ARC_FILTER: {
109  ShortestDistance<Arc, Queue, AnyArcFilter<Arc>>(fst, distance, opts);
110  return;
111  }
112  case EPSILON_ARC_FILTER: {
113  ShortestDistance<Arc, Queue, EpsilonArcFilter<Arc>>(fst, distance, opts);
114  return;
115  }
117  ShortestDistance<Arc, Queue, InputEpsilonArcFilter<Arc>>(fst, distance,
118  opts);
119  return;
120  }
122  ShortestDistance<Arc, Queue, OutputEpsilonArcFilter<Arc>>(fst, distance,
123  opts);
124  return;
125  }
126  default: {
127  FSTERROR() << "ShortestDistance: Unknown arc filter type: "
128  << opts.arc_filter_type;
129  distance->clear();
130  distance->resize(1, Arc::Weight::NoWeight());
131  return;
132  }
133  }
134 }
135 
136 } // namespace internal
137 
138 using ShortestDistanceArgs1 =
139  std::tuple<const FstClass &, std::vector<WeightClass> *,
141 
142 template <class Arc>
144  using StateId = typename Arc::StateId;
145  using Weight = typename Arc::Weight;
146  const Fst<Arc> &fst = *(std::get<0>(*args).GetFst<Arc>());
147  const auto &opts = std::get<2>(*args);
148  std::vector<Weight> typed_distance;
149  switch (opts.queue_type) {
150  case AUTO_QUEUE: {
151  internal::ShortestDistance<Arc, AutoQueue<StateId>>(fst, &typed_distance,
152  opts);
153  break;
154  }
155  case FIFO_QUEUE: {
156  internal::ShortestDistance<Arc, FifoQueue<StateId>>(fst, &typed_distance,
157  opts);
158  break;
159  }
160  case LIFO_QUEUE: {
161  internal::ShortestDistance<Arc, LifoQueue<StateId>>(fst, &typed_distance,
162  opts);
163  break;
164  }
165  case SHORTEST_FIRST_QUEUE: {
168  fst, &typed_distance, opts);
169  break;
170  }
171  case STATE_ORDER_QUEUE: {
172  internal::ShortestDistance<Arc, StateOrderQueue<StateId>>(
173  fst, &typed_distance, opts);
174  break;
175  }
176  case TOP_ORDER_QUEUE: {
177  internal::ShortestDistance<Arc, TopOrderQueue<StateId>>(
178  fst, &typed_distance, opts);
179  break;
180  }
181  default: {
182  FSTERROR() << "ShortestDistance: Unknown queue type: " << opts.queue_type;
183  typed_distance.clear();
184  typed_distance.resize(1, Arc::Weight::NoWeight());
185  break;
186  }
187  }
188  internal::CopyWeights(typed_distance, std::get<1>(*args));
189 }
190 
191 using ShortestDistanceArgs2 =
192  std::tuple<const FstClass &, std::vector<WeightClass> *, bool, double>;
193 
194 template <class Arc>
196  using Weight = typename Arc::Weight;
197  const Fst<Arc> &fst = *(std::get<0>(*args).GetFst<Arc>());
198  std::vector<Weight> typed_distance;
199  ShortestDistance(fst, &typed_distance, std::get<2>(*args),
200  std::get<3>(*args));
201  internal::CopyWeights(typed_distance, std::get<1>(*args));
202 }
203 
204 void ShortestDistance(const FstClass &fst, std::vector<WeightClass> *distance,
205  const ShortestDistanceOptions &opts);
206 
207 void ShortestDistance(const FstClass &ifst, std::vector<WeightClass> *distance,
208  bool reverse = false,
209  double delta = fst::kShortestDelta);
210 
211 } // namespace script
212 } // namespace fst
213 
214 #endif // FST_SCRIPT_SHORTEST_DISTANCE_H_
QueueType
Definition: queue.h:56
void CopyWeights(const std::vector< WeightClass > &weights, std::vector< Weight > *typed_weights)
Definition: script-impl.h:187
int64_t int64
Definition: types.h:27
#define FSTERROR()
Definition: util.h:35
static TopOrderQueue< StateId > * Construct(const Fst< Arc > &fst, const std::vector< Weight > *)
void ShortestDistance(const Fst< Arc > &fst, std::vector< typename Arc::Weight > *distance, const ShortestDistanceOptions &opts)
static NaturalShortestFirstQueue< StateId, Weight > * Construct(const Fst< Arc > &, const std::vector< Weight > *distance)
void ShortestDistance(ShortestDistanceArgs1 *args)
constexpr float kShortestDelta
static AutoQueue< StateId > * Construct(const Fst< Arc > &fst, const std::vector< Weight > *distance)
static Queue * Construct(const Fst< Arc > &, const std::vector< Weight > *)
ShortestDistanceOptions(QueueType queue_type, ArcFilterType arc_filter_type, int64 source, float delta)
std::tuple< const FstClass &, std::vector< WeightClass > *, bool, double > ShortestDistanceArgs2
std::tuple< const FstClass &, std::vector< WeightClass > *, const ShortestDistanceOptions & > ShortestDistanceArgs1