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