14a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// shortest-distance.h 24a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 34a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Licensed under the Apache License, Version 2.0 (the "License"); 44a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// you may not use this file except in compliance with the License. 54a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// You may obtain a copy of the License at 64a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 74a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// http://www.apache.org/licenses/LICENSE-2.0 84a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 94a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Unless required by applicable law or agreed to in writing, software 104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// distributed under the License is distributed on an "AS IS" BASIS, 114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// See the License for the specific language governing permissions and 134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// limitations under the License. 144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Author: allauzen@cs.nyu.edu (Cyril Allauzen) 164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// \file 184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Functions and classes to find shortest distance in an FST. 194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#ifndef FST_LIB_SHORTEST_DISTANCE_H__ 214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#define FST_LIB_SHORTEST_DISTANCE_H__ 224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include <deque> 244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/arcfilter.h" 264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/cache.h" 274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/queue.h" 284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/reverse.h" 294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/test-properties.h" 304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectnamespace fst { 324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class Arc, class Queue, class ArcFilter> 344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectstruct ShortestDistanceOptions { 354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::StateId StateId; 364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Queue *state_queue; // Queue discipline used; owned by caller 384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcFilter arc_filter; // Arc filter (e.g., limit to only epsilon graph) 394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId source; // If kNoStateId, use the Fst's initial state 404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project float delta; // Determines the degree of convergence required 414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ShortestDistanceOptions(Queue *q, ArcFilter filt, StateId src = kNoStateId, 434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project float d = kDelta) 444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : state_queue(q), arc_filter(filt), source(src), delta(d) {} 454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Computation state of the shortest-distance algorithm. Reusable 494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// information is maintained across calls to member function 504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// ShortestDistance(source) when 'retain' is true for improved 514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// efficiency when calling multiple times from different source states 524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// (e.g., in epsilon removal). Vector 'distance' should not be 534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// modified by the user between these calls. 544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate<class Arc, class Queue, class ArcFilter> 554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ShortestDistanceState { 564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::StateId StateId; 584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::Weight Weight; 594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ShortestDistanceState( 614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Fst<Arc> &fst, 624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<Weight> *distance, 634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const ShortestDistanceOptions<Arc, Queue, ArcFilter> &opts, 644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool retain) 654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : fst_(fst.Copy()), distance_(distance), state_queue_(opts.state_queue), 664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc_filter_(opts.arc_filter), 674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delta_(opts.delta), retain_(retain) { 684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project distance_->clear(); 694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ~ShortestDistanceState() { 724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete fst_; 734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void ShortestDistance(StateId source); 764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Fst<Arc> *fst_; 794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<Weight> *distance_; 804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Queue *state_queue_; 814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcFilter arc_filter_; 824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project float delta_; 834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool retain_; // Retain and reuse information across calls 844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<Weight> rdistance_; // Relaxation distance. 864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<bool> enqueued_; // Is state enqueued? 874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<StateId> sources_; // Source state for ith state in 'distance_', 884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // 'rdistance_', and 'enqueued_' if retained. 894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Compute the shortest distance. If 'source' is kNoStateId, use 924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// the initial state of the Fst. 934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class Arc, class Queue, class ArcFilter> 944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid ShortestDistanceState<Arc, Queue, ArcFilter>::ShortestDistance( 954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId source) { 964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (fst_->Start() == kNoStateId) 974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return; 984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!(Weight::Properties() & kRightSemiring)) 1004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LOG(FATAL) << "ShortestDistance: Weight needs to be right distributive: " 1014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project << Weight::Type(); 1024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project state_queue_->Clear(); 1044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!retain_) { 1064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project distance_->clear(); 1074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project rdistance_.clear(); 1084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project enqueued_.clear(); 1094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (source == kNoStateId) 1124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project source = fst_->Start(); 1134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while ((StateId)distance_->size() <= source) { 1154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project distance_->push_back(Weight::Zero()); 1164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project rdistance_.push_back(Weight::Zero()); 1174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project enqueued_.push_back(false); 1184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (retain_) { 1204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while ((StateId)sources_.size() <= source) 1214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project sources_.push_back(kNoStateId); 1224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project sources_[source] = source; 1234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (*distance_)[source] = Weight::One(); 1254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project rdistance_[source] = Weight::One(); 1264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project enqueued_[source] = true; 1274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project state_queue_->Enqueue(source); 1294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (!state_queue_->Empty()) { 1314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId s = state_queue_->Head(); 1324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project state_queue_->Dequeue(); 1334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while ((StateId)distance_->size() <= s) { 1344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project distance_->push_back(Weight::Zero()); 1354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project rdistance_.push_back(Weight::Zero()); 1364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project enqueued_.push_back(false); 1374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project enqueued_[s] = false; 1394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight r = rdistance_[s]; 1404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project rdistance_[s] = Weight::Zero(); 1414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (ArcIterator< Fst<Arc> > aiter(*fst_, s); 1424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project !aiter.Done(); 1434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project aiter.Next()) { 1444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Arc &arc = aiter.Value(); 1454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!arc_filter_(arc) || arc.weight == Weight::Zero()) 1464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project continue; 1474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while ((StateId)distance_->size() <= arc.nextstate) { 1484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project distance_->push_back(Weight::Zero()); 1494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project rdistance_.push_back(Weight::Zero()); 1504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project enqueued_.push_back(false); 1514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (retain_) { 1534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while ((StateId)sources_.size() <= arc.nextstate) 1544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project sources_.push_back(kNoStateId); 1554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (sources_[arc.nextstate] != source) { 1564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (*distance_)[arc.nextstate] = Weight::Zero(); 1574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project rdistance_[arc.nextstate] = Weight::Zero(); 1584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project enqueued_[arc.nextstate] = false; 1594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project sources_[arc.nextstate] = source; 1604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight &nd = (*distance_)[arc.nextstate]; 1634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight &nr = rdistance_[arc.nextstate]; 1644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight w = Times(r, arc.weight); 1654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!ApproxEqual(nd, Plus(nd, w), delta_)) { 1664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project nd = Plus(nd, w); 1674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project nr = Plus(nr, w); 1684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!enqueued_[arc.nextstate]) { 1694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project state_queue_->Enqueue(arc.nextstate); 1704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project enqueued_[arc.nextstate] = true; 1714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 1724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project state_queue_->Update(arc.nextstate); 1734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 1784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Shortest-distance algorithm: this version allows fine control 1814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// via the options argument. See below for a simpler interface. 1824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 1834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// This computes the shortest distance from the 'opts.source' state to 1844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// each visited state S and stores the value in the 'distance' vector. 1854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// An unvisited state S has distance Zero(), which will be stored in 1864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// the 'distance' vector if S is less than the maximum visited state. 1874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The state queue discipline, arc filter, and convergence delta are 1884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// taken in the options argument. 1894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The weights must must be right distributive and k-closed (i.e., 1 + 1914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// x + x^2 + ... + x^(k +1) = 1 + x + x^2 + ... + x^k). 1924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 1934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The algorithm is from Mohri, "Semiring Framweork and Algorithms for 1944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Shortest-Distance Problems", Journal of Automata, Languages and 1954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Combinatorics 7(3):321-350, 2002. The complexity of algorithm 1964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// depends on the properties of the semiring and the queue discipline 1974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// used. Refer to the paper for more details. 1984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate<class Arc, class Queue, class ArcFilter> 1994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid ShortestDistance( 2004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Fst<Arc> &fst, 2014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<typename Arc::Weight> *distance, 2024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const ShortestDistanceOptions<Arc, Queue, ArcFilter> &opts) { 2034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ShortestDistanceState<Arc, Queue, ArcFilter> 2054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project sd_state(fst, distance, opts, false); 2064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project sd_state.ShortestDistance(opts.source); 2074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 2084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Shortest-distance algorithm: simplified interface. See above for a 2104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// version that allows finer control. 2114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 2124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// If 'reverse' is false, this computes the shortest distance from the 2134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// initial state to each state S and stores the value in the 2144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 'distance' vector. If 'reverse' is true, this computes the shortest 2154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// distance from each state to the final states. An unvisited state S 2164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// has distance Zero(), which will be stored in the 'distance' vector 2174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// if S is less than the maximum visited state. The state queue 2184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// discipline is automatically-selected. 2194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 2204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The weights must must be right (left) distributive if reverse is 2214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// false (true) and k-closed (i.e., 1 + x + x^2 + ... + x^(k +1) = 1 + 2224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// x + x^2 + ... + x^k). 2234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 2244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The algorithm is from Mohri, "Semiring Framweork and Algorithms for 2254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Shortest-Distance Problems", Journal of Automata, Languages and 2264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Combinatorics 7(3):321-350, 2002. The complexity of algorithm 2274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// depends on the properties of the semiring and the queue discipline 2284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// used. Refer to the paper for more details. 2294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate<class Arc> 2304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid ShortestDistance(const Fst<Arc> &fst, 2314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<typename Arc::Weight> *distance, 2324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool reverse = false) { 2334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::StateId StateId; 2344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::Weight Weight; 2354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!reverse) { 2374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AnyArcFilter<Arc> arc_filter; 2384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AutoQueue<StateId> state_queue(fst, distance, arc_filter); 2394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ShortestDistanceOptions< Arc, AutoQueue<StateId>, AnyArcFilter<Arc> > 2404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project opts(&state_queue, arc_filter); 2414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ShortestDistance(fst, distance, opts); 2424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 2434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef ReverseArc<Arc> ReverseArc; 2444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename ReverseArc::Weight ReverseWeight; 2454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AnyArcFilter<ReverseArc> rarc_filter; 2464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project VectorFst<ReverseArc> rfst; 2474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Reverse(fst, &rfst); 2484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<ReverseWeight> rdistance; 2494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AutoQueue<StateId> state_queue(rfst, &rdistance, rarc_filter); 2504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ShortestDistanceOptions< ReverseArc, AutoQueue<StateId>, 2514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AnyArcFilter<ReverseArc> > 2524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ropts(&state_queue, rarc_filter); 2534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ShortestDistance(rfst, &rdistance, ropts); 2544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project distance->clear(); 2554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (distance->size() < rdistance.size() - 1) 2564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project distance->push_back(rdistance[distance->size() + 1].Reverse()); 2574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 2594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} // namespace fst 2614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif // FST_LIB_SHORTEST_DISTANCE_H__ 263