1f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// shortest-path.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: riley@google.com (Michael Riley) 17f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 18f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// \file 19f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Functions to find shortest paths in a PDT. 20f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 21f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#ifndef FST_EXTENSIONS_PDT_SHORTEST_PATH_H__ 22f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#define FST_EXTENSIONS_PDT_SHORTEST_PATH_H__ 23f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 24f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/shortest-path.h> 25f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/extensions/pdt/paren.h> 26f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/extensions/pdt/pdt.h> 27f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 28f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <unordered_map> 29f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing std::tr1::unordered_map; 30f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing std::tr1::unordered_multimap; 31f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <tr1/unordered_set> 32f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing std::tr1::unordered_set; 33f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing std::tr1::unordered_multiset; 34f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <stack> 35f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <vector> 36f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing std::vector; 37f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 38f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonnamespace fst { 39f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 40f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class Arc, class Queue> 41f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonstruct PdtShortestPathOptions { 42f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool keep_parentheses; 43f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool path_gc; 44f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 45f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson PdtShortestPathOptions(bool kp = false, bool gc = true) 46f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : keep_parentheses(kp), path_gc(gc) {} 47f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 48f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 49f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 50f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Class to store PDT shortest path results. Stores shortest path 51f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// tree info 'Distance()', Parent(), and ArcParent() information keyed 52f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// on two types: 53f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// (1) By SearchState: This is a usual node in a shortest path tree but: 54f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// (a) is w.r.t a PDT search state - a pair of a PDT state and 55f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// a 'start' state, which is either the PDT start state or 56f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// the destination state of an open parenthesis. 57f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// (b) the Distance() is from this 'start' state to the search state. 58f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// (c) Parent().state is kNoLabel for the 'start' state. 59f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 60f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// (2) By ParenSpec: This connects shortest path trees depending on the 61f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// the parenthesis taken. Given the parenthesis spec: 62f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// (a) the Distance() is from the Parent() 'start' state to the 63f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// parenthesis destination state. 64f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// (b) the ArcParent() is the parenthesis arc. 65f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class Arc> 66f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass PdtShortestPathData { 67f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 68f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const uint8 kFinal; 69f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 70f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::StateId StateId; 71f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::Weight Weight; 72f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::Label Label; 73f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 74f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson struct SearchState { 75f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchState() : state(kNoStateId), start(kNoStateId) {} 76f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 77f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchState(StateId s, StateId t) : state(s), start(t) {} 78f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 79f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool operator==(const SearchState &s) const { 80f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (&s == this) 81f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return true; 82f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return s.state == this->state && s.start == this->start; 83f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 84f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 85f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId state; // PDT state 86f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId start; // PDT paren 'source' state 87f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson }; 88f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 89f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 90f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Specifies paren id, source and dest 'start' states of a paren. 91f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // These are the 'start' states of the respective sub-graphs. 92f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson struct ParenSpec { 93f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ParenSpec() 94f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : paren_id(kNoLabel), src_start(kNoStateId), dest_start(kNoStateId) {} 95f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 96f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ParenSpec(Label id, StateId s, StateId d) 97f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : paren_id(id), src_start(s), dest_start(d) {} 98f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 99f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Label paren_id; // Id of parenthesis 100f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId src_start; // sub-graph 'start' state for paren source. 101f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId dest_start; // sub-graph 'start' state for paren dest. 102f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 103f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool operator==(const ParenSpec &x) const { 104f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (&x == this) 105f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return true; 106f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return x.paren_id == this->paren_id && 107f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson x.src_start == this->src_start && 108f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson x.dest_start == this->dest_start; 109f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 110f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson }; 111f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 112f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson struct SearchData { 113f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchData() : distance(Weight::Zero()), 114f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson parent(kNoStateId, kNoStateId), 115f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson paren_id(kNoLabel), 116f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson flags(0) {} 117f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 118f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight distance; // Distance to this state from PDT 'start' state 119f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchState parent; // Parent state in shortest path tree 120f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson int16 paren_id; // If parent arc has paren, paren ID, o.w. kNoLabel 121f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint8 flags; // First byte reserved for PdtShortestPathData use 122f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson }; 123f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 124f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson PdtShortestPathData(bool gc) 125f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : state_(kNoStateId, kNoStateId), 126f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson paren_(kNoLabel, kNoStateId, kNoStateId), 127f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson gc_(gc), 128f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson nstates_(0), 129f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ngc_(0), 130f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson finished_(false) {} 131f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 132f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ~PdtShortestPathData() { 133f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "opm size: " << paren_map_.size(); 134f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "# of search states: " << nstates_; 135f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (gc_) 136f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "# of GC'd search states: " << ngc_; 137f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 138f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 139f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Clear() { 140f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson search_map_.clear(); 141f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson search_multimap_.clear(); 142f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson paren_map_.clear(); 143f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson state_ = SearchState(kNoStateId, kNoStateId); 144f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson nstates_ = 0; 145f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ngc_ = 0; 146f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 147f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 148f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight Distance(SearchState s) const { 149f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchData *data = GetSearchData(s); 150f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return data->distance; 151f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 152f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 153f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight Distance(const ParenSpec &paren) const { 154f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchData *data = GetSearchData(paren); 155f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return data->distance; 156f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 157f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 158f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchState Parent(SearchState s) const { 159f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchData *data = GetSearchData(s); 160f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return data->parent; 161f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 162f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 163f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchState Parent(const ParenSpec &paren) const { 164f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchData *data = GetSearchData(paren); 165f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return data->parent; 166f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 167f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 168f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Label ParenId(SearchState s) const { 169f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchData *data = GetSearchData(s); 170f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return data->paren_id; 171f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 172f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 173f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint8 Flags(SearchState s) const { 174f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchData *data = GetSearchData(s); 175f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return data->flags; 176f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 177f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 178f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void SetDistance(SearchState s, Weight w) { 179f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchData *data = GetSearchData(s); 180f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson data->distance = w; 181f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 182f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 183f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void SetDistance(const ParenSpec &paren, Weight w) { 184f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchData *data = GetSearchData(paren); 185f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson data->distance = w; 186f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 187f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 188f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void SetParent(SearchState s, SearchState p) { 189f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchData *data = GetSearchData(s); 190f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson data->parent = p; 191f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 192f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 193f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void SetParent(const ParenSpec &paren, SearchState p) { 194f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchData *data = GetSearchData(paren); 195f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson data->parent = p; 196f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 197f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 198f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void SetParenId(SearchState s, Label p) { 199f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (p >= 32768) 200f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson FSTERROR() << "PdtShortestPathData: Paren ID does not fits in an int16"; 201f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchData *data = GetSearchData(s); 202f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson data->paren_id = p; 203f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 204f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 205f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void SetFlags(SearchState s, uint8 f, uint8 mask) { 206f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchData *data = GetSearchData(s); 207f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson data->flags &= ~mask; 208f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson data->flags |= f & mask; 209f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 210f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 211f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void GC(StateId s); 212f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 213f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Finish() { finished_ = true; } 214f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 215f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 216f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const Arc kNoArc; 217f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const size_t kPrime0; 218f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const size_t kPrime1; 219f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const uint8 kInited; 220f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const uint8 kMarked; 221f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 222f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Hash for search state 223f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson struct SearchStateHash { 224f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson size_t operator()(const SearchState &s) const { 225f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return s.state + s.start * kPrime0; 226f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 227f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson }; 228f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 229f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Hash for paren map 230f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson struct ParenHash { 231f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson size_t operator()(const ParenSpec &paren) const { 232f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return paren.paren_id + paren.src_start * kPrime0 + 233f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson paren.dest_start * kPrime1; 234f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 235f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson }; 236f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 237f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef unordered_map<SearchState, SearchData, SearchStateHash> SearchMap; 238f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 239f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef unordered_multimap<StateId, StateId> SearchMultimap; 240f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 241f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Hash map from paren spec to open paren data 242f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef unordered_map<ParenSpec, SearchData, ParenHash> ParenMap; 243f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 244f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchData *GetSearchData(SearchState s) const { 245f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (s == state_) 246f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return state_data_; 247f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (finished_) { 248f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typename SearchMap::iterator it = search_map_.find(s); 249f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (it == search_map_.end()) 250f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return &null_search_data_; 251f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson state_ = s; 252f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return state_data_ = &(it->second); 253f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else { 254f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson state_ = s; 255f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson state_data_ = &search_map_[s]; 256f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!(state_data_->flags & kInited)) { 257f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ++nstates_; 258f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (gc_) 259f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson search_multimap_.insert(make_pair(s.start, s.state)); 260f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson state_data_->flags = kInited; 261f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 262f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return state_data_; 263f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 264f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 265f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 266f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchData *GetSearchData(ParenSpec paren) const { 267f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (paren == paren_) 268f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return paren_data_; 269f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (finished_) { 270f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typename ParenMap::iterator it = paren_map_.find(paren); 271f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (it == paren_map_.end()) 272f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return &null_search_data_; 273f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson paren_ = paren; 274f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return state_data_ = &(it->second); 275f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else { 276f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson paren_ = paren; 277f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return paren_data_ = &paren_map_[paren]; 278f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 279f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 280f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 281f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson mutable SearchMap search_map_; // Maps from search state to data 282f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson mutable SearchMultimap search_multimap_; // Maps from 'start' to subgraph 283f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson mutable ParenMap paren_map_; // Maps paren spec to search data 284f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson mutable SearchState state_; // Last state accessed 285f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson mutable SearchData *state_data_; // Last state data accessed 286f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson mutable ParenSpec paren_; // Last paren spec accessed 287f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson mutable SearchData *paren_data_; // Last paren data accessed 288f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool gc_; // Allow GC? 289f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson mutable size_t nstates_; // Total number of search states 290f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson size_t ngc_; // Number of GC'd search states 291f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson mutable SearchData null_search_data_; // Null search data 292f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool finished_; // Read-only access when true 293f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 294f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DISALLOW_COPY_AND_ASSIGN(PdtShortestPathData); 295f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 296f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 297f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Deletes inaccessible search data from a given 'start' (open paren dest) 298f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// state. Assumes 'final' (close paren source or PDT final) states have 299f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// been flagged 'kFinal'. 300f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc> 301f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonvoid PdtShortestPathData<Arc>::GC(StateId start) { 302f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!gc_) 303f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return; 304f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<StateId> final; 305f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (typename SearchMultimap::iterator mmit = search_multimap_.find(start); 306f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson mmit != search_multimap_.end() && mmit->first == start; 307f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ++mmit) { 308f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchState s(mmit->second, start); 309f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const SearchData &data = search_map_[s]; 310f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (data.flags & kFinal) 311f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson final.push_back(s.state); 312f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 313f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 314f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Mark phase 315f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (size_t i = 0; i < final.size(); ++i) { 316f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchState s(final[i], start); 317f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson while (s.state != kNoLabel) { 318f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchData *sdata = &search_map_[s]; 319f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (sdata->flags & kMarked) 320f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson break; 321f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson sdata->flags |= kMarked; 322f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchState p = sdata->parent; 323f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (p.start != start && p.start != kNoLabel) { // entering sub-subgraph 324f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ParenSpec paren(sdata->paren_id, s.start, p.start); 325f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchData *pdata = &paren_map_[paren]; 326f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson s = pdata->parent; 327f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else { 328f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson s = p; 329f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 330f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 331f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 332f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 333f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Sweep phase 334f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typename SearchMultimap::iterator mmit = search_multimap_.find(start); 335f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson while (mmit != search_multimap_.end() && mmit->first == start) { 336f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchState s(mmit->second, start); 337f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typename SearchMap::iterator mit = search_map_.find(s); 338f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const SearchData &data = mit->second; 339f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!(data.flags & kMarked)) { 340f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson search_map_.erase(mit); 341f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ++ngc_; 342f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 343f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson search_multimap_.erase(mmit++); 344f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 345f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 346f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 347f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc> const Arc PdtShortestPathData<Arc>::kNoArc 348f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson = Arc(kNoLabel, kNoLabel, Weight::Zero(), kNoStateId); 349f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 350f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc> const size_t PdtShortestPathData<Arc>::kPrime0 = 7853; 351f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 352f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc> const size_t PdtShortestPathData<Arc>::kPrime1 = 7867; 353f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 354f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc> const uint8 PdtShortestPathData<Arc>::kInited = 0x01; 355f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 356f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc> const uint8 PdtShortestPathData<Arc>::kFinal = 0x02; 357f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 358f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc> const uint8 PdtShortestPathData<Arc>::kMarked = 0x04; 359f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 360f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 361f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// This computes the single source shortest (balanced) path (SSSP) 362f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// through a weighted PDT that has a bounded stack (i.e. is expandable 363f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// as an FST). It is a generalization of the classic SSSP graph 364f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// algorithm that removes a state s from a queue (defined by a 365f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// user-provided queue type) and relaxes the destination states of 366f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// transitions leaving s. In this PDT version, states that have 367f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// entering open parentheses are treated as source states for a 368f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// sub-graph SSSP problem with the shortest path up to the open 369f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// parenthesis being first saved. When a close parenthesis is then 370f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// encountered any balancing open parenthesis is examined for this 371f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// saved information and multiplied back. In this way, each sub-graph 372f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// is entered only once rather than repeatedly. If every state in the 373f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// input PDT has the property that there is a unique 'start' state for 374f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// it with entering open parentheses, then this algorithm is quite 375f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// straight-forward. In general, this will not be the case, so the 376f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// algorithm (implicitly) creates a new graph where each state is a 377f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// pair of an original state and a possible parenthesis 'start' state 378f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// for that state. 379f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc, class Queue> 380f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass PdtShortestPath { 381f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 382f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::StateId StateId; 383f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::Weight Weight; 384f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::Label Label; 385f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 386f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef PdtShortestPathData<Arc> SpData; 387f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename SpData::SearchState SearchState; 388f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename SpData::ParenSpec ParenSpec; 389f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 390f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename PdtParenReachable<Arc>::SetIterator StateSetIterator; 391f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename PdtBalanceData<Arc>::SetIterator CloseSourceIterator; 392f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 393f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson PdtShortestPath(const Fst<Arc> &ifst, 394f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const vector<pair<Label, Label> > &parens, 395f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const PdtShortestPathOptions<Arc, Queue> &opts) 396f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : kFinal(SpData::kFinal), 397f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ifst_(ifst.Copy()), 398f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson parens_(parens), 399f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson keep_parens_(opts.keep_parentheses), 400f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson start_(ifst.Start()), 401f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson sp_data_(opts.path_gc), 402f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson error_(false) { 403f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 404f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if ((Weight::Properties() & (kPath | kRightSemiring)) 405f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson != (kPath | kRightSemiring)) { 406f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson FSTERROR() << "SingleShortestPath: Weight needs to have the path" 407f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson << " property and be right distributive: " << Weight::Type(); 408f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson error_ = true; 409f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 410f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 411f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (Label i = 0; i < parens.size(); ++i) { 412f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const pair<Label, Label> &p = parens[i]; 413f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson paren_id_map_[p.first] = i; 414f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson paren_id_map_[p.second] = i; 415f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 416f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson }; 417f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 418f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ~PdtShortestPath() { 419f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "# of input states: " << CountStates(*ifst_); 420f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "# of enqueued: " << nenqueued_; 421f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(1) << "cpmm size: " << close_paren_multimap_.size(); 422f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delete ifst_; 423f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 424f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 425f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void ShortestPath(MutableFst<Arc> *ofst) { 426f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Init(ofst); 427f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson GetDistance(start_); 428f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson GetPath(); 429f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson sp_data_.Finish(); 430f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (error_) ofst->SetProperties(kError, kError); 431f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 432f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 433f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const PdtShortestPathData<Arc> &GetShortestPathData() const { 434f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return sp_data_; 435f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 436f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 437f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson PdtBalanceData<Arc> *GetBalanceData() { return &balance_data_; } 438f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 439f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 440f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const Arc kNoArc; 441f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const uint8 kEnqueued; 442f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const uint8 kExpanded; 443f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const uint8 kFinal; 444f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 445f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 446f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Hash multimap from close paren label to an paren arc. 447f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef unordered_multimap<ParenState<Arc>, Arc, 448f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typename ParenState<Arc>::Hash> CloseParenMultimap; 449f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 450f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const CloseParenMultimap &GetCloseParenMultimap() const { 451f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return close_paren_multimap_; 452f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 453f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 454f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 455f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Init(MutableFst<Arc> *ofst); 456f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void GetDistance(StateId start); 457f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void ProcFinal(SearchState s); 458f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void ProcArcs(SearchState s); 459f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void ProcOpenParen(Label paren_id, SearchState s, Arc arc, Weight w); 460f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void ProcCloseParen(Label paren_id, SearchState s, const Arc &arc, Weight w); 461f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void ProcNonParen(SearchState s, const Arc &arc, Weight w); 462f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Relax(SearchState s, SearchState t, Arc arc, Weight w, Label paren_id); 463f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Enqueue(SearchState d); 464f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void GetPath(); 465f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Arc GetPathArc(SearchState s, SearchState p, Label paren_id, bool open); 466f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 467f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Fst<Arc> *ifst_; 468f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson MutableFst<Arc> *ofst_; 469f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const vector<pair<Label, Label> > &parens_; 470f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool keep_parens_; 471f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Queue *state_queue_; // current state queue 472f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId start_; 473f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight f_distance_; 474f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchState f_parent_; 475f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SpData sp_data_; 476f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson unordered_map<Label, Label> paren_id_map_; 477f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CloseParenMultimap close_paren_multimap_; 478f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson PdtBalanceData<Arc> balance_data_; 479f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ssize_t nenqueued_; 480f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool error_; 481f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 482f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DISALLOW_COPY_AND_ASSIGN(PdtShortestPath); 483f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 484f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 485f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc, class Queue> 486f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonvoid PdtShortestPath<Arc, Queue>::Init(MutableFst<Arc> *ofst) { 487f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ofst_ = ofst; 488f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ofst->DeleteStates(); 489f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ofst->SetInputSymbols(ifst_->InputSymbols()); 490f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ofst->SetOutputSymbols(ifst_->OutputSymbols()); 491f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 492f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (ifst_->Start() == kNoStateId) 493f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return; 494f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 495f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson f_distance_ = Weight::Zero(); 496f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson f_parent_ = SearchState(kNoStateId, kNoStateId); 497f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 498f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson sp_data_.Clear(); 499f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson close_paren_multimap_.clear(); 500f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson balance_data_.Clear(); 501f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson nenqueued_ = 0; 502f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 503f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Find open parens per destination state and close parens per source state. 504f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (StateIterator<Fst<Arc> > siter(*ifst_); !siter.Done(); siter.Next()) { 505f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId s = siter.Value(); 506f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (ArcIterator<Fst<Arc> > aiter(*ifst_, s); 507f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson !aiter.Done(); aiter.Next()) { 508f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const Arc &arc = aiter.Value(); 509f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typename unordered_map<Label, Label>::const_iterator pit 510f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson = paren_id_map_.find(arc.ilabel); 511f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (pit != paren_id_map_.end()) { // Is a paren? 512f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Label paren_id = pit->second; 513f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (arc.ilabel == parens_[paren_id].first) { // Open paren 514f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson balance_data_.OpenInsert(paren_id, arc.nextstate); 515f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else { // Close paren 516f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ParenState<Arc> paren_state(paren_id, s); 517f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson close_paren_multimap_.insert(make_pair(paren_state, arc)); 518f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 519f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 520f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 521f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 522f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 523f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 524f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Computes the shortest distance stored in a recursive way. Each 525f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// sub-graph (i.e. different paren 'start' state) begins with weight One(). 526f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc, class Queue> 527f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonvoid PdtShortestPath<Arc, Queue>::GetDistance(StateId start) { 528f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (start == kNoStateId) 529f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return; 530f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 531f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Queue state_queue; 532f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson state_queue_ = &state_queue; 533f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchState q(start, start); 534f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Enqueue(q); 535f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson sp_data_.SetDistance(q, Weight::One()); 536f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 537f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson while (!state_queue_->Empty()) { 538f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId state = state_queue_->Head(); 539f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson state_queue_->Dequeue(); 540f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchState s(state, start); 541f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson sp_data_.SetFlags(s, 0, kEnqueued); 542f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ProcFinal(s); 543f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ProcArcs(s); 544f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson sp_data_.SetFlags(s, kExpanded, kExpanded); 545f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 546f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson balance_data_.FinishInsert(start); 547f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson sp_data_.GC(start); 548f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 549f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 550f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Updates best complete path. 551f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc, class Queue> 552f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonvoid PdtShortestPath<Arc, Queue>::ProcFinal(SearchState s) { 553f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (ifst_->Final(s.state) != Weight::Zero() && s.start == start_) { 554f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight w = Times(sp_data_.Distance(s), 555f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ifst_->Final(s.state)); 556f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (f_distance_ != Plus(f_distance_, w)) { 557f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (f_parent_.state != kNoStateId) 558f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson sp_data_.SetFlags(f_parent_, 0, kFinal); 559f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson sp_data_.SetFlags(s, kFinal, kFinal); 560f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 561f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson f_distance_ = Plus(f_distance_, w); 562f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson f_parent_ = s; 563f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 564f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 565f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 566f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 567f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Processes all arcs leaving the state s. 568f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc, class Queue> 569f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonvoid PdtShortestPath<Arc, Queue>::ProcArcs(SearchState s) { 570f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (ArcIterator< Fst<Arc> > aiter(*ifst_, s.state); 571f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson !aiter.Done(); 572f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson aiter.Next()) { 573f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Arc arc = aiter.Value(); 574f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight w = Times(sp_data_.Distance(s), arc.weight); 575f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 576f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typename unordered_map<Label, Label>::const_iterator pit 577f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson = paren_id_map_.find(arc.ilabel); 578f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (pit != paren_id_map_.end()) { // Is a paren? 579f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Label paren_id = pit->second; 580f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (arc.ilabel == parens_[paren_id].first) 581f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ProcOpenParen(paren_id, s, arc, w); 582f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson else 583f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ProcCloseParen(paren_id, s, arc, w); 584f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else { 585f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ProcNonParen(s, arc, w); 586f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 587f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 588f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 589f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 590f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Saves the shortest path info for reaching this parenthesis 591f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// and starts a new SSSP in the sub-graph pointed to by the parenthesis 592f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// if previously unvisited. Otherwise it finds any previously encountered 593f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// closing parentheses and relaxes them using the recursively stored 594f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// shortest distance to them. 595f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc, class Queue> inline 596f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonvoid PdtShortestPath<Arc, Queue>::ProcOpenParen( 597f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Label paren_id, SearchState s, Arc arc, Weight w) { 598f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 599f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchState d(arc.nextstate, arc.nextstate); 600f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ParenSpec paren(paren_id, s.start, d.start); 601f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight pdist = sp_data_.Distance(paren); 602f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (pdist != Plus(pdist, w)) { 603f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson sp_data_.SetDistance(paren, w); 604f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson sp_data_.SetParent(paren, s); 605f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight dist = sp_data_.Distance(d); 606f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (dist == Weight::Zero()) { 607f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Queue *state_queue = state_queue_; 608f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson GetDistance(d.start); 609f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson state_queue_ = state_queue; 610f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 611f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (CloseSourceIterator set_iter = 612f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson balance_data_.Find(paren_id, arc.nextstate); 613f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson !set_iter.Done(); set_iter.Next()) { 614f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchState cpstate(set_iter.Element(), d.start); 615f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ParenState<Arc> paren_state(paren_id, cpstate.state); 616f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (typename CloseParenMultimap::const_iterator cpit = 617f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson close_paren_multimap_.find(paren_state); 618f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson cpit != close_paren_multimap_.end() && paren_state == cpit->first; 619f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ++cpit) { 620f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const Arc &cparc = cpit->second; 621f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight cpw = Times(w, Times(sp_data_.Distance(cpstate), 622f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson cparc.weight)); 623f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Relax(cpstate, s, cparc, cpw, paren_id); 624f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 625f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 626f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 627f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 628f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 629f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Saves the correspondence between each closing parenthesis and its 630f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// balancing open parenthesis info. Relaxes any close parenthesis 631f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// destination state that has a balancing previously encountered open 632f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// parenthesis. 633f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc, class Queue> inline 634f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonvoid PdtShortestPath<Arc, Queue>::ProcCloseParen( 635f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Label paren_id, SearchState s, const Arc &arc, Weight w) { 636f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ParenState<Arc> paren_state(paren_id, s.start); 637f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!(sp_data_.Flags(s) & kExpanded)) { 638f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson balance_data_.CloseInsert(paren_id, s.start, s.state); 639f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson sp_data_.SetFlags(s, kFinal, kFinal); 640f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 641f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 642f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 643f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// For non-parentheses, classical relaxation. 644f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc, class Queue> inline 645f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonvoid PdtShortestPath<Arc, Queue>::ProcNonParen( 646f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchState s, const Arc &arc, Weight w) { 647f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Relax(s, s, arc, w, kNoLabel); 648f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 649f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 650f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Classical relaxation on the search graph for 'arc' from state 's'. 651f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// State 't' is in the same sub-graph as the nextstate should be (i.e. 652f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// has the same paren 'start'. 653f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc, class Queue> inline 654f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonvoid PdtShortestPath<Arc, Queue>::Relax( 655f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchState s, SearchState t, Arc arc, Weight w, Label paren_id) { 656f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchState d(arc.nextstate, t.start); 657f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight dist = sp_data_.Distance(d); 658f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (dist != Plus(dist, w)) { 659f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson sp_data_.SetParent(d, s); 660f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson sp_data_.SetParenId(d, paren_id); 661f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson sp_data_.SetDistance(d, Plus(dist, w)); 662f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Enqueue(d); 663f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 664f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 665f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 666f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc, class Queue> inline 667f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonvoid PdtShortestPath<Arc, Queue>::Enqueue(SearchState s) { 668f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!(sp_data_.Flags(s) & kEnqueued)) { 669f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson state_queue_->Enqueue(s.state); 670f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson sp_data_.SetFlags(s, kEnqueued, kEnqueued); 671f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ++nenqueued_; 672f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else { 673f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson state_queue_->Update(s.state); 674f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 675f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 676f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 677f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Follows parent pointers to find the shortest path. Uses a stack 678f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// since the shortest distance is stored recursively. 679f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc, class Queue> 680f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonvoid PdtShortestPath<Arc, Queue>::GetPath() { 681f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchState s = f_parent_, d = SearchState(kNoStateId, kNoStateId); 682f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId s_p = kNoStateId, d_p = kNoStateId; 683f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Arc arc(kNoArc); 684f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Label paren_id = kNoLabel; 685f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson stack<ParenSpec> paren_stack; 686f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson while (s.state != kNoStateId) { 687f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson d_p = s_p; 688f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson s_p = ofst_->AddState(); 689f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (d.state == kNoStateId) { 690f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ofst_->SetFinal(s_p, ifst_->Final(f_parent_.state)); 691f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else { 692f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (paren_id != kNoLabel) { // paren? 693f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (arc.ilabel == parens_[paren_id].first) { // open paren 694f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson paren_stack.pop(); 695f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else { // close paren 696f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ParenSpec paren(paren_id, d.start, s.start); 697f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson paren_stack.push(paren); 698f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 699f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!keep_parens_) 700f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson arc.ilabel = arc.olabel = 0; 701f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 702f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson arc.nextstate = d_p; 703f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ofst_->AddArc(s_p, arc); 704f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 705f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson d = s; 706f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson s = sp_data_.Parent(d); 707f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson paren_id = sp_data_.ParenId(d); 708f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (s.state != kNoStateId) { 709f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson arc = GetPathArc(s, d, paren_id, false); 710f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else if (!paren_stack.empty()) { 711f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ParenSpec paren = paren_stack.top(); 712f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson s = sp_data_.Parent(paren); 713f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson paren_id = paren.paren_id; 714f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson arc = GetPathArc(s, d, paren_id, true); 715f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 716f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 717f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ofst_->SetStart(s_p); 718f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ofst_->SetProperties( 719f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestPathProperties(ofst_->Properties(kFstProperties, false)), 720f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson kFstProperties); 721f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 722f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 723f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 724f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Finds transition with least weight between two states with label matching 725f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// paren_id and open/close paren type or a non-paren if kNoLabel. 726f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc, class Queue> 727f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian HodsonArc PdtShortestPath<Arc, Queue>::GetPathArc( 728f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SearchState s, SearchState d, Label paren_id, bool open_paren) { 729f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Arc path_arc = kNoArc; 730f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (ArcIterator< Fst<Arc> > aiter(*ifst_, s.state); 731f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson !aiter.Done(); 732f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson aiter.Next()) { 733f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const Arc &arc = aiter.Value(); 734f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (arc.nextstate != d.state) 735f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson continue; 736f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Label arc_paren_id = kNoLabel; 737f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typename unordered_map<Label, Label>::const_iterator pit 738f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson = paren_id_map_.find(arc.ilabel); 739f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (pit != paren_id_map_.end()) { 740f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson arc_paren_id = pit->second; 741f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool arc_open_paren = arc.ilabel == parens_[arc_paren_id].first; 742f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (arc_open_paren != open_paren) 743f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson continue; 744f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 745f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (arc_paren_id != paren_id) 746f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson continue; 747f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (arc.weight == Plus(arc.weight, path_arc.weight)) 748f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson path_arc = arc; 749f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 750f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (path_arc.nextstate == kNoStateId) { 751f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson FSTERROR() << "PdtShortestPath::GetPathArc failed to find arc"; 752f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson error_ = true; 753f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 754f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return path_arc; 755f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 756f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 757f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc, class Queue> 758f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonconst Arc PdtShortestPath<Arc, Queue>::kNoArc 759f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson = Arc(kNoLabel, kNoLabel, Weight::Zero(), kNoStateId); 760f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 761f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc, class Queue> 762f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonconst uint8 PdtShortestPath<Arc, Queue>::kEnqueued = 0x10; 763f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 764f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc, class Queue> 765f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonconst uint8 PdtShortestPath<Arc, Queue>::kExpanded = 0x20; 766f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 767f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc, class Queue> 768f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonvoid ShortestPath(const Fst<Arc> &ifst, 769f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const vector<pair<typename Arc::Label, 770f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typename Arc::Label> > &parens, 771f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson MutableFst<Arc> *ofst, 772f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const PdtShortestPathOptions<Arc, Queue> &opts) { 773f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson PdtShortestPath<Arc, Queue> psp(ifst, parens, opts); 774f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson psp.ShortestPath(ofst); 775f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 776f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 777f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc> 778f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonvoid ShortestPath(const Fst<Arc> &ifst, 779f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const vector<pair<typename Arc::Label, 780f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typename Arc::Label> > &parens, 781f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson MutableFst<Arc> *ofst) { 782f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef FifoQueue<typename Arc::StateId> Queue; 783f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson PdtShortestPathOptions<Arc, Queue> opts; 784f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson PdtShortestPath<Arc, Queue> psp(ifst, parens, opts); 785f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson psp.ShortestPath(ofst); 786f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 787f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 788f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} // namespace fst 789f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 790f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#endif // FST_EXTENSIONS_PDT_SHORTEST_PATH_H__ 791