FST  openfst-1.7.2
OpenFst Library
shortest-path.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 // Functions to find shortest paths in an FST.
5 
6 #ifndef FST_SHORTEST_PATH_H_
7 #define FST_SHORTEST_PATH_H_
8 
9 #include <functional>
10 #include <type_traits>
11 #include <utility>
12 #include <vector>
13 
14 #include <fst/log.h>
15 
16 #include <fst/cache.h>
17 #include <fst/determinize.h>
18 #include <fst/queue.h>
19 #include <fst/shortest-distance.h>
20 #include <fst/test-properties.h>
21 
22 
23 namespace fst {
24 
25 template <class Arc, class Queue, class ArcFilter>
27  : public ShortestDistanceOptions<Arc, Queue, ArcFilter> {
28  using StateId = typename Arc::StateId;
29  using Weight = typename Arc::Weight;
30 
31  int32 nshortest; // Returns n-shortest paths.
32  bool unique; // Only returns paths with distinct input strings.
33  bool has_distance; // Distance vector already contains the
34  // shortest distance from the initial state.
35  bool first_path; // Single shortest path stops after finding the first
36  // path to a final state; that path is the shortest path
37  // only when:
38  // (1) using the ShortestFirstQueue with all the weights
39  // in the FST being between One() and Zero() according to
40  // NaturalLess or when
41  // (2) using the NaturalAStarQueue with an admissible
42  // and consistent estimate.
43  Weight weight_threshold; // Pruning weight threshold.
44  StateId state_threshold; // Pruning state threshold.
45 
46  ShortestPathOptions(Queue *queue, ArcFilter filter, int32 nshortest = 1,
47  bool unique = false, bool has_distance = false,
48  float delta = kShortestDelta, bool first_path = false,
49  Weight weight_threshold = Weight::Zero(),
50  StateId state_threshold = kNoStateId)
51  : ShortestDistanceOptions<Arc, Queue, ArcFilter>(queue, filter,
52  kNoStateId, delta),
53  nshortest(nshortest),
54  unique(unique),
55  has_distance(has_distance),
56  first_path(first_path),
57  weight_threshold(std::move(weight_threshold)),
58  state_threshold(state_threshold) {}
59 };
60 
61 namespace internal {
62 
63 constexpr size_t kNoArc = -1;
64 
65 // Helper function for SingleShortestPath building the shortest path as a left-
66 // to-right machine backwards from the best final state. It takes the input
67 // FST passed to SingleShortestPath and the parent vector and f_parent returned
68 // by that function, and builds the result into the provided output mutable FS
69 // This is not normally called by users; see ShortestPath instead.
70 template <class Arc>
72  const Fst<Arc> &ifst, MutableFst<Arc> *ofst,
73  const std::vector<std::pair<typename Arc::StateId, size_t>> &parent,
74  typename Arc::StateId f_parent) {
75  using StateId = typename Arc::StateId;
76  ofst->DeleteStates();
77  ofst->SetInputSymbols(ifst.InputSymbols());
78  ofst->SetOutputSymbols(ifst.OutputSymbols());
79  StateId s_p = kNoStateId;
80  StateId d_p = kNoStateId;
81  for (StateId state = f_parent, d = kNoStateId; state != kNoStateId;
82  d = state, state = parent[state].first) {
83  d_p = s_p;
84  s_p = ofst->AddState();
85  if (d == kNoStateId) {
86  ofst->SetFinal(s_p, ifst.Final(f_parent));
87  } else {
88  ArcIterator<Fst<Arc>> aiter(ifst, state);
89  aiter.Seek(parent[d].second);
90  auto arc = aiter.Value();
91  arc.nextstate = d_p;
92  ofst->AddArc(s_p, std::move(arc));
93  }
94  }
95  ofst->SetStart(s_p);
96  if (ifst.Properties(kError, false)) ofst->SetProperties(kError, kError);
97  ofst->SetProperties(
100 }
101 
102 // Helper function for SingleShortestPath building a tree of shortest paths to
103 // every final state in the input FST. It takes the input FST and parent values
104 // computed by SingleShortestPath and builds into the output mutable FST the
105 // subtree of ifst that consists only of the best paths to all final states.
106 // This is not normally called by users; see ShortestPath instead.
107 template <class Arc>
109  const Fst<Arc> &ifst, MutableFst<Arc> *ofst,
110  const std::vector<std::pair<typename Arc::StateId, size_t>> &parent) {
111  ofst->DeleteStates();
112  ofst->SetInputSymbols(ifst.InputSymbols());
113  ofst->SetOutputSymbols(ifst.OutputSymbols());
114  ofst->SetStart(ifst.Start());
115  for (StateIterator<Fst<Arc>> siter(ifst); !siter.Done(); siter.Next()) {
116  ofst->AddState();
117  ofst->SetFinal(siter.Value(), ifst.Final(siter.Value()));
118  }
119  for (const auto &pair : parent) {
120  if (pair.first != kNoStateId && pair.second != kNoArc) {
121  ArcIterator<Fst<Arc>> aiter(ifst, pair.first);
122  aiter.Seek(pair.second);
123  ofst->AddArc(pair.first, aiter.Value());
124  }
125  }
126  if (ifst.Properties(kError, false)) ofst->SetProperties(kError, kError);
127  ofst->SetProperties(
128  ShortestPathProperties(ofst->Properties(kFstProperties, false), true),
130 }
131 
132 // Implements the stopping criterion when ShortestPathOptions::first_path
133 // is set to true:
134 // operator()(s, d, f) == true
135 // iff every successful path through state 's' has a cost greater or equal
136 // to 'f' under the assumption that 'd' is the shortest distance to state 's'.
137 // Correct when using the ShortestFirstQueue with all the weights in the FST
138 // being between One() and Zero() according to NaturalLess
139 template <typename S, typename W, typename Queue>
141  FirstPathSelect(const Queue &) {}
142  bool operator()(S s, W d, W f) const { return f == Plus(d, f); }
143 };
144 
145 // Specialisation for A*.
146 // Correct when the estimate is admissible and consistent.
147 template <typename S, typename W, typename Estimate>
148 class FirstPathSelect<S, W, NaturalAStarQueue<S, W, Estimate>> {
149  public:
151 
153  : estimate_(state_queue.GetCompare().GetEstimate()) {}
154 
155  bool operator()(S s, W d, W f) const {
156  return f == Plus(Times(d, estimate_(s)), f);
157  }
158 
159  private:
160  const Estimate &estimate_;
161 };
162 
163 // Shortest-path algorithm. It builds the output mutable FST so that it contains
164 // the shortest path in the input FST; distance returns the shortest distances
165 // from the source state to each state in the input FST, and the options struct
166 // is
167 // used to specify options such as the queue discipline, the arc filter and
168 // delta. The super_final option is an output parameter indicating the final
169 // state, and the parent argument is used for the storage of the backtrace path
170 // for each state 1 to n, (i.e., the best previous state and the arc that
171 // transition to state n.) The shortest path is the lowest weight path w.r.t.
172 // the natural semiring order. The weights need to be right distributive and
173 // have the path (kPath) property. False is returned if an error is encountered.
174 //
175 // This is not normally called by users; see ShortestPath instead (with n = 1).
176 template <class Arc, class Queue, class ArcFilter>
178  const Fst<Arc> &ifst, std::vector<typename Arc::Weight> *distance,
180  typename Arc::StateId *f_parent,
181  std::vector<std::pair<typename Arc::StateId, size_t>> *parent) {
182  using StateId = typename Arc::StateId;
183  using Weight = typename Arc::Weight;
184  static_assert(IsPath<Weight>::value, "Weight must have path property.");
185  static_assert((Weight::Properties() & kRightSemiring) == kRightSemiring,
186  "Weight must be right distributive.");
187  parent->clear();
188  *f_parent = kNoStateId;
189  if (ifst.Start() == kNoStateId) return true;
190  std::vector<bool> enqueued;
191  auto state_queue = opts.state_queue;
192  const auto source = (opts.source == kNoStateId) ? ifst.Start() : opts.source;
193  bool final_seen = false;
194  auto f_distance = Weight::Zero();
195  distance->clear();
196  state_queue->Clear();
197  while (distance->size() < source) {
198  distance->push_back(Weight::Zero());
199  enqueued.push_back(false);
200  parent->emplace_back(kNoStateId, kNoArc);
201  }
202  distance->push_back(Weight::One());
203  parent->emplace_back(kNoStateId, kNoArc);
204  state_queue->Enqueue(source);
205  enqueued.push_back(true);
206  while (!state_queue->Empty()) {
207  const auto s = state_queue->Head();
208  state_queue->Dequeue();
209  enqueued[s] = false;
210  const auto sd = (*distance)[s];
211  // If we are using a shortest queue, no other path is going to be shorter
212  // than f_distance at this point.
213  using FirstPath = FirstPathSelect<StateId, Weight, Queue>;
214  if (opts.first_path && final_seen &&
215  FirstPath(*state_queue)(s, sd, f_distance)) {
216  break;
217  }
218  if (ifst.Final(s) != Weight::Zero()) {
219  const auto plus = Plus(f_distance, Times(sd, ifst.Final(s)));
220  if (f_distance != plus) {
221  f_distance = plus;
222  *f_parent = s;
223  }
224  if (!f_distance.Member()) return false;
225  final_seen = true;
226  }
227  for (ArcIterator<Fst<Arc>> aiter(ifst, s); !aiter.Done(); aiter.Next()) {
228  const auto &arc = aiter.Value();
229  while (distance->size() <= arc.nextstate) {
230  distance->push_back(Weight::Zero());
231  enqueued.push_back(false);
232  parent->emplace_back(kNoStateId, kNoArc);
233  }
234  auto &nd = (*distance)[arc.nextstate];
235  const auto weight = Times(sd, arc.weight);
236  if (nd != Plus(nd, weight)) {
237  nd = Plus(nd, weight);
238  if (!nd.Member()) return false;
239  (*parent)[arc.nextstate] = std::make_pair(s, aiter.Position());
240  if (!enqueued[arc.nextstate]) {
241  state_queue->Enqueue(arc.nextstate);
242  enqueued[arc.nextstate] = true;
243  } else {
244  state_queue->Update(arc.nextstate);
245  }
246  }
247  }
248  }
249  return true;
250 }
251 
252 template <class StateId, class Weight>
254  public:
255  ShortestPathCompare(const std::vector<std::pair<StateId, Weight>> &pairs,
256  const std::vector<Weight> &distance, StateId superfinal,
257  float delta)
258  : pairs_(pairs),
259  distance_(distance),
260  superfinal_(superfinal),
261  delta_(delta) {}
262 
263  bool operator()(const StateId x, const StateId y) const {
264  const auto &px = pairs_[x];
265  const auto &py = pairs_[y];
266  const auto wx = Times(PWeight(px.first), px.second);
267  const auto wy = Times(PWeight(py.first), py.second);
268  // Penalize complete paths to ensure correct results with inexact weights.
269  // This forms a strict weak order so long as ApproxEqual(a, b) =>
270  // ApproxEqual(a, c) for all c s.t. less_(a, c) && less_(c, b).
271  if (px.first == superfinal_ && py.first != superfinal_) {
272  return less_(wy, wx) || ApproxEqual(wx, wy, delta_);
273  } else if (py.first == superfinal_ && px.first != superfinal_) {
274  return less_(wy, wx) && !ApproxEqual(wx, wy, delta_);
275  } else {
276  return less_(wy, wx);
277  }
278  }
279 
280  private:
281  Weight PWeight(StateId state) const {
282  return (state == superfinal_)
283  ? Weight::One()
284  : (state < distance_.size()) ? distance_[state] : Weight::Zero();
285  }
286 
287  const std::vector<std::pair<StateId, Weight>> &pairs_;
288  const std::vector<Weight> &distance_;
289  const StateId superfinal_;
290  const float delta_;
291  NaturalLess<Weight> less_;
292 };
293 
294 // N-Shortest-path algorithm: implements the core n-shortest path algorithm.
295 // The output is built reversed. See below for versions with more options and
296 // *not reversed*.
297 //
298 // The output mutable FST contains the REVERSE of n'shortest paths in the input
299 // FST; distance must contain the shortest distance from each state to a final
300 // state in the input FST; delta is the convergence delta.
301 //
302 // The n-shortest paths are the n-lowest weight paths w.r.t. the natural
303 // semiring order. The single path that can be read from the ith of at most n
304 // transitions leaving the initial state of the input FST is the ith shortest
305 // path. Disregarding the initial state and initial transitions, the
306 // n-shortest paths, in fact, form a tree rooted at the single final state.
307 //
308 // The weights need to be left and right distributive (kSemiring) and have the
309 // path (kPath) property.
310 //
311 // Arc weights must satisfy the property that the sum of the weights of one or
312 // more paths from some state S to T is never Zero(). In particular, arc weights
313 // are never Zero().
314 //
315 // For more information, see:
316 //
317 // Mohri, M, and Riley, M. 2002. An efficient algorithm for the n-best-strings
318 // problem. In Proc. ICSLP.
319 //
320 // The algorithm relies on the shortest-distance algorithm. There are some
321 // issues with the pseudo-code as written in the paper (viz., line 11).
322 //
323 // IMPLEMENTATION NOTE: The input FST can be a delayed FST and at any state in
324 // its expansion the values of distance vector need only be defined at that time
325 // for the states that are known to exist.
326 template <class Arc, class RevArc>
327 void NShortestPath(const Fst<RevArc> &ifst, MutableFst<Arc> *ofst,
328  const std::vector<typename Arc::Weight> &distance,
329  int32 nshortest, float delta = kShortestDelta,
330  typename Arc::Weight weight_threshold = Arc::Weight::Zero(),
331  typename Arc::StateId state_threshold = kNoStateId) {
332  using StateId = typename Arc::StateId;
333  using Weight = typename Arc::Weight;
334  using Pair = std::pair<StateId, Weight>;
335  static_assert((Weight::Properties() & kPath) == kPath,
336  "Weight must have path property.");
337  static_assert((Weight::Properties() & kSemiring) == kSemiring,
338  "Weight must be distributive.");
339  if (nshortest <= 0) return;
340  ofst->DeleteStates();
341  ofst->SetInputSymbols(ifst.InputSymbols());
342  ofst->SetOutputSymbols(ifst.OutputSymbols());
343  // Each state in ofst corresponds to a path with weight w from the initial
344  // state of ifst to a state s in ifst, that can be characterized by a pair
345  // (s, w). The vector pairs maps each state in ofst to the corresponding
346  // pair maps states in ofst to the corresponding pair (s, w).
347  std::vector<Pair> pairs;
348  // The supefinal state is denoted by kNoStateId. The distance from the
349  // superfinal state to the final state is semiring One, so
350  // `distance[kNoStateId]` is not needed.
351  const ShortestPathCompare<StateId, Weight> compare(pairs, distance,
352  kNoStateId, delta);
353  const NaturalLess<Weight> less;
354  if (ifst.Start() == kNoStateId || distance.size() <= ifst.Start() ||
355  distance[ifst.Start()] == Weight::Zero() ||
356  less(weight_threshold, Weight::One()) || state_threshold == 0) {
357  if (ifst.Properties(kError, false)) ofst->SetProperties(kError, kError);
358  return;
359  }
360  ofst->SetStart(ofst->AddState());
361  const auto final_state = ofst->AddState();
362  ofst->SetFinal(final_state, Weight::One());
363  while (pairs.size() <= final_state) {
364  pairs.push_back(std::make_pair(kNoStateId, Weight::Zero()));
365  }
366  pairs[final_state] = std::make_pair(ifst.Start(), Weight::One());
367  std::vector<StateId> heap;
368  heap.push_back(final_state);
369  const auto limit = Times(distance[ifst.Start()], weight_threshold);
370  // r[s + 1], s state in fst, is the number of states in ofst which
371  // corresponding pair contains s, i.e., it is number of paths computed so far
372  // to s. Valid for s == kNoStateId (the superfinal state).
373  std::vector<int> r;
374  while (!heap.empty()) {
375  std::pop_heap(heap.begin(), heap.end(), compare);
376  const auto state = heap.back();
377  const auto p = pairs[state];
378  heap.pop_back();
379  const auto d =
380  (p.first == kNoStateId)
381  ? Weight::One()
382  : (p.first < distance.size()) ? distance[p.first] : Weight::Zero();
383  if (less(limit, Times(d, p.second)) ||
384  (state_threshold != kNoStateId &&
385  ofst->NumStates() >= state_threshold)) {
386  continue;
387  }
388  while (r.size() <= p.first + 1) r.push_back(0);
389  ++r[p.first + 1];
390  if (p.first == kNoStateId) {
391  ofst->AddArc(ofst->Start(), Arc(0, 0, Weight::One(), state));
392  }
393  if ((p.first == kNoStateId) && (r[p.first + 1] == nshortest)) break;
394  if (r[p.first + 1] > nshortest) continue;
395  if (p.first == kNoStateId) continue;
396  for (ArcIterator<Fst<RevArc>> aiter(ifst, p.first); !aiter.Done();
397  aiter.Next()) {
398  const auto &rarc = aiter.Value();
399  Arc arc(rarc.ilabel, rarc.olabel, rarc.weight.Reverse(), rarc.nextstate);
400  const auto weight = Times(p.second, arc.weight);
401  const auto next = ofst->AddState();
402  pairs.push_back(std::make_pair(arc.nextstate, weight));
403  arc.nextstate = state;
404  ofst->AddArc(next, std::move(arc));
405  heap.push_back(next);
406  std::push_heap(heap.begin(), heap.end(), compare);
407  }
408  const auto final_weight = ifst.Final(p.first).Reverse();
409  if (final_weight != Weight::Zero()) {
410  const auto weight = Times(p.second, final_weight);
411  const auto next = ofst->AddState();
412  pairs.push_back(std::make_pair(kNoStateId, weight));
413  ofst->AddArc(next, Arc(0, 0, final_weight, state));
414  heap.push_back(next);
415  std::push_heap(heap.begin(), heap.end(), compare);
416  }
417  }
418  Connect(ofst);
419  if (ifst.Properties(kError, false)) ofst->SetProperties(kError, kError);
420  ofst->SetProperties(
423 }
424 
425 } // namespace internal
426 
427 // N-Shortest-path algorithm: this version allows finer control via the options
428 // argument. See below for a simpler interface. The output mutable FST contains
429 // the n-shortest paths in the input FST; the distance argument is used to
430 // return the shortest distances from the source state to each state in the
431 // input FST, and the options struct is used to specify the number of paths to
432 // return, whether they need to have distinct input strings, the queue
433 // discipline, the arc filter and the convergence delta.
434 //
435 // The n-shortest paths are the n-lowest weight paths w.r.t. the natural
436 // semiring order. The single path that can be read from the ith of at most n
437 // transitions leaving the initial state of the output FST is the ith shortest
438 // path.
439 // Disregarding the initial state and initial transitions, The n-shortest paths,
440 // in fact, form a tree rooted at the single final state.
441 //
442 // The weights need to be right distributive and have the path (kPath) property.
443 // They need to be left distributive as well for nshortest > 1.
444 //
445 // For more information, see:
446 //
447 // Mohri, M, and Riley, M. 2002. An efficient algorithm for the n-best-strings
448 // problem. In Proc. ICSLP.
449 //
450 // The algorithm relies on the shortest-distance algorithm. There are some
451 // issues with the pseudo-code as written in the paper (viz., line 11).
452 template <class Arc, class Queue, class ArcFilter,
453  typename std::enable_if<IsPath<typename Arc::Weight>::value>::type * =
454  nullptr>
455 void ShortestPath(const Fst<Arc> &ifst, MutableFst<Arc> *ofst,
456  std::vector<typename Arc::Weight> *distance,
458  using StateId = typename Arc::StateId;
459  using Weight = typename Arc::Weight;
460  using RevArc = ReverseArc<Arc>;
461  if (opts.nshortest == 1) {
462  std::vector<std::pair<StateId, size_t>> parent;
463  StateId f_parent;
464  if (internal::SingleShortestPath(ifst, distance, opts, &f_parent,
465  &parent)) {
466  internal::SingleShortestPathBacktrace(ifst, ofst, parent, f_parent);
467  } else {
468  ofst->SetProperties(kError, kError);
469  }
470  return;
471  }
472  if (opts.nshortest <= 0) return;
473  if (!opts.has_distance) {
474  ShortestDistance(ifst, distance, opts);
475  if (distance->size() == 1 && !(*distance)[0].Member()) {
476  ofst->SetProperties(kError, kError);
477  return;
478  }
479  }
480  // Algorithm works on the reverse of 'fst'; 'distance' is the distance to the
481  // final state in 'rfst', 'ofst' is built as the reverse of the tree of
482  // n-shortest path in 'rfst'.
483  VectorFst<RevArc> rfst;
484  Reverse(ifst, &rfst);
485  auto d = Weight::Zero();
486  for (ArcIterator<VectorFst<RevArc>> aiter(rfst, 0); !aiter.Done();
487  aiter.Next()) {
488  const auto &arc = aiter.Value();
489  const auto state = arc.nextstate - 1;
490  if (state < distance->size()) {
491  d = Plus(d, Times(arc.weight.Reverse(), (*distance)[state]));
492  }
493  }
494  // TODO(kbg): Avoid this expensive vector operation.
495  distance->insert(distance->begin(), d);
496  if (!opts.unique) {
497  internal::NShortestPath(rfst, ofst, *distance, opts.nshortest, opts.delta,
498  opts.weight_threshold, opts.state_threshold);
499  } else {
500  std::vector<Weight> ddistance;
502  DeterminizeFst<RevArc> dfst(rfst, distance, &ddistance, dopts);
503  internal::NShortestPath(dfst, ofst, ddistance, opts.nshortest, opts.delta,
504  opts.weight_threshold, opts.state_threshold);
505  }
506  // TODO(kbg): Avoid this expensive vector operation.
507  distance->erase(distance->begin());
508 }
509 
510 template <class Arc, class Queue, class ArcFilter,
511  typename std::enable_if<!IsPath<typename Arc::Weight>::value>::type
512  * = nullptr>
513 void ShortestPath(const Fst<Arc> &, MutableFst<Arc> *ofst,
514  std::vector<typename Arc::Weight> *,
516  FSTERROR() << "ShortestPath: Weight needs to have the "
517  << "path property and be distributive: " << Arc::Weight::Type();
518  ofst->SetProperties(kError, kError);
519 }
520 
521 // Shortest-path algorithm: simplified interface. See above for a version that
522 // allows finer control. The output mutable FST contains the n-shortest paths
523 // in the input FST. The queue discipline is automatically selected. When unique
524 // is true, only paths with distinct input label sequences are returned.
525 //
526 // The n-shortest paths are the n-lowest weight paths w.r.t. the natural
527 // semiring order. The single path that can be read from the ith of at most n
528 // transitions leaving the initial state of the output FST is the ith best path.
529 // The weights need to be right distributive and have the path (kPath) property.
530 template <class Arc>
531 void ShortestPath(const Fst<Arc> &ifst, MutableFst<Arc> *ofst,
532  int32 nshortest = 1, bool unique = false,
533  bool first_path = false,
534  typename Arc::Weight weight_threshold = Arc::Weight::Zero(),
535  typename Arc::StateId state_threshold = kNoStateId,
536  float delta = kShortestDelta) {
537  using StateId = typename Arc::StateId;
538  std::vector<typename Arc::Weight> distance;
540  AutoQueue<StateId> state_queue(ifst, &distance, arc_filter);
542  &state_queue, arc_filter, nshortest, unique, false, delta, first_path,
543  weight_threshold, state_threshold);
544  ShortestPath(ifst, ofst, &distance, opts);
545 }
546 
547 } // namespace fst
548 
549 #endif // FST_SHORTEST_PATH_H_
void NShortestPath(const Fst< RevArc > &ifst, MutableFst< Arc > *ofst, const std::vector< typename Arc::Weight > &distance, int32 nshortest, float delta=kShortestDelta, typename Arc::Weight weight_threshold=Arc::Weight::Zero(), typename Arc::StateId state_threshold=kNoStateId)
constexpr uint64 kRightSemiring
Definition: weight.h:115
virtual void AddArc(StateId, const Arc &arc)=0
virtual void SetInputSymbols(const SymbolTable *isyms)=0
virtual Weight Final(StateId) const =0
ExpectationWeight< X1, X2 > Times(const ExpectationWeight< X1, X2 > &w1, const ExpectationWeight< X1, X2 > &w2)
virtual void SetStart(StateId)=0
void Connect(MutableFst< Arc > *fst)
Definition: connect.h:268
constexpr uint64 kFstProperties
Definition: properties.h:301
constexpr int kNoStateId
Definition: fst.h:180
const Arc & Value() const
Definition: fst.h:503
bool SingleShortestPath(const Fst< Arc > &ifst, std::vector< typename Arc::Weight > *distance, const ShortestPathOptions< Arc, Queue, ArcFilter > &opts, typename Arc::StateId *f_parent, std::vector< std::pair< typename Arc::StateId, size_t >> *parent)
void Reverse(const Fst< Arc > &ifst, const std::vector< std::pair< typename Arc::Label, typename Arc::Label >> &parens, std::vector< typename Arc::Label > *assignments, MutableFst< RevArc > *ofst)
Definition: reverse.h:20
virtual uint64 Properties(uint64 mask, bool test) const =0
void SingleShortestPathBacktrace(const Fst< Arc > &ifst, MutableFst< Arc > *ofst, const std::vector< std::pair< typename Arc::StateId, size_t >> &parent, typename Arc::StateId f_parent)
Definition: shortest-path.h:71
#define FSTERROR()
Definition: util.h:35
virtual void SetFinal(StateId, Weight)=0
typename Arc::StateId StateId
Definition: shortest-path.h:28
void Seek(size_t a)
Definition: fst.h:523
constexpr uint64 kSemiring
Definition: weight.h:117
ExpectationWeight< X1, X2 > Plus(const ExpectationWeight< X1, X2 > &w1, const ExpectationWeight< X1, X2 > &w2)
virtual StateId Start() const =0
constexpr float kShortestDelta
void ShortestPath(const Fst< Arc > &ifst, const std::vector< std::pair< typename Arc::Label, typename Arc::Label >> &parens, MutableFst< Arc > *ofst, const PdtShortestPathOptions< Arc, Queue > &opts)
std::integral_constant< bool,(W::Properties()&kPath)!=0 > IsPath
Definition: weight.h:139
constexpr size_t kNoArc
Definition: shortest-path.h:63
ShortestPathOptions(Queue *queue, ArcFilter filter, int32 nshortest=1, bool unique=false, bool has_distance=false, float delta=kShortestDelta, bool first_path=false, Weight weight_threshold=Weight::Zero(), StateId state_threshold=kNoStateId)
Definition: shortest-path.h:46
typename Arc::StateId StateId
bool operator()(S s, W d, W f) const
virtual const SymbolTable * InputSymbols() const =0
constexpr uint64 kPath
Definition: weight.h:126
int32_t int32
Definition: types.h:26
constexpr bool ApproxEqual(const FloatWeightTpl< T > &w1, const FloatWeightTpl< T > &w2, float delta=kDelta)
Definition: float-weight.h:140
constexpr uint64 kError
Definition: properties.h:33
virtual StateId AddState()=0
void SingleShortestTree(const Fst< Arc > &ifst, MutableFst< Arc > *ofst, const std::vector< std::pair< typename Arc::StateId, size_t >> &parent)
virtual void DeleteStates(const std::vector< StateId > &)=0
void ShortestDistance(const Fst< Arc > &fst, std::vector< typename Arc::Weight > *distance, const ShortestDistanceOptions< Arc, Queue, ArcFilter > &opts)
bool operator()(const StateId x, const StateId y) const
virtual void SetOutputSymbols(const SymbolTable *osyms)=0
uint64 ShortestPathProperties(uint64 props, bool tree=false)
Definition: properties.cc:350
virtual StateId NumStates() const =0
ShortestPathCompare(const std::vector< std::pair< StateId, Weight >> &pairs, const std::vector< Weight > &distance, StateId superfinal, float delta)
typename Arc::Weight Weight
Definition: shortest-path.h:29
virtual void SetProperties(uint64 props, uint64 mask)=0
virtual const SymbolTable * OutputSymbols() const =0