14a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// shortest-path.h 24a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 34a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Licensed under the Apache License, Version 2.0 (the "License"); 44a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// you may not use this file except in compliance with the License. 54a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// You may obtain a copy of the License at 64a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 74a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// http://www.apache.org/licenses/LICENSE-2.0 84a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 94a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Unless required by applicable law or agreed to in writing, software 104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// distributed under the License is distributed on an "AS IS" BASIS, 114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// See the License for the specific language governing permissions and 134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// limitations under the License. 144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Author: allauzen@cs.nyu.edu (Cyril Allauzen) 164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// \file 184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Functions to find shortest paths in an FST. 194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#ifndef FST_LIB_SHORTEST_PATH_H__ 214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#define FST_LIB_SHORTEST_PATH_H__ 224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include <functional> 244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/cache.h" 264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/queue.h" 274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/shortest-distance.h" 284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/test-properties.h" 294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectnamespace fst { 314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class Arc, class Queue, class ArcFilter> 334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectstruct ShortestPathOptions 344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : public ShortestDistanceOptions<Arc, Queue, ArcFilter> { 354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::StateId StateId; 364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t nshortest; // return n-shortest paths 384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool unique; // only return paths with distinct input strings 394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool has_distance; // distance vector already contains the 404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // shortest distance from the initial state 414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ShortestPathOptions(Queue *q, ArcFilter filt, size_t n = 1, bool u = false, 434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool hasdist = false, float d = kDelta) 444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : ShortestDistanceOptions<Arc, Queue, ArcFilter>(q, filt, kNoStateId, d), 454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project nshortest(n), unique(u), has_distance(hasdist) {} 464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Shortest-path algorithm: normally not called directly; prefer 504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 'ShortestPath' below with n=1. 'ofst' contains the shortest path in 514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 'ifst'. 'distance' returns the shortest distances from the source 524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// state to each state in 'ifst'. 'opts' is used to specify options 534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// such as the queue discipline, the arc filter and delta. 544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The shortest path is the lowest weight path w.r.t. the natural 564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// semiring order. 574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The weights need to be right distributive and have the path (kPath) 594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// property. 604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate<class Arc, class Queue, class ArcFilter> 614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid SingleShortestPath(const Fst<Arc> &ifst, 624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project MutableFst<Arc> *ofst, 634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<typename Arc::Weight> *distance, 644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ShortestPathOptions<Arc, Queue, ArcFilter> &opts) { 654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::StateId StateId; 664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::Weight Weight; 674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ofst->DeleteStates(); 694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ofst->SetInputSymbols(ifst.InputSymbols()); 704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ofst->SetOutputSymbols(ifst.OutputSymbols()); 714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (ifst.Start() == kNoStateId) 734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return; 744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<Weight> rdistance; 764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<bool> enqueued; 774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<StateId> parent; 784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<Arc> arc_parent; 794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Queue *state_queue = opts.state_queue; 814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId source = opts.source == kNoStateId ? ifst.Start() : opts.source; 824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight f_distance = Weight::Zero(); 834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId f_parent = kNoStateId; 844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project distance->clear(); 864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project state_queue->Clear(); 874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (opts.nshortest != 1) 884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LOG(FATAL) << "SingleShortestPath: for nshortest > 1, use ShortestPath" 894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project << " instead"; 904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if ((Weight::Properties() & (kPath | kRightSemiring)) 914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project != (kPath | kRightSemiring)) 924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LOG(FATAL) << "SingleShortestPath: Weight needs to have the path" 934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project << " property and be right distributive: " << Weight::Type(); 944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (distance->size() < source) { 964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project distance->push_back(Weight::Zero()); 974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project enqueued.push_back(false); 984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project parent.push_back(kNoStateId); 994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc_parent.push_back(Arc(kNoLabel, kNoLabel, Weight::Zero(), kNoStateId)); 1004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project distance->push_back(Weight::One()); 1024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project parent.push_back(kNoStateId); 1034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc_parent.push_back(Arc(kNoLabel, kNoLabel, Weight::Zero(), kNoStateId)); 1044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project state_queue->Enqueue(source); 1054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project enqueued.push_back(true); 1064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (!state_queue->Empty()) { 1084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId s = state_queue->Head(); 1094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project state_queue->Dequeue(); 1104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project enqueued[s] = false; 1114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight sd = (*distance)[s]; 1124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (ArcIterator< Fst<Arc> > aiter(ifst, s); 1134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project !aiter.Done(); 1144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project aiter.Next()) { 1154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Arc &arc = aiter.Value(); 1164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (distance->size() <= arc.nextstate) { 1174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project distance->push_back(Weight::Zero()); 1184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project enqueued.push_back(false); 1194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project parent.push_back(kNoStateId); 1204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc_parent.push_back(Arc(kNoLabel, kNoLabel, Weight::Zero(), 1214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project kNoStateId)); 1224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight &nd = (*distance)[arc.nextstate]; 1244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight w = Times(sd, arc.weight); 1254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (nd != Plus(nd, w)) { 1264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project nd = Plus(nd, w); 1274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project parent[arc.nextstate] = s; 1284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc_parent[arc.nextstate] = arc; 1294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!enqueued[arc.nextstate]) { 1304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project state_queue->Enqueue(arc.nextstate); 1314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project enqueued[arc.nextstate] = true; 1324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 1334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project state_queue->Update(arc.nextstate); 1344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (ifst.Final(s) != Weight::Zero()) { 1384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight w = Times(sd, ifst.Final(s)); 1394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (f_distance != Plus(f_distance, w)) { 1404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project f_distance = Plus(f_distance, w); 1414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project f_parent = s; 1424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (*distance)[source] = Weight::One(); 1464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project parent[source] = kNoStateId; 1474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId s_p = kNoStateId, d_p = kNoStateId; 1494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (StateId s = f_parent, d = kNoStateId; 1504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project s != kNoStateId; 1514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project d = s, s = parent[s]) { 1524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project enqueued[s] = true; 1534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project d_p = s_p; 1544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project s_p = ofst->AddState(); 1554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (d == kNoStateId) { 1564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ofst->SetFinal(s_p, ifst.Final(f_parent)); 1574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 1584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc_parent[d].nextstate = d_p; 1594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ofst->AddArc(s_p, arc_parent[d]); 1604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ofst->SetStart(s_p); 1634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 1644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class S, class W> 1674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ShortestPathCompare { 1684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 1694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef S StateId; 1704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef W Weight; 1714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef pair<StateId, Weight> Pair; 1724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ShortestPathCompare(const vector<Pair>& pairs, 1744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const vector<Weight>& distance, 1754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId sfinal, float d) 1764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : pairs_(pairs), distance_(distance), superfinal_(sfinal), delta_(d) {} 1774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool operator()(const StateId x, const StateId y) const { 1794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Pair &px = pairs_[x]; 1804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Pair &py = pairs_[y]; 1814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight wx = Times(distance_[px.first], px.second); 1824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight wy = Times(distance_[py.first], py.second); 1834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Penalize complete paths to ensure correct results with inexact weights. 1844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // This forms a strict weak order so long as ApproxEqual(a, b) => 1854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // ApproxEqual(a, c) for all c s.t. less_(a, c) && less_(c, b). 1864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (px.first == superfinal_ && py.first != superfinal_) { 1874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return less_(wy, wx) || ApproxEqual(wx, wy, delta_); 1884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else if (py.first == superfinal_ && px.first != superfinal_) { 1894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return less_(wy, wx) && !ApproxEqual(wx, wy, delta_); 1904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 1914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return less_(wy, wx); 1924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 1964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const vector<Pair> &pairs_; 1974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const vector<Weight> &distance_; 1984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId superfinal_; 1994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project float delta_; 2004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project NaturalLess<Weight> less_; 2014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 2024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// N-Shortest-path algorithm: this version allow fine control 2054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// via the otpions argument. See below for a simpler interface. 2064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 2074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 'ofst' contains the n-shortest paths in 'ifst'. 'distance' returns 2084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// the shortest distances from the source state to each state in 2094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 'ifst'. 'opts' is used to specify options such as the number of 2104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// paths to return, whether they need to have distinct input 2114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// strings, the queue discipline, the arc filter and the convergence 2124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// delta. 2134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 2144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The n-shortest paths are the n-lowest weight paths w.r.t. the 2154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// natural semiring order. The single path that can be 2164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// read from the ith of at most n transitions leaving the initial 2174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// state of 'ofst' is the ith shortest path. 2184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The weights need to be right distributive and have the path (kPath) 2204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// property. They need to be left distributive as well for nshortest 2214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// > 1. 2224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 2234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The algorithm is from Mohri and Riley, "An Efficient Algorithm for 2244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// the n-best-strings problem", ICSLP 2002. The algorithm relies on 2254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// the shortest-distance algorithm. There are some issues with the 2264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// pseudo-code as written in the paper (viz., line 11). 2274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate<class Arc, class Queue, class ArcFilter> 2284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid ShortestPath(const Fst<Arc> &ifst, MutableFst<Arc> *ofst, 2294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<typename Arc::Weight> *distance, 2304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ShortestPathOptions<Arc, Queue, ArcFilter> &opts) { 2314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::StateId StateId; 2324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::Weight Weight; 2334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef pair<StateId, Weight> Pair; 2344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef ReverseArc<Arc> ReverseArc; 2354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename ReverseArc::Weight ReverseWeight; 2364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t n = opts.nshortest; 2384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (n == 1) { 2404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SingleShortestPath(ifst, ofst, distance, opts); 2414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return; 2424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ofst->DeleteStates(); 2444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ofst->SetInputSymbols(ifst.InputSymbols()); 2454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ofst->SetOutputSymbols(ifst.OutputSymbols()); 2464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (n <= 0) return; 2474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if ((Weight::Properties() & (kPath | kSemiring)) != (kPath | kSemiring)) 2484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LOG(FATAL) << "ShortestPath: n-shortest: Weight needs to have the " 2494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project << "path property and be distributive: " 2504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project << Weight::Type(); 2514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (opts.unique) 2524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LOG(FATAL) << "ShortestPath: n-shortest-string algorithm not " 2534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project << "currently implemented"; 2544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Algorithm works on the reverse of 'fst' : 'rfst' 'distance' is 2564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // the distance to the final state in 'rfst' 'ofst' is built as the 2574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // reverse of the tree of n-shortest path in 'rfst'. 2584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!opts.has_distance) 2604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ShortestDistance(ifst, distance, opts); 2614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project VectorFst<ReverseArc> rfst; 2624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Reverse(ifst, &rfst); 2634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project distance->insert(distance->begin(), Weight::One()); 2644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (distance->size() < rfst.NumStates()) 2654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project distance->push_back(Weight::Zero()); 2664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Each state in 'ofst' corresponds to a path with weight w from the 2694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // initial state of 'rfst' to a state s in 'rfst', that can be 2704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // characterized by a pair (s,w). The vector 'pairs' maps each 2714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // state in 'ofst' to the corresponding pair maps states in OFST to 2724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // the corresponding pair (s,w). 2734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<Pair> pairs; 2744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // 'r[s]', 's' state in 'fst', is the number of states in 'ofst' 2754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // which corresponding pair contains 's' ,i.e. , it is number of 2764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // paths computed so far to 's'. 2774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId superfinal = distance->size(); // superfinal must be handled 2784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project distance->push_back(Weight::One()); // differently when unique=true 2794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ShortestPathCompare<StateId, Weight> 2804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project compare(pairs, *distance, superfinal, opts.delta); 2814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<StateId> heap; 2824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<int> r; 2834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (r.size() < distance->size()) 2844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project r.push_back(0); 2854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ofst->SetStart(ofst->AddState()); 2864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId final = ofst->AddState(); 2874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ofst->SetFinal(final, Weight::One()); 2884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (pairs.size() <= final) 2894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project pairs.push_back(Pair(kNoStateId, Weight::Zero())); 2904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project pairs[final] = Pair(rfst.Start(), Weight::One()); 2914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project heap.push_back(final); 2924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (!heap.empty()) { 2944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project pop_heap(heap.begin(), heap.end(), compare); 2954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId state = heap.back(); 2964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Pair p = pairs[state]; 2974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project heap.pop_back(); 2984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ++r[p.first]; 3004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (p.first == superfinal) 3014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ofst->AddArc(ofst->Start(), Arc(0, 0, Weight::One(), state)); 3024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if ((p.first == superfinal) && (r[p.first] == n)) break; 3034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (r[p.first] > n) continue; 3044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (p.first == superfinal) 3054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project continue; 3064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (ArcIterator< Fst<ReverseArc> > aiter(rfst, p.first); 3084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project !aiter.Done(); 3094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project aiter.Next()) { 3104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const ReverseArc &rarc = aiter.Value(); 3114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Arc arc(rarc.ilabel, rarc.olabel, rarc.weight.Reverse(), rarc.nextstate); 3124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight w = Times(p.second, arc.weight); 3134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId next = ofst->AddState(); 3144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project pairs.push_back(Pair(arc.nextstate, w)); 3154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc.nextstate = state; 3164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ofst->AddArc(next, arc); 3174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project heap.push_back(next); 3184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project push_heap(heap.begin(), heap.end(), compare); 3194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight finalw = rfst.Final(p.first).Reverse(); 3224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (finalw != Weight::Zero()) { 3234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight w = Times(p.second, finalw); 3244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId next = ofst->AddState(); 3254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project pairs.push_back(Pair(superfinal, w)); 3264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ofst->AddArc(next, Arc(0, 0, finalw, state)); 3274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project heap.push_back(next); 3284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project push_heap(heap.begin(), heap.end(), compare); 3294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Connect(ofst); 3324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project distance->erase(distance->begin()); 3334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project distance->pop_back(); 3344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 3354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Shortest-path algorithm: simplified interface. See above for a 3374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// version that allows finer control. 3384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 'ofst' contains the 'n'-shortest paths in 'ifst'. The queue 3404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// discipline is automatically selected. When 'unique' == true, only 3414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// paths with distinct input labels are returned. 3424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 3434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The n-shortest paths are the n-lowest weight paths w.r.t. the 3444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// natural semiring order. The single path that can be read from the 3454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// ith of at most n transitions leaving the initial state of 'ofst' is 3464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// the ith best path. 3474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 3484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The weights need to be right distributive and have the path 3494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// (kPath) property. 3504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate<class Arc> 3514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid ShortestPath(const Fst<Arc> &ifst, MutableFst<Arc> *ofst, 3524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t n = 1, bool unique = false) { 3534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<typename Arc::Weight> distance; 3544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AnyArcFilter<Arc> arc_filter; 3554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AutoQueue<typename Arc::StateId> state_queue(ifst, &distance, arc_filter); 3564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ShortestPathOptions< Arc, AutoQueue<typename Arc::StateId>, 3574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AnyArcFilter<Arc> > opts(&state_queue, arc_filter, n, unique); 3584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ShortestPath(ifst, ofst, &distance, opts); 3594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 3604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} // namespace fst 3624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif // FST_LIB_SHORTEST_PATH_H__ 364