14a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// connect.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// 164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// \file 174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Classes and functions to remove unsuccessful paths from an Fst. 184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#ifndef FST_LIB_CONNECT_H__ 204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#define FST_LIB_CONNECT_H__ 214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/mutable-fst.h" 234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectnamespace fst { 254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Finds and returns strongly-connected components, accessible and 274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// coaccessible states and related properties. Uses Tarzan's single 284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// DFS SCC algorithm (see Aho, et al, "Design and Analysis of Computer 294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Algorithms", 189pp). 304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass SccVisitor { 324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef A Arc; 344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::Weight Weight; 354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // scc[i]: strongly-connected component number for state i. 384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // SCC numbers will be in topological order for acyclic input. 394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // access[i]: accessibility of state i. 404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // coaccess[i]: coaccessibility of state i. 414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Any of above can be NULL. 424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // props: related property bits (cyclicity, initial cyclicity, 434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // accessibiliity, coaccessiblity) set/cleared (o.w. unchanged). 444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SccVisitor(vector<StateId> *scc, vector<bool> *access, 454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<bool> *coaccess, uint64 *props) 464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : scc_(scc), access_(access), coaccess_(coaccess), props_(props) {} 474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SccVisitor(uint64 *props) 484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : scc_(0), access_(0), coaccess_(0), props_(props) {} 494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void InitVisit(const Fst<A> &fst) { 514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (scc_) 524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project scc_->clear(); 534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (access_) 544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project access_->clear(); 554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (coaccess_) { 564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project coaccess_->clear(); 574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project coaccess_internal_ = false; 584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project coaccess_ = new vector<bool>; 604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project coaccess_internal_ = true; 614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *props_ |= kAcyclic | kInitialAcyclic | kAccessible | kCoAccessible; 634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *props_ &= ~(kCyclic | kInitialCyclic | kNotAccessible | kNotCoAccessible); 644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst_ = &fst; 654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project start_ = fst.Start(); 664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project nstates_ = 0; 674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project nscc_ = 0; 684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project dfnumber_ = new vector<StateId>; 694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project lowlink_ = new vector<StateId>; 704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project onstack_ = new vector<bool>; 714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project scc_stack_ = new vector<StateId>; 724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool InitState(StateId s, StateId root) { 754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project scc_stack_->push_back(s); 764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while ((StateId)dfnumber_->size() <= s) { 774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (scc_) 784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project scc_->push_back(-1); 794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (access_) 804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project access_->push_back(false); 814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project coaccess_->push_back(false); 824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project dfnumber_->push_back(-1); 834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project lowlink_->push_back(-1); 844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project onstack_->push_back(false); 854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (*dfnumber_)[s] = nstates_; 874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (*lowlink_)[s] = nstates_; 884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (*onstack_)[s] = true; 894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (root == start_) { 904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (access_) 914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (*access_)[s] = true; 924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (access_) 944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (*access_)[s] = false; 954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *props_ |= kNotAccessible; 964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *props_ &= ~kAccessible; 974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ++nstates_; 994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return true; 1004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool TreeArc(StateId s, const A &arc) { return true; } 1034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool BackArc(StateId s, const A &arc) { 1054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId t = arc.nextstate; 1064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if ((*dfnumber_)[t] < (*lowlink_)[s]) 1074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (*lowlink_)[s] = (*dfnumber_)[t]; 1084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if ((*coaccess_)[t]) 1094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (*coaccess_)[s] = true; 1104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *props_ |= kCyclic; 1114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *props_ &= ~kAcyclic; 1124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (arc.nextstate == start_) { 1134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *props_ |= kInitialCyclic; 1144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *props_ &= ~kInitialAcyclic; 1154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return true; 1174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool ForwardOrCrossArc(StateId s, const A &arc) { 1204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId t = arc.nextstate; 1214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if ((*dfnumber_)[t] < (*dfnumber_)[s] /* cross edge */ && 1224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (*onstack_)[t] && (*dfnumber_)[t] < (*lowlink_)[s]) 1234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (*lowlink_)[s] = (*dfnumber_)[t]; 1244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if ((*coaccess_)[t]) 1254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (*coaccess_)[s] = true; 1264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return true; 1274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void FinishState(StateId s, StateId p, const A *) { 1304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (fst_->Final(s) != Weight::Zero()) 1314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (*coaccess_)[s] = true; 1324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if ((*dfnumber_)[s] == (*lowlink_)[s]) { // root of new SCC 1334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool scc_coaccess = false; 1344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t i = scc_stack_->size(); 1354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId t; 1364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project do { 1374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project t = (*scc_stack_)[--i]; 1384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if ((*coaccess_)[t]) 1394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project scc_coaccess = true; 1404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } while (s != t); 1414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project do { 1424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project t = scc_stack_->back(); 1434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (scc_) 1444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (*scc_)[t] = nscc_; 1454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (scc_coaccess) 1464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (*coaccess_)[t] = true; 1474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (*onstack_)[t] = false; 1484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project scc_stack_->pop_back(); 1494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } while (s != t); 1504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!scc_coaccess) { 1514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *props_ |= kNotCoAccessible; 1524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *props_ &= ~kCoAccessible; 1534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ++nscc_; 1554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (p != kNoStateId) { 1574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if ((*coaccess_)[s]) 1584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (*coaccess_)[p] = true; 1594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if ((*lowlink_)[s] < (*lowlink_)[p]) 1604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (*lowlink_)[p] = (*lowlink_)[s]; 1614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void FinishVisit() { 1654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Numbers SCC's in topological order when acyclic. 1664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (scc_) 1674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (StateId i = 0; i < (StateId)scc_->size(); ++i) 1684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (*scc_)[i] = nscc_ - 1 - (*scc_)[i]; 1694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (coaccess_internal_) 1704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete coaccess_; 1714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete dfnumber_; 1724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete lowlink_; 1734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete onstack_; 1744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete scc_stack_; 1754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 1784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<StateId> *scc_; // State's scc number 1794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<bool> *access_; // State's accessibility 1804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<bool> *coaccess_; // State's coaccessibility 1814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 *props_; 1824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Fst<A> *fst_; 1834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId start_; 1844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId nstates_; // State count 1854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId nscc_; // SCC count 1864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool coaccess_internal_; 1874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<StateId> *dfnumber_; // state discovery times 1884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<StateId> *lowlink_; // lowlink[s] == dfnumber[s] => SCC root 1894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<bool> *onstack_; // is a state on the SCC stack 1904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<StateId> *scc_stack_; // SCC stack (w/ random access) 1914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 1924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Trims an FST, removing states and arcs that are not on successful 1954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// paths. This version modifies its input. 1964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 1974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Complexity: 1984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Time: O(V + E) 1994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Space: O(V + E) 2004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// where V = # of states and E = # of arcs. 2014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate<class Arc> 2024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid Connect(MutableFst<Arc> *fst) { 2034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::StateId StateId; 2044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<bool> access; 2064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<bool> coaccess; 2074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 props = 0; 2084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SccVisitor<Arc> scc_visitor(0, &access, &coaccess, &props); 2094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DfsVisit(*fst, &scc_visitor); 2104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<StateId> dstates; 2114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (StateId s = 0; s < (StateId)access.size(); ++s) 2124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!access[s] || !coaccess[s]) 2134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project dstates.push_back(s); 2144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst->DeleteStates(dstates); 2154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst->SetProperties(kAccessible | kCoAccessible, kAccessible | kCoAccessible); 2164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 2174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} // namespace fst 2194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif // FST_LIB_CONNECT_H__ 221