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