Lines Matching refs:distance
1 // shortest-distance.h
19 // Functions and classes to find shortest distance in an FST.
62 // Computation state of the shortest-distance algorithm. Reusable
67 // may not be freed before this class. Vector 'distance' should not be
78 vector<Weight> *distance,
81 : fst_(fst), distance_(distance), state_queue_(opts.state_queue),
103 vector<Weight> rdistance_; // Relaxation distance.
112 // Compute the shortest distance. If 'source' is kNoStateId, use
222 // Shortest-distance algorithm: this version allows fine control
225 // This computes the shortest distance from the 'opts.source' state to
226 // each visited state S and stores the value in the 'distance' vector.
227 // An unvisited state S has distance Zero(), which will be stored in
228 // the 'distance' vector if S is less than the maximum visited state.
231 // The 'distance' vector will contain a unique element for which
238 // Shortest-Distance Problems", Journal of Automata, Languages and
245 vector<typename Arc::Weight> *distance,
249 sd_state(fst, distance, opts, false);
252 distance->clear();
253 distance->resize(1, Arc::Weight::NoWeight());
257 // Shortest-distance algorithm: simplified interface. See above for a
260 // If 'reverse' is false, this computes the shortest distance from the
262 // 'distance' vector. If 'reverse' is true, this computes the shortest
263 // distance from each state to the final states. An unvisited state S
264 // has distance Zero(), which will be stored in the 'distance' vector
267 // The 'distance' vector will contain a unique element for which
275 // Shortest-Distance Problems", Journal of Automata, Languages and
281 vector<typename Arc::Weight> *distance,
289 AutoQueue<StateId> state_queue(fst, distance, arc_filter);
293 ShortestDistance(fst, distance, opts);
307 distance->clear();
309 distance->resize(1, Arc::Weight::NoWeight());
312 while (distance->size() < rdistance.size() - 1)
313 distance->push_back(rdistance[distance->size() + 1].Reverse());
319 // the shortest-distance from the initial state to the final states.
325 vector<Weight> distance;
327 ShortestDistance(fst, &distance, false, delta);
328 if (distance.size() == 1 && !distance[0].Member())
331 for (StateId s = 0; s < distance.size(); ++s)
332 sum = Plus(sum, Times(distance[s], fst.Final(s)));
335 ShortestDistance(fst, &distance, true, delta);
337 if (distance.size() == 1 && !distance[0].Member())
339 return s != kNoStateId && s < distance.size() ?
340 distance[s] : Weight::Zero();
