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 #ifndef FST_SCRIPT_SHORTEST_PATH_H_
5 #define FST_SCRIPT_SHORTEST_PATH_H_
6 
7 #include <memory>
8 #include <vector>
9 
10 #include <fst/shortest-path.h>
11 #include <fst/script/fst-class.h>
14 
15 namespace fst {
16 namespace script {
17 
18 // Slightly simplified interface: `has_distance` and `first_path` are disabled.
19 
22  const bool unique;
25 
26  ShortestPathOptions(QueueType queue_type, int32 nshortest, bool unique,
27  float delta, const WeightClass &weight_threshold,
28  int64 state_threshold = kNoStateId)
29  : ShortestDistanceOptions(queue_type, ANY_ARC_FILTER, kNoStateId, delta),
30  nshortest(nshortest),
31  unique(unique),
32  weight_threshold(weight_threshold),
33  state_threshold(state_threshold) {}
34 };
35 
36 namespace internal {
37 
38 // Code to implement switching on queue types.
39 
40 template <class Arc, class Queue>
41 void ShortestPath(const Fst<Arc> &ifst, MutableFst<Arc> *ofst,
42  std::vector<typename Arc::Weight> *distance,
43  const ShortestPathOptions &opts) {
44  using ArcFilter = AnyArcFilter<Arc>;
45  using Weight = typename Arc::Weight;
46  const std::unique_ptr<Queue> queue(
49  queue.get(), ArcFilter(), opts.nshortest, opts.unique,
50  /* has_distance=*/false, opts.delta, /* first_path=*/false,
51  *opts.weight_threshold.GetWeight<Weight>(), opts.state_threshold);
52  ShortestPath(ifst, ofst, distance, sopts);
53 }
54 
55 template <class Arc>
56 void ShortestPath(const Fst<Arc> &ifst, MutableFst<Arc> *ofst,
57  const ShortestPathOptions &opts) {
58  using StateId = typename Arc::StateId;
59  using Weight = typename Arc::Weight;
60  std::vector<Weight> distance;
61  switch (opts.queue_type) {
62  case AUTO_QUEUE: {
63  ShortestPath<Arc, AutoQueue<StateId>>(ifst, ofst, &distance, opts);
64  return;
65  }
66  case FIFO_QUEUE: {
67  ShortestPath<Arc, FifoQueue<StateId>>(ifst, ofst, &distance, opts);
68  return;
69  }
70  case LIFO_QUEUE: {
71  ShortestPath<Arc, LifoQueue<StateId>>(ifst, ofst, &distance, opts);
72  return;
73  }
74  case SHORTEST_FIRST_QUEUE: {
75  ShortestPath<Arc, NaturalShortestFirstQueue<StateId, Weight>>(ifst, ofst,
76  &distance,
77  opts);
78  return;
79  }
80  case STATE_ORDER_QUEUE: {
81  ShortestPath<Arc, StateOrderQueue<StateId>>(ifst, ofst, &distance, opts);
82  return;
83  }
84  case TOP_ORDER_QUEUE: {
85  ShortestPath<Arc, TopOrderQueue<StateId>>(ifst, ofst, &distance, opts);
86  return;
87  }
88  default: {
89  FSTERROR() << "ShortestPath: Unknown queue type: "
90  << opts.queue_type;
91  ofst->SetProperties(kError, kError);
92  return;
93  }
94  }
95 }
96 
97 } // namespace internal
98 
99 using ShortestPathArgs = std::tuple<const FstClass &, MutableFstClass *,
101 
102 template <class Arc>
104  const Fst<Arc> &ifst = *(std::get<0>(*args).GetFst<Arc>());
105  MutableFst<Arc> *ofst = std::get<1>(*args)->GetMutableFst<Arc>();
106  const ShortestPathOptions &opts = std::get<2>(*args);
107  internal::ShortestPath(ifst, ofst, opts);
108 }
109 
110 void ShortestPath(const FstClass &ifst, MutableFstClass *ofst,
111  const ShortestPathOptions &opts);
112 
113 } // namespace script
114 } // namespace fst
115 
116 #endif // FST_SCRIPT_SHORTEST_PATH_H_
ShortestPathOptions(QueueType queue_type, int32 nshortest, bool unique, float delta, const WeightClass &weight_threshold, int64 state_threshold=kNoStateId)
Definition: shortest-path.h:26
QueueType
Definition: queue.h:56
void ShortestPath(ShortestPathArgs *args)
constexpr int kNoStateId
Definition: fst.h:180
int64_t int64
Definition: types.h:27
#define FSTERROR()
Definition: util.h:35
const WeightClass & weight_threshold
Definition: shortest-path.h:23
void ShortestPath(const Fst< Arc > &ifst, MutableFst< Arc > *ofst, std::vector< typename Arc::Weight > *distance, const ShortestPathOptions &opts)
Definition: shortest-path.h:41
std::tuple< const FstClass &, MutableFstClass *, const ShortestPathOptions & > ShortestPathArgs
const W * GetWeight() const
Definition: weight-class.h:133
int32_t int32
Definition: types.h:26
constexpr uint64 kError
Definition: properties.h:33
virtual void SetProperties(uint64 props, uint64 mask)=0