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