/usr/include/fst/script/shortest-path.h is in libfst-dev 1.6.3-2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 | // 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/arg-packs.h>
#include <fst/script/fst-class.h>
#include <fst/script/shortest-distance.h> // for ShortestDistanceOptions
#include <fst/script/weight-class.h>
namespace fst {
namespace script {
struct ShortestPathOptions : public fst::script::ShortestDistanceOptions {
const int32 nshortest;
const bool unique;
const bool has_distance;
const bool first_path;
const WeightClass &weight_threshold;
const int64 state_threshold;
ShortestPathOptions(QueueType qt, int32 n, bool u, bool hasdist, float d,
bool fp, const WeightClass &w,
int64 s = fst::kNoStateId)
: ShortestDistanceOptions(qt, ANY_ARC_FILTER, kNoStateId, d),
nshortest(n), unique(u), has_distance(hasdist), first_path(fp),
weight_threshold(w), state_threshold(s) {}
};
// 1
using ShortestPathArgs1 =
args::Package<const FstClass &, MutableFstClass *,
std::vector<WeightClass> *, const ShortestPathOptions &>;
template <class Arc>
void ShortestPath(ShortestPathArgs1 *args) {
using StateId = typename Arc::StateId;
using Weight = typename Arc::Weight;
const Fst<Arc> &ifst = *(args->arg1.GetFst<Arc>());
MutableFst<Arc> *ofst = args->arg2->GetMutableFst<Arc>();
const ShortestPathOptions &opts = args->arg4;
using ArcFilter = AnyArcFilter<Arc>;
std::vector<Weight> weights;
const Weight &weight_threshold = *opts.weight_threshold.GetWeight<Weight>();
switch (opts.queue_type) {
case AUTO_QUEUE: {
using Queue = AutoQueue<StateId>;
std::unique_ptr<Queue> queue(
QueueConstructor<Queue, Arc, ArcFilter>::Construct(ifst, &weights));
fst::ShortestPathOptions<Arc, Queue, ArcFilter> spopts(
queue.get(), ArcFilter(), opts.nshortest, opts.unique,
opts.has_distance, opts.delta, opts.first_path, weight_threshold,
opts.state_threshold);
ShortestPath(ifst, ofst, &weights, spopts);
return;
}
case FIFO_QUEUE: {
using Queue = FifoQueue<StateId>;
std::unique_ptr<Queue> queue(
QueueConstructor<Queue, Arc, ArcFilter>::Construct(ifst, &weights));
fst::ShortestPathOptions<Arc, Queue, ArcFilter> spopts(
queue.get(), ArcFilter(), opts.nshortest, opts.unique,
opts.has_distance, opts.delta, opts.first_path, weight_threshold,
opts.state_threshold);
ShortestPath(ifst, ofst, &weights, spopts);
return;
}
case LIFO_QUEUE: {
using Queue = LifoQueue<StateId>;
std::unique_ptr<Queue> queue(
QueueConstructor<Queue, Arc, ArcFilter>::Construct(ifst, &weights));
fst::ShortestPathOptions<Arc, Queue, ArcFilter> spopts(
queue.get(), ArcFilter(), opts.nshortest, opts.unique,
opts.has_distance, opts.delta, opts.first_path, weight_threshold,
opts.state_threshold);
ShortestPath(ifst, ofst, &weights, spopts);
return;
}
case SHORTEST_FIRST_QUEUE: {
using Queue = NaturalShortestFirstQueue<StateId, Weight>;
std::unique_ptr<Queue> queue(
QueueConstructor<Queue, Arc, ArcFilter>::Construct(ifst, &weights));
fst::ShortestPathOptions<Arc, Queue, ArcFilter> spopts(
queue.get(), ArcFilter(), opts.nshortest, opts.unique,
opts.has_distance, opts.delta, opts.first_path, weight_threshold,
opts.state_threshold);
ShortestPath(ifst, ofst, &weights, spopts);
return;
}
case STATE_ORDER_QUEUE: {
using Queue = StateOrderQueue<StateId>;
std::unique_ptr<Queue> queue(
QueueConstructor<Queue, Arc, ArcFilter>::Construct(ifst, &weights));
fst::ShortestPathOptions<Arc, Queue, ArcFilter> spopts(
queue.get(), ArcFilter(), opts.nshortest, opts.unique,
opts.has_distance, opts.delta, opts.first_path, weight_threshold,
opts.state_threshold);
ShortestPath(ifst, ofst, &weights, spopts);
return;
}
case TOP_ORDER_QUEUE: {
using Queue = TopOrderQueue<StateId>;
std::unique_ptr<Queue> queue(
QueueConstructor<Queue, Arc, ArcFilter>::Construct(ifst, &weights));
fst::ShortestPathOptions<Arc, Queue, ArcFilter> spopts(
queue.get(), ArcFilter(), opts.nshortest, opts.unique,
opts.has_distance, opts.delta, opts.first_path, weight_threshold,
opts.state_threshold);
ShortestPath(ifst, ofst, &weights, spopts);
return;
}
default:
FSTERROR() << "Unknown queue type: " << opts.queue_type;
ofst->SetProperties(kError, kError);
}
// Copies the weights back.
args->arg3->resize(weights.size());
for (auto i = 0; i < weights.size(); ++i) {
(*args->arg3)[i] = WeightClass(weights[i]);
}
}
// 2
using ShortestPathArgs2 =
args::Package<const FstClass &, MutableFstClass *, int32, bool, bool,
const WeightClass &, int64>;
template <class Arc>
void ShortestPath(ShortestPathArgs2 *args) {
const Fst<Arc> &ifst = *(args->arg1.GetFst<Arc>());
MutableFst<Arc> *ofst = args->arg2->GetMutableFst<Arc>();
const typename Arc::Weight &weight_threshold =
*args->arg6.GetWeight<typename Arc::Weight>();
ShortestPath(ifst, ofst, args->arg3, args->arg4, args->arg5,
weight_threshold, args->arg7);
}
// 1
void ShortestPath(const FstClass &ifst, MutableFstClass *ofst,
std::vector<WeightClass> *distance,
const ShortestPathOptions &opts);
// 2
void ShortestPath(const FstClass &ifst, MutableFstClass *ofst, int32 n,
bool unique, bool first_path, const WeightClass &weight_threshold,
int64 state_threshold = fst::kNoStateId);
} // namespace script
} // namespace fst
#endif // FST_SCRIPT_SHORTEST_PATH_H_
|