FST  openfst-1.7.1
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 a PDT.
5 
6 #ifndef FST_EXTENSIONS_PDT_SHORTEST_PATH_H_
7 #define FST_EXTENSIONS_PDT_SHORTEST_PATH_H_
8 
9 #include <stack>
10 #include <unordered_map>
11 #include <utility>
12 #include <vector>
13 
14 #include <fst/log.h>
15 
17 #include <fst/extensions/pdt/pdt.h>
18 #include <fst/shortest-path.h>
19 
20 namespace fst {
21 
22 template <class Arc, class Queue>
25  bool path_gc;
26 
27  PdtShortestPathOptions(bool keep_parentheses = false, bool path_gc = true)
28  : keep_parentheses(keep_parentheses), path_gc(path_gc) {}
29 };
30 
31 namespace internal {
32 
33 // Flags for shortest path data.
34 
35 constexpr uint8 kPdtInited = 0x01;
36 constexpr uint8 kPdtFinal = 0x02;
37 constexpr uint8 kPdtMarked = 0x04;
38 
39 // Stores shortest path tree info Distance(), Parent(), and ArcParent()
40 // information keyed on two types:
41 //
42 // 1. SearchState: This is a usual node in a shortest path tree but:
43 // a. is w.r.t a PDT search state (a pair of a PDT state and a "start" state,
44 // either the PDT start state or the destination state of an open
45 // parenthesis).
46 // b. the Distance() is from this "start" state to the search state.
47 // c. Parent().state is kNoLabel for the "start" state.
48 //
49 // 2. ParenSpec: This connects shortest path trees depending on the the
50 // parenthesis taken. Given the parenthesis spec:
51 // a. the Distance() is from the Parent() "start" state to the parenthesis
52 // destination state.
53 // b. The ArcParent() is the parenthesis arc.
54 template <class Arc>
56  public:
57  using Label = typename Arc::Label;
58  using StateId = typename Arc::StateId;
59  using Weight = typename Arc::Weight;
60 
61  struct SearchState {
62  StateId state; // PDT state.
63  StateId start; // PDT paren "start" state.
64 
66  : state(s), start(t) {}
67 
68  bool operator==(const SearchState &other) const {
69  if (&other == this) return true;
70  return other.state == state && other.start == start;
71  }
72  };
73 
74  // Specifies paren ID, source and dest "start" states of a paren. These are
75  // the "start" states of the respective sub-graphs.
76  struct ParenSpec {
77  ParenSpec(Label paren_id = kNoLabel, StateId src_start = kNoStateId,
78  StateId dest_start = kNoStateId)
79  : paren_id(paren_id), src_start(src_start), dest_start(dest_start) {}
80 
82  StateId src_start; // Sub-graph "start" state for paren source.
83  StateId dest_start; // Sub-graph "start" state for paren dest.
84 
85  bool operator==(const ParenSpec &other) const {
86  if (&other == this) return true;
87  return (other.paren_id == paren_id &&
88  other.src_start == other.src_start &&
89  other.dest_start == dest_start);
90  }
91  };
92 
93  struct SearchData {
95  : distance(Weight::Zero()),
96  parent(kNoStateId, kNoStateId),
97  paren_id(kNoLabel),
98  flags(0) {}
99 
100  Weight distance; // Distance to this state from PDT "start" state.
101  SearchState parent; // Parent state in shortest path tree.
102  int16 paren_id; // If parent arc has paren, paren ID (or kNoLabel).
103  uint8 flags; // First byte reserved for PdtShortestPathData use.
104  };
105 
107  : gc_(gc), nstates_(0), ngc_(0), finished_(false) {}
108 
110  VLOG(1) << "opm size: " << paren_map_.size();
111  VLOG(1) << "# of search states: " << nstates_;
112  if (gc_) VLOG(1) << "# of GC'd search states: " << ngc_;
113  }
114 
115  void Clear() {
116  search_map_.clear();
117  search_multimap_.clear();
118  paren_map_.clear();
119  state_ = SearchState(kNoStateId, kNoStateId);
120  nstates_ = 0;
121  ngc_ = 0;
122  }
123 
124  // TODO(kbg): Currently copying SearchState and passing a const reference to
125  // ParenSpec. Benchmark to confirm this is the right thing to do.
126 
127  Weight Distance(SearchState s) const { return GetSearchData(s)->distance; }
128 
129  Weight Distance(const ParenSpec &paren) const {
130  return GetSearchData(paren)->distance;
131  }
132 
133  SearchState Parent(SearchState s) const { return GetSearchData(s)->parent; }
134 
135  SearchState Parent(const ParenSpec &paren) const {
136  return GetSearchData(paren)->parent;
137  }
138 
139  Label ParenId(SearchState s) const { return GetSearchData(s)->paren_id; }
140 
141  uint8 Flags(SearchState s) const { return GetSearchData(s)->flags; }
142 
143  void SetDistance(SearchState s, Weight weight) {
144  GetSearchData(s)->distance = std::move(weight);
145  }
146 
147  void SetDistance(const ParenSpec &paren, Weight weight) {
148  GetSearchData(paren)->distance = std::move(weight);
149  }
150 
151  void SetParent(SearchState s, SearchState p) { GetSearchData(s)->parent = p; }
152 
153  void SetParent(const ParenSpec &paren, SearchState p) {
154  GetSearchData(paren)->parent = p;
155  }
156 
158  if (p >= 32768) {
159  FSTERROR() << "PdtShortestPathData: Paren ID does not fit in an int16";
160  }
161  GetSearchData(s)->paren_id = p;
162  }
163 
164  void SetFlags(SearchState s, uint8 f, uint8 mask) {
165  auto *data = GetSearchData(s);
166  data->flags &= ~mask;
167  data->flags |= f & mask;
168  }
169 
170  void GC(StateId s);
171 
172  void Finish() { finished_ = true; }
173 
174  private:
175  // Hash for search state.
176  struct SearchStateHash {
177  size_t operator()(const SearchState &s) const {
178  static constexpr auto prime = 7853;
179  return s.state + s.start * prime;
180  }
181  };
182 
183  // Hash for paren map.
184  struct ParenHash {
185  size_t operator()(const ParenSpec &paren) const {
186  static constexpr auto prime0 = 7853;
187  static constexpr auto prime1 = 7867;
188  return paren.paren_id + paren.src_start * prime0 +
189  paren.dest_start * prime1;
190  }
191  };
192 
193  using SearchMap =
194  std::unordered_map<SearchState, SearchData, SearchStateHash>;
195 
196  using SearchMultimap = std::unordered_multimap<StateId, StateId>;
197 
198  // Hash map from paren spec to open paren data.
199  using ParenMap = std::unordered_map<ParenSpec, SearchData, ParenHash>;
200 
201  SearchData *GetSearchData(SearchState s) const {
202  if (s == state_) return state_data_;
203  if (finished_) {
204  auto it = search_map_.find(s);
205  if (it == search_map_.end()) return &null_search_data_;
206  state_ = s;
207  return state_data_ = &(it->second);
208  } else {
209  state_ = s;
210  state_data_ = &search_map_[s];
211  if (!(state_data_->flags & kPdtInited)) {
212  ++nstates_;
213  if (gc_) search_multimap_.insert(std::make_pair(s.start, s.state));
214  state_data_->flags = kPdtInited;
215  }
216  return state_data_;
217  }
218  }
219 
220  SearchData *GetSearchData(ParenSpec paren) const {
221  if (paren == paren_) return paren_data_;
222  if (finished_) {
223  auto it = paren_map_.find(paren);
224  if (it == paren_map_.end()) return &null_search_data_;
225  paren_ = paren;
226  return state_data_ = &(it->second);
227  } else {
228  paren_ = paren;
229  return paren_data_ = &paren_map_[paren];
230  }
231  }
232 
233  mutable SearchMap search_map_; // Maps from search state to data.
234  mutable SearchMultimap search_multimap_; // Maps from "start" to subgraph.
235  mutable ParenMap paren_map_; // Maps paren spec to search data.
236  mutable SearchState state_; // Last state accessed.
237  mutable SearchData *state_data_; // Last state data accessed.
238  mutable ParenSpec paren_; // Last paren spec accessed.
239  mutable SearchData *paren_data_; // Last paren data accessed.
240  bool gc_; // Allow GC?
241  mutable size_t nstates_; // Total number of search states.
242  size_t ngc_; // Number of GC'd search states.
243  mutable SearchData null_search_data_; // Null search data.
244  bool finished_; // Read-only access when true.
245 
246  PdtShortestPathData(const PdtShortestPathData &) = delete;
247  PdtShortestPathData &operator=(const PdtShortestPathData &) = delete;
248 };
249 
250 // Deletes inaccessible search data from a given "start" (open paren dest)
251 // state. Assumes "final" (close paren source or PDT final) states have
252 // been flagged kPdtFinal.
253 template <class Arc>
255  if (!gc_) return;
256  std::vector<StateId> finals;
257  for (auto it = search_multimap_.find(start);
258  it != search_multimap_.end() && it->first == start; ++it) {
259  const SearchState s(it->second, start);
260  if (search_map_[s].flags & kPdtFinal) finals.push_back(s.state);
261  }
262  // Mark phase.
263  for (const auto state : finals) {
264  SearchState ss(state, start);
265  while (ss.state != kNoLabel) {
266  auto &sdata = search_map_[ss];
267  if (sdata.flags & kPdtMarked) break;
268  sdata.flags |= kPdtMarked;
269  const auto p = sdata.parent;
270  if (p.start != start && p.start != kNoLabel) { // Entering sub-subgraph.
271  const ParenSpec paren(sdata.paren_id, ss.start, p.start);
272  ss = paren_map_[paren].parent;
273  } else {
274  ss = p;
275  }
276  }
277  }
278  // Sweep phase.
279  auto it = search_multimap_.find(start);
280  while (it != search_multimap_.end() && it->first == start) {
281  const SearchState s(it->second, start);
282  auto mit = search_map_.find(s);
283  const SearchData &data = mit->second;
284  if (!(data.flags & kPdtMarked)) {
285  search_map_.erase(mit);
286  ++ngc_;
287  }
288  search_multimap_.erase(it++);
289  }
290 }
291 
292 } // namespace internal
293 
294 // This computes the single source shortest (balanced) path (SSSP) through a
295 // weighted PDT that has a bounded stack (i.e., is expandable as an FST). It is
296 // a generalization of the classic SSSP graph algorithm that removes a state s
297 // from a queue (defined by a user-provided queue type) and relaxes the
298 // destination states of transitions leaving s. In this PDT version, states that
299 // have entering open parentheses are treated as source states for a sub-graph
300 // SSSP problem with the shortest path up to the open parenthesis being first
301 // saved. When a close parenthesis is then encountered any balancing open
302 // parenthesis is examined for this saved information and multiplied back. In
303 // this way, each sub-graph is entered only once rather than repeatedly. If
304 // every state in the input PDT has the property that there is a unique "start"
305 // state for it with entering open parentheses, then this algorithm is quite
306 // straightforward. In general, this will not be the case, so the algorithm
307 // (implicitly) creates a new graph where each state is a pair of an original
308 // state and a possible parenthesis "start" state for that state.
309 template <class Arc, class Queue>
311  public:
312  using Label = typename Arc::Label;
313  using StateId = typename Arc::StateId;
314  using Weight = typename Arc::Weight;
315 
318  using ParenSpec = typename SpData::ParenSpec;
319  using CloseSourceIterator =
321 
323  const std::vector<std::pair<Label, Label>> &parens,
325  : ifst_(ifst.Copy()),
326  parens_(parens),
327  keep_parens_(opts.keep_parentheses),
328  start_(ifst.Start()),
329  sp_data_(opts.path_gc),
330  error_(false) {
331  // TODO(kbg): Make this a compile-time static_assert once:
332  // 1) All weight properties are made constexpr for all weight types.
333  // 2) We have a pleasant way to "deregister" this oepration for non-path
334  // semirings so an informative error message is produced. The best
335  // solution will probably involve some kind of SFINAE magic.
336  if ((Weight::Properties() & (kPath | kRightSemiring)) !=
337  (kPath | kRightSemiring)) {
338  FSTERROR() << "PdtShortestPath: Weight needs to have the path"
339  << " property and be right distributive: " << Weight::Type();
340  error_ = true;
341  }
342  for (Label i = 0; i < parens.size(); ++i) {
343  const auto &pair = parens[i];
344  paren_map_[pair.first] = i;
345  paren_map_[pair.second] = i;
346  }
347  }
348 
350  VLOG(1) << "# of input states: " << CountStates(*ifst_);
351  VLOG(1) << "# of enqueued: " << nenqueued_;
352  VLOG(1) << "cpmm size: " << close_paren_multimap_.size();
353  }
354 
356  Init(ofst);
357  GetDistance(start_);
358  GetPath();
359  sp_data_.Finish();
360  if (error_) ofst->SetProperties(kError, kError);
361  }
362 
364  return sp_data_;
365  }
366 
367  internal::PdtBalanceData<Arc> *GetBalanceData() { return &balance_data_; }
368 
369  public:
370  // Hash multimap from close paren label to an paren arc.
371  using CloseParenMultimap =
372  std::unordered_multimap<internal::ParenState<Arc>, Arc,
374 
376  return close_paren_multimap_;
377  }
378 
379  private:
380  void Init(MutableFst<Arc> *ofst);
381 
382  void GetDistance(StateId start);
383 
384  void ProcFinal(SearchState s);
385 
386  void ProcArcs(SearchState s);
387 
388  void ProcOpenParen(Label paren_id, SearchState s, StateId nexstate,
389  const Weight &weight);
390 
391  void ProcCloseParen(Label paren_id, SearchState s, const Weight &weight);
392 
393  void ProcNonParen(SearchState s, StateId nextstate, const Weight &weight);
394 
395  void Relax(SearchState s, SearchState t, StateId nextstate,
396  const Weight &weight, Label paren_id);
397 
398  void Enqueue(SearchState d);
399 
400  void GetPath();
401 
402  Arc GetPathArc(SearchState s, SearchState p, Label paren_id, bool open);
403 
404  std::unique_ptr<Fst<Arc>> ifst_;
405  MutableFst<Arc> *ofst_;
406  const std::vector<std::pair<Label, Label>> &parens_;
407  bool keep_parens_;
408  Queue *state_queue_;
409  StateId start_;
410  Weight fdistance_;
411  SearchState f_parent_;
412  SpData sp_data_;
413  std::unordered_map<Label, Label> paren_map_;
414  CloseParenMultimap close_paren_multimap_;
415  internal::PdtBalanceData<Arc> balance_data_;
416  ssize_t nenqueued_;
417  bool error_;
418 
419  static constexpr uint8 kEnqueued = 0x10;
420  static constexpr uint8 kExpanded = 0x20;
421  static constexpr uint8 kFinished = 0x40;
422 
423  static const Arc kNoArc;
424 };
425 
426 template <class Arc, class Queue>
428  ofst_ = ofst;
429  ofst->DeleteStates();
430  ofst->SetInputSymbols(ifst_->InputSymbols());
431  ofst->SetOutputSymbols(ifst_->OutputSymbols());
432  if (ifst_->Start() == kNoStateId) return;
433  fdistance_ = Weight::Zero();
434  f_parent_ = SearchState(kNoStateId, kNoStateId);
435  sp_data_.Clear();
436  close_paren_multimap_.clear();
437  balance_data_.Clear();
438  nenqueued_ = 0;
439  // Finds open parens per destination state and close parens per source state.
440  for (StateIterator<Fst<Arc>> siter(*ifst_); !siter.Done(); siter.Next()) {
441  const auto s = siter.Value();
442  for (ArcIterator<Fst<Arc>> aiter(*ifst_, s); !aiter.Done(); aiter.Next()) {
443  const auto &arc = aiter.Value();
444  const auto it = paren_map_.find(arc.ilabel);
445  if (it != paren_map_.end()) { // Is a paren?
446  const auto paren_id = it->second;
447  if (arc.ilabel == parens_[paren_id].first) { // Open paren.
448  balance_data_.OpenInsert(paren_id, arc.nextstate);
449  } else { // Close paren.
450  const internal::ParenState<Arc> paren_state(paren_id, s);
451  close_paren_multimap_.emplace(paren_state, arc);
452  }
453  }
454  }
455  }
456 }
457 
458 // Computes the shortest distance stored in a recursive way. Each sub-graph
459 // (i.e., different paren "start" state) begins with weight One().
460 template <class Arc, class Queue>
462  if (start == kNoStateId) return;
463  Queue state_queue;
464  state_queue_ = &state_queue;
465  const SearchState q(start, start);
466  Enqueue(q);
467  sp_data_.SetDistance(q, Weight::One());
468  while (!state_queue_->Empty()) {
469  const auto state = state_queue_->Head();
470  state_queue_->Dequeue();
471  const SearchState s(state, start);
472  sp_data_.SetFlags(s, 0, kEnqueued);
473  ProcFinal(s);
474  ProcArcs(s);
475  sp_data_.SetFlags(s, kExpanded, kExpanded);
476  }
477  sp_data_.SetFlags(q, kFinished, kFinished);
478  balance_data_.FinishInsert(start);
479  sp_data_.GC(start);
480 }
481 
482 // Updates best complete path.
483 template <class Arc, class Queue>
485  if (ifst_->Final(s.state) != Weight::Zero() && s.start == start_) {
486  const auto weight = Times(sp_data_.Distance(s), ifst_->Final(s.state));
487  if (fdistance_ != Plus(fdistance_, weight)) {
488  if (f_parent_.state != kNoStateId) {
489  sp_data_.SetFlags(f_parent_, 0, internal::kPdtFinal);
490  }
491  sp_data_.SetFlags(s, internal::kPdtFinal, internal::kPdtFinal);
492  fdistance_ = Plus(fdistance_, weight);
493  f_parent_ = s;
494  }
495  }
496 }
497 
498 // Processes all arcs leaving the state s.
499 template <class Arc, class Queue>
501  for (ArcIterator<Fst<Arc>> aiter(*ifst_, s.state); !aiter.Done();
502  aiter.Next()) {
503  const auto &arc = aiter.Value();
504  const auto weight = Times(sp_data_.Distance(s), arc.weight);
505  const auto it = paren_map_.find(arc.ilabel);
506  if (it != paren_map_.end()) { // Is a paren?
507  const auto paren_id = it->second;
508  if (arc.ilabel == parens_[paren_id].first) {
509  ProcOpenParen(paren_id, s, arc.nextstate, weight);
510  } else {
511  ProcCloseParen(paren_id, s, weight);
512  }
513  } else {
514  ProcNonParen(s, arc.nextstate, weight);
515  }
516  }
517 }
518 
519 // Saves the shortest path info for reaching this parenthesis and starts a new
520 // SSSP in the sub-graph pointed to by the parenthesis if previously unvisited.
521 // Otherwise it finds any previously encountered closing parentheses and relaxes
522 // them using the recursively stored shortest distance to them.
523 template <class Arc, class Queue>
525  SearchState s,
526  StateId nextstate,
527  const Weight &weight) {
528  const SearchState d(nextstate, nextstate);
529  const ParenSpec paren(paren_id, s.start, d.start);
530  const auto pdist = sp_data_.Distance(paren);
531  if (pdist != Plus(pdist, weight)) {
532  sp_data_.SetDistance(paren, weight);
533  sp_data_.SetParent(paren, s);
534  const auto dist = sp_data_.Distance(d);
535  if (dist == Weight::Zero()) {
536  auto *state_queue = state_queue_;
537  GetDistance(d.start);
538  state_queue_ = state_queue;
539  } else if (!(sp_data_.Flags(d) & kFinished)) {
540  FSTERROR()
541  << "PdtShortestPath: open parenthesis recursion: not bounded stack";
542  error_ = true;
543  }
544  for (auto set_iter = balance_data_.Find(paren_id, nextstate);
545  !set_iter.Done(); set_iter.Next()) {
546  const SearchState cpstate(set_iter.Element(), d.start);
547  const internal::ParenState<Arc> paren_state(paren_id, cpstate.state);
548  for (auto cpit = close_paren_multimap_.find(paren_state);
549  cpit != close_paren_multimap_.end() && paren_state == cpit->first;
550  ++cpit) {
551  const auto &cparc = cpit->second;
552  const auto cpw =
553  Times(weight, Times(sp_data_.Distance(cpstate), cparc.weight));
554  Relax(cpstate, s, cparc.nextstate, cpw, paren_id);
555  }
556  }
557  }
558 }
559 
560 // Saves the correspondence between each closing parenthesis and its balancing
561 // open parenthesis info. Relaxes any close parenthesis destination state that
562 // has a balancing previously encountered open parenthesis.
563 template <class Arc, class Queue>
565  SearchState s,
566  const Weight &weight) {
567  const internal::ParenState<Arc> paren_state(paren_id, s.start);
568  if (!(sp_data_.Flags(s) & kExpanded)) {
569  balance_data_.CloseInsert(paren_id, s.start, s.state);
570  sp_data_.SetFlags(s, internal::kPdtFinal, internal::kPdtFinal);
571  }
572 }
573 
574 // Classical relaxation for non-parentheses.
575 template <class Arc, class Queue>
577  StateId nextstate,
578  const Weight &weight) {
579  Relax(s, s, nextstate, weight, kNoLabel);
580 }
581 
582 // Classical relaxation on the search graph for an arc with destination state
583 // nexstate from state s. State t is in the same sub-graph as nextstate (i.e.,
584 // has the same paren "start").
585 template <class Arc, class Queue>
587  StateId nextstate,
588  const Weight &weight,
589  Label paren_id) {
590  const SearchState d(nextstate, t.start);
591  Weight dist = sp_data_.Distance(d);
592  if (dist != Plus(dist, weight)) {
593  sp_data_.SetParent(d, s);
594  sp_data_.SetParenId(d, paren_id);
595  sp_data_.SetDistance(d, Plus(dist, weight));
596  Enqueue(d);
597  }
598 }
599 
600 template <class Arc, class Queue>
602  if (!(sp_data_.Flags(s) & kEnqueued)) {
603  state_queue_->Enqueue(s.state);
604  sp_data_.SetFlags(s, kEnqueued, kEnqueued);
605  ++nenqueued_;
606  } else {
607  state_queue_->Update(s.state);
608  }
609 }
610 
611 // Follows parent pointers to find the shortest path. A stack is used since the
612 // shortest distance is stored recursively.
613 template <class Arc, class Queue>
615  SearchState s = f_parent_;
617  StateId s_p = kNoStateId;
618  StateId d_p = kNoStateId;
619  auto arc = kNoArc;
620  Label paren_id = kNoLabel;
621  std::stack<ParenSpec> paren_stack;
622  while (s.state != kNoStateId) {
623  d_p = s_p;
624  s_p = ofst_->AddState();
625  if (d.state == kNoStateId) {
626  ofst_->SetFinal(s_p, ifst_->Final(f_parent_.state));
627  } else {
628  if (paren_id != kNoLabel) { // Paren?
629  if (arc.ilabel == parens_[paren_id].first) { // Open paren?
630  paren_stack.pop();
631  } else { // Close paren?
632  const ParenSpec paren(paren_id, d.start, s.start);
633  paren_stack.push(paren);
634  }
635  if (!keep_parens_) arc.ilabel = arc.olabel = 0;
636  }
637  arc.nextstate = d_p;
638  ofst_->AddArc(s_p, arc);
639  }
640  d = s;
641  s = sp_data_.Parent(d);
642  paren_id = sp_data_.ParenId(d);
643  if (s.state != kNoStateId) {
644  arc = GetPathArc(s, d, paren_id, false);
645  } else if (!paren_stack.empty()) {
646  const ParenSpec paren = paren_stack.top();
647  s = sp_data_.Parent(paren);
648  paren_id = paren.paren_id;
649  arc = GetPathArc(s, d, paren_id, true);
650  }
651  }
652  ofst_->SetStart(s_p);
653  ofst_->SetProperties(
654  ShortestPathProperties(ofst_->Properties(kFstProperties, false)),
656 }
657 
658 // Finds transition with least weight between two states with label matching
659 // paren_id and open/close paren type or a non-paren if kNoLabel.
660 template <class Arc, class Queue>
662  Label paren_id, bool open_paren) {
663  auto path_arc = kNoArc;
664  for (ArcIterator<Fst<Arc>> aiter(*ifst_, s.state); !aiter.Done();
665  aiter.Next()) {
666  const auto &arc = aiter.Value();
667  if (arc.nextstate != d.state) continue;
668  Label arc_paren_id = kNoLabel;
669  const auto it = paren_map_.find(arc.ilabel);
670  if (it != paren_map_.end()) {
671  arc_paren_id = it->second;
672  bool arc_open_paren = (arc.ilabel == parens_[arc_paren_id].first);
673  if (arc_open_paren != open_paren) continue;
674  }
675  if (arc_paren_id != paren_id) continue;
676  if (arc.weight == Plus(arc.weight, path_arc.weight)) path_arc = arc;
677  }
678  if (path_arc.nextstate == kNoStateId) {
679  FSTERROR() << "PdtShortestPath::GetPathArc: Failed to find arc";
680  error_ = true;
681  }
682  return path_arc;
683 }
684 
685 template <class Arc, class Queue>
687  Weight::Zero(), kNoStateId);
688 
689 // Functional variants.
690 
691 template <class Arc, class Queue>
693  const Fst<Arc> &ifst,
694  const std::vector<std::pair<typename Arc::Label, typename Arc::Label>>
695  &parens,
697  PdtShortestPath<Arc, Queue> psp(ifst, parens, opts);
698  psp.ShortestPath(ofst);
699 }
700 
701 template <class Arc>
703  const Fst<Arc> &ifst,
704  const std::vector<std::pair<typename Arc::Label, typename Arc::Label>>
705  &parens,
706  MutableFst<Arc> *ofst) {
709  PdtShortestPath<Arc, Q> psp(ifst, parens, opts);
710  psp.ShortestPath(ofst);
711 }
712 
713 } // namespace fst
714 
715 #endif // FST_EXTENSIONS_PDT_SHORTEST_PATH_H_
int16_t int16
Definition: types.h:25
bool operator==(const ParenSpec &other) const
Definition: shortest-path.h:85
internal::PdtBalanceData< Arc > * GetBalanceData()
constexpr int kNoLabel
Definition: fst.h:179
SearchState Parent(SearchState s) const
constexpr uint64 kRightSemiring
Definition: weight.h:115
typename Arc::StateId StateId
Definition: shortest-path.h:58
void SetDistance(SearchState s, Weight weight)
SearchState Parent(const ParenSpec &paren) const
virtual void SetInputSymbols(const SymbolTable *isyms)=0
ExpectationWeight< X1, X2 > Times(const ExpectationWeight< X1, X2 > &w1, const ExpectationWeight< X1, X2 > &w2)
ParenSpec(Label paren_id=kNoLabel, StateId src_start=kNoStateId, StateId dest_start=kNoStateId)
Definition: shortest-path.h:77
std::unordered_multimap< internal::ParenState< Arc >, Arc, typename internal::ParenState< Arc >::Hash > CloseParenMultimap
constexpr uint64 kFstProperties
Definition: properties.h:301
constexpr int kNoStateId
Definition: fst.h:180
constexpr uint64 kExpanded
Definition: properties.h:27
void SetParent(SearchState s, SearchState p)
#define FSTERROR()
Definition: util.h:35
SearchState(StateId s=kNoStateId, StateId t=kNoStateId)
Definition: shortest-path.h:65
typename Collection< ssize_t, StateId >::SetIterator SetIterator
Definition: paren.h:317
uint8_t uint8
Definition: types.h:29
PdtShortestPath(const Fst< Arc > &ifst, const std::vector< std::pair< Label, Label >> &parens, const PdtShortestPathOptions< Arc, Queue > &opts)
#define VLOG(level)
Definition: log.h:49
const CloseParenMultimap & GetCloseParenMultimap() const
Weight Distance(const ParenSpec &paren) const
ExpectationWeight< X1, X2 > Plus(const ExpectationWeight< X1, X2 > &w1, const ExpectationWeight< X1, X2 > &w2)
constexpr uint8 kPdtFinal
Definition: shortest-path.h:36
void SetParenId(SearchState s, Label p)
PdtShortestPathOptions(bool keep_parentheses=false, bool path_gc=true)
Definition: shortest-path.h:27
Label ParenId(SearchState s) const
void SetDistance(const ParenSpec &paren, Weight weight)
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:63
void ShortestPath(MutableFst< Arc > *ofst)
Arc::StateId CountStates(const Fst< Arc > &fst)
Definition: expanded-fst.h:154
void SetFlags(SearchState s, uint8 f, uint8 mask)
constexpr uint64 kPath
Definition: weight.h:126
constexpr uint64 kError
Definition: properties.h:33
bool operator==(const SearchState &other) const
Definition: shortest-path.h:68
uint8 Flags(SearchState s) const
virtual void DeleteStates(const std::vector< StateId > &)=0
typename internal::PdtBalanceData< Arc >::SetIterator CloseSourceIterator
virtual void SetOutputSymbols(const SymbolTable *osyms)=0
Weight Distance(SearchState s) const
uint64 ShortestPathProperties(uint64 props, bool tree=false)
Definition: properties.cc:350
const internal::PdtShortestPathData< Arc > & GetShortestPathData() const
constexpr uint8 kPdtMarked
Definition: shortest-path.h:37
void SetParent(const ParenSpec &paren, SearchState p)
constexpr uint8 kPdtInited
Definition: shortest-path.h:35
virtual void SetProperties(uint64 props, uint64 mask)=0