Cross Reference: /external/openfst/src/include/fst/shortest-distance.h

Lines Matching refs:distance
1 // shortest-distance.h
19 // Functions and classes to find shortest distance in an FST.
63 // Computation state of the shortest-distance algorithm. Reusable
68 // may not be freed before this class. Vector 'distance' should not be
79       vector<Weight> *distance,
82       : fst_(fst), distance_(distance), state_queue_(opts.state_queue),
104   vector<Weight> rdistance_;  // Relaxation distance.
113 // Compute the shortest distance. If 'source' is kNoStateId, use
223 // Shortest-distance algorithm: this version allows fine control
226 // This computes the shortest distance from the 'opts.source' state to
227 // each visited state S and stores the value in the 'distance' vector.
228 // An unvisited state S has distance Zero(), which will be stored in
229 // the 'distance' vector if S is less than the maximum visited state.
232 // The 'distance' vector will contain a unique element for which
246     vector<typename Arc::Weight> *distance,
250     sd_state(fst, distance, opts, false);
253     distance->clear();
254     distance->resize(1, Arc::Weight::NoWeight());
258 // Shortest-distance algorithm: simplified interface. See above for a
261 // If 'reverse' is false, this computes the shortest distance from the
263 // 'distance' vector. If 'reverse' is true, this computes the shortest
264 // distance from each state to the final states.  An unvisited state S
265 // has distance Zero(), which will be stored in the 'distance' vector
268 // The 'distance' vector will contain a unique element for which
282                       vector<typename Arc::Weight> *distance,
290     AutoQueue<StateId> state_queue(fst, distance, arc_filter);
294     ShortestDistance(fst, distance, opts);
308     distance->clear();
310       distance->resize(1, Arc::Weight::NoWeight());
313     while (distance->size() < rdistance.size() - 1)
314       distance->push_back(rdistance[distance->size() + 1].Reverse());
320 // the shortest-distance from the initial state to the final states.
326   vector<Weight> distance;
328     ShortestDistance(fst, &distance, false, delta);
329     if (distance.size() == 1 && !distance[0].Member())
332     for (StateId s = 0; s < distance.size(); ++s)
333       sum = Plus(sum, Times(distance[s], fst.Final(s)));
336     ShortestDistance(fst, &distance, true, delta);
338     if (distance.size() == 1 && !distance[0].Member())
340     return s != kNoStateId && s < distance.size() ?
341         distance[s] : Weight::Zero();