// 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_
|
