1f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// shortest-distance.h 2f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 3f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Licensed under the Apache License, Version 2.0 (the "License"); 4f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// you may not use this file except in compliance with the License. 5f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// You may obtain a copy of the License at 6f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 7f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// http://www.apache.org/licenses/LICENSE-2.0 8f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 9f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Unless required by applicable law or agreed to in writing, software 10f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// distributed under the License is distributed on an "AS IS" BASIS, 11f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// See the License for the specific language governing permissions and 13f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// limitations under the License. 14f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 15f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Copyright 2005-2010 Google, Inc. 16f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Author: allauzen@google.com (Cyril Allauzen) 17f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 18f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// \file 19f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Functions and classes to find shortest distance in an FST. 20f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 21f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#ifndef FST_LIB_SHORTEST_DISTANCE_H__ 22f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#define FST_LIB_SHORTEST_DISTANCE_H__ 23f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 24f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <deque> 255b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkinusing std::deque; 26f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <vector> 27f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing std::vector; 28f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 29f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/arcfilter.h> 30f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/cache.h> 31f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/queue.h> 32f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/reverse.h> 33f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/test-properties.h> 34f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 35f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 36f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonnamespace fst { 37f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 38f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class Arc, class Queue, class ArcFilter> 39f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonstruct ShortestDistanceOptions { 40f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::StateId StateId; 41f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 42f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Queue *state_queue; // Queue discipline used; owned by caller 43f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcFilter arc_filter; // Arc filter (e.g., limit to only epsilon graph) 44f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId source; // If kNoStateId, use the Fst's initial state 45f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson float delta; // Determines the degree of convergence required 46f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool first_path; // For a semiring with the path property (o.w. 47f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // undefined), compute the shortest-distances along 48f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // along the first path to a final state found 49f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // by the algorithm. That path is the shortest-path 50f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // only if the FST has a unique final state (or all 51f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // the final states have the same final weight), the 52f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // queue discipline is shortest-first and all the 53f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // weights in the FST are between One() and Zero() 54f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // according to NaturalLess. 55f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 56f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestDistanceOptions(Queue *q, ArcFilter filt, StateId src = kNoStateId, 57f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson float d = kDelta) 58f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : state_queue(q), arc_filter(filt), source(src), delta(d), 59f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson first_path(false) {} 60f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 61f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 62f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 63f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Computation state of the shortest-distance algorithm. Reusable 64f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// information is maintained across calls to member function 65f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// ShortestDistance(source) when 'retain' is true for improved 66f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// efficiency when calling multiple times from different source states 67f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// (e.g., in epsilon removal). Contrary to usual conventions, 'fst' 68f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// may not be freed before this class. Vector 'distance' should not be 69f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// modified by the user between these calls. 70f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// The Error() method returns true if an error was encountered. 71f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc, class Queue, class ArcFilter> 72f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass ShortestDistanceState { 73f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 74f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::StateId StateId; 75f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::Weight Weight; 76f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 77f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestDistanceState( 78f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const Fst<Arc> &fst, 79f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<Weight> *distance, 80f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const ShortestDistanceOptions<Arc, Queue, ArcFilter> &opts, 81f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool retain) 82f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : fst_(fst), distance_(distance), state_queue_(opts.state_queue), 83f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson arc_filter_(opts.arc_filter), delta_(opts.delta), 84f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson first_path_(opts.first_path), retain_(retain), source_id_(0), 85f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson error_(false) { 86f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson distance_->clear(); 87f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 88f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 89f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ~ShortestDistanceState() {} 90f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 91f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void ShortestDistance(StateId source); 92f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 93f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool Error() const { return error_; } 94f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 95f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 96f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const Fst<Arc> &fst_; 97f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<Weight> *distance_; 98f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Queue *state_queue_; 99f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcFilter arc_filter_; 100f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson float delta_; 101f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool first_path_; 102f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool retain_; // Retain and reuse information across calls 103f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 104f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<Weight> rdistance_; // Relaxation distance. 105f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<bool> enqueued_; // Is state enqueued? 106f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<StateId> sources_; // Source ID for ith state in 'distance_', 107f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // 'rdistance_', and 'enqueued_' if retained. 108f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId source_id_; // Unique ID characterizing each call to SD 109f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 110f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool error_; 111f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 112f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 113f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Compute the shortest distance. If 'source' is kNoStateId, use 114f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// the initial state of the Fst. 115f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class Arc, class Queue, class ArcFilter> 116f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonvoid ShortestDistanceState<Arc, Queue, ArcFilter>::ShortestDistance( 117f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId source) { 118f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (fst_.Start() == kNoStateId) { 119f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (fst_.Properties(kError, false)) error_ = true; 120f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return; 121f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 122f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 123f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!(Weight::Properties() & kRightSemiring)) { 124f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson FSTERROR() << "ShortestDistance: Weight needs to be right distributive: " 125f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson << Weight::Type(); 126f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson error_ = true; 127f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return; 128f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 129f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 130f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (first_path_ && !(Weight::Properties() & kPath)) { 131f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson FSTERROR() << "ShortestDistance: first_path option disallowed when " 132f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson << "Weight does not have the path property: " 133f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson << Weight::Type(); 134f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson error_ = true; 135f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return; 136f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 137f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 138f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson state_queue_->Clear(); 139f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 140f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!retain_) { 141f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson distance_->clear(); 142f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rdistance_.clear(); 143f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson enqueued_.clear(); 144f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 145f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 146f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (source == kNoStateId) 147f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson source = fst_.Start(); 148f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 149f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson while (distance_->size() <= source) { 150f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson distance_->push_back(Weight::Zero()); 151f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rdistance_.push_back(Weight::Zero()); 152f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson enqueued_.push_back(false); 153f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 154f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (retain_) { 155f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson while (sources_.size() <= source) 156f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson sources_.push_back(kNoStateId); 157f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson sources_[source] = source_id_; 158f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 159f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson (*distance_)[source] = Weight::One(); 160f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rdistance_[source] = Weight::One(); 161f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson enqueued_[source] = true; 162f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 163f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson state_queue_->Enqueue(source); 164f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 165f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson while (!state_queue_->Empty()) { 166f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId s = state_queue_->Head(); 167f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson state_queue_->Dequeue(); 168f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson while (distance_->size() <= s) { 169f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson distance_->push_back(Weight::Zero()); 170f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rdistance_.push_back(Weight::Zero()); 171f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson enqueued_.push_back(false); 172f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 173f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (first_path_ && (fst_.Final(s) != Weight::Zero())) 174f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson break; 175f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson enqueued_[s] = false; 176f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight r = rdistance_[s]; 177f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rdistance_[s] = Weight::Zero(); 178f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (ArcIterator< Fst<Arc> > aiter(fst_, s); 179f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson !aiter.Done(); 180f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson aiter.Next()) { 181f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const Arc &arc = aiter.Value(); 182dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin if (!arc_filter_(arc)) 183f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson continue; 184f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson while (distance_->size() <= arc.nextstate) { 185f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson distance_->push_back(Weight::Zero()); 186f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rdistance_.push_back(Weight::Zero()); 187f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson enqueued_.push_back(false); 188f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 189f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (retain_) { 190f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson while (sources_.size() <= arc.nextstate) 191f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson sources_.push_back(kNoStateId); 192f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (sources_[arc.nextstate] != source_id_) { 193f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson (*distance_)[arc.nextstate] = Weight::Zero(); 194f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rdistance_[arc.nextstate] = Weight::Zero(); 195f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson enqueued_[arc.nextstate] = false; 196f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson sources_[arc.nextstate] = source_id_; 197f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 198f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 199f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight &nd = (*distance_)[arc.nextstate]; 200f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight &nr = rdistance_[arc.nextstate]; 201f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight w = Times(r, arc.weight); 202f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!ApproxEqual(nd, Plus(nd, w), delta_)) { 203f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson nd = Plus(nd, w); 204f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson nr = Plus(nr, w); 205f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!nd.Member() || !nr.Member()) { 206f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson error_ = true; 207f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return; 208f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 209f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!enqueued_[arc.nextstate]) { 210f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson state_queue_->Enqueue(arc.nextstate); 211f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson enqueued_[arc.nextstate] = true; 212f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else { 213f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson state_queue_->Update(arc.nextstate); 214f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 215f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 216f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 217f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 218f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ++source_id_; 219f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (fst_.Properties(kError, false)) error_ = true; 220f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 221f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 222f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 223f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Shortest-distance algorithm: this version allows fine control 224f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// via the options argument. See below for a simpler interface. 225f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 226f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// This computes the shortest distance from the 'opts.source' state to 227f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// each visited state S and stores the value in the 'distance' vector. 228f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// An unvisited state S has distance Zero(), which will be stored in 229f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// the 'distance' vector if S is less than the maximum visited state. 230f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// The state queue discipline, arc filter, and convergence delta are 231f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// taken in the options argument. 232f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// The 'distance' vector will contain a unique element for which 233f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Member() is false if an error was encountered. 234f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 235f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// The weights must must be right distributive and k-closed (i.e., 1 + 236f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// x + x^2 + ... + x^(k +1) = 1 + x + x^2 + ... + x^k). 237f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 238f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// The algorithm is from Mohri, "Semiring Framweork and Algorithms for 239f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Shortest-Distance Problems", Journal of Automata, Languages and 240f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Combinatorics 7(3):321-350, 2002. The complexity of algorithm 241f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// depends on the properties of the semiring and the queue discipline 242f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// used. Refer to the paper for more details. 243f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc, class Queue, class ArcFilter> 244f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonvoid ShortestDistance( 245f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const Fst<Arc> &fst, 246f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<typename Arc::Weight> *distance, 247f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const ShortestDistanceOptions<Arc, Queue, ArcFilter> &opts) { 248f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 249f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestDistanceState<Arc, Queue, ArcFilter> 250f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson sd_state(fst, distance, opts, false); 251f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson sd_state.ShortestDistance(opts.source); 252f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (sd_state.Error()) { 253f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson distance->clear(); 254f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson distance->resize(1, Arc::Weight::NoWeight()); 255f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 256f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 257f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 258f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Shortest-distance algorithm: simplified interface. See above for a 259f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// version that allows finer control. 260f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 261f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// If 'reverse' is false, this computes the shortest distance from the 262f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// initial state to each state S and stores the value in the 263f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 'distance' vector. If 'reverse' is true, this computes the shortest 264f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// distance from each state to the final states. An unvisited state S 265f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// has distance Zero(), which will be stored in the 'distance' vector 266f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// if S is less than the maximum visited state. The state queue 267f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// discipline is automatically-selected. 268f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// The 'distance' vector will contain a unique element for which 269f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Member() is false if an error was encountered. 270f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 271f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// The weights must must be right (left) distributive if reverse is 272f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// false (true) and k-closed (i.e., 1 + x + x^2 + ... + x^(k +1) = 1 + 273f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// x + x^2 + ... + x^k). 274f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 275f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// The algorithm is from Mohri, "Semiring Framweork and Algorithms for 276f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Shortest-Distance Problems", Journal of Automata, Languages and 277f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Combinatorics 7(3):321-350, 2002. The complexity of algorithm 278f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// depends on the properties of the semiring and the queue discipline 279f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// used. Refer to the paper for more details. 280f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc> 281f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonvoid ShortestDistance(const Fst<Arc> &fst, 282f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<typename Arc::Weight> *distance, 283f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool reverse = false, 284f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson float delta = kDelta) { 285f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::StateId StateId; 286f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::Weight Weight; 287f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 288f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!reverse) { 289f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson AnyArcFilter<Arc> arc_filter; 290f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson AutoQueue<StateId> state_queue(fst, distance, arc_filter); 291f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestDistanceOptions< Arc, AutoQueue<StateId>, AnyArcFilter<Arc> > 292f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson opts(&state_queue, arc_filter); 293f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson opts.delta = delta; 294f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestDistance(fst, distance, opts); 295f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else { 296f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef ReverseArc<Arc> ReverseArc; 297f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename ReverseArc::Weight ReverseWeight; 298f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson AnyArcFilter<ReverseArc> rarc_filter; 299f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<ReverseArc> rfst; 300f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Reverse(fst, &rfst); 301f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<ReverseWeight> rdistance; 302f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson AutoQueue<StateId> state_queue(rfst, &rdistance, rarc_filter); 303f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestDistanceOptions< ReverseArc, AutoQueue<StateId>, 304f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson AnyArcFilter<ReverseArc> > 305f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ropts(&state_queue, rarc_filter); 306f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ropts.delta = delta; 307f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestDistance(rfst, &rdistance, ropts); 308f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson distance->clear(); 309f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (rdistance.size() == 1 && !rdistance[0].Member()) { 310f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson distance->resize(1, Arc::Weight::NoWeight()); 311f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return; 312f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 313f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson while (distance->size() < rdistance.size() - 1) 314f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson distance->push_back(rdistance[distance->size() + 1].Reverse()); 315f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 316f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 317f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 318f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 319f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Return the sum of the weight of all successful paths in an FST, i.e., 320f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// the shortest-distance from the initial state to the final states. 321f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Returns a weight such that Member() is false if an error was encountered. 322f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class Arc> 323f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontypename Arc::Weight ShortestDistance(const Fst<Arc> &fst, float delta = kDelta) { 324f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::Weight Weight; 325f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::StateId StateId; 326f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<Weight> distance; 327f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (Weight::Properties() & kRightSemiring) { 328f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestDistance(fst, &distance, false, delta); 329f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (distance.size() == 1 && !distance[0].Member()) 330f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return Arc::Weight::NoWeight(); 331f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight sum = Weight::Zero(); 332f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (StateId s = 0; s < distance.size(); ++s) 333f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson sum = Plus(sum, Times(distance[s], fst.Final(s))); 334f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return sum; 335f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else { 336f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestDistance(fst, &distance, true, delta); 337f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId s = fst.Start(); 338f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (distance.size() == 1 && !distance[0].Member()) 339f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return Arc::Weight::NoWeight(); 340f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return s != kNoStateId && s < distance.size() ? 341f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson distance[s] : Weight::Zero(); 342f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 343f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 344f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 345f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 346f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} // namespace fst 347f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 348f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#endif // FST_LIB_SHORTEST_DISTANCE_H__ 349