1f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// topsort.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// Topological sort of FSTs 20f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 21f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#ifndef FST_LIB_TOPSORT_H__ 22f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#define FST_LIB_TOPSORT_H__ 23f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 24f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <algorithm> 25f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <vector> 26f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing std::vector; 27f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 28f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 29f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/dfs-visit.h> 30f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/fst.h> 31f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/statesort.h> 32f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 33f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 34f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonnamespace fst { 35f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 36f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// DFS visitor class to return topological ordering. 37f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class A> 38f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass TopOrderVisitor { 39f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 40f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef A Arc; 41f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename A::StateId StateId; 42f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 43f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // If acyclic, ORDER[i] gives the topological position of state Id i; 44f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // otherwise unchanged. ACYCLIC will be true iff the FST has 45f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // no cycles. 46f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson TopOrderVisitor(vector<StateId> *order, bool *acyclic) 47f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : order_(order), acyclic_(acyclic) {} 48f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 49f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void InitVisit(const Fst<A> &fst) { 50f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson finish_ = new vector<StateId>; 51f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson *acyclic_ = true; 52f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 53f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 54f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool InitState(StateId s, StateId r) { return true; } 55f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 56f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool TreeArc(StateId s, const A &arc) { return true; } 57f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 58f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool BackArc(StateId s, const A &arc) { return (*acyclic_ = false); } 59f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 60f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool ForwardOrCrossArc(StateId s, const A &arc) { return true; } 61f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 62f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void FinishState(StateId s, StateId p, const A *) { finish_->push_back(s); } 63f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 64f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void FinishVisit() { 65f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (*acyclic_) { 66f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson order_->clear(); 67f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (StateId s = 0; s < finish_->size(); ++s) 68f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson order_->push_back(kNoStateId); 69f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (StateId s = 0; s < finish_->size(); ++s) 70f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson (*order_)[(*finish_)[finish_->size() - s - 1]] = s; 71f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 72f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delete finish_; 73f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 74f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 75f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 76f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<StateId> *order_; 77f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool *acyclic_; 78f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<StateId> *finish_; // states in finishing-time order 79f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 80f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 81f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 82f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Topologically sorts its input if acyclic, modifying it. Otherwise, 83f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// the input is unchanged. When sorted, all transitions are from 84f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// lower to higher state IDs. 85f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 86f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Complexity: 87f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// - Time: O(V + E) 88f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// - Space: O(V + E) 89f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// where V = # of states and E = # of arcs. 90f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class Arc> 91f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonbool TopSort(MutableFst<Arc> *fst) { 92f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::StateId StateId; 93f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 94f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<StateId> order; 95f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool acyclic; 96f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 97f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson TopOrderVisitor<Arc> top_order_visitor(&order, &acyclic); 98f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DfsVisit(*fst, &top_order_visitor); 99f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 100f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (acyclic) { 101f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateSort(fst, order); 102f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst->SetProperties(kAcyclic | kInitialAcyclic | kTopSorted, 103f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson kAcyclic | kInitialAcyclic | kTopSorted); 104f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else { 105f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst->SetProperties(kCyclic | kNotTopSorted, kCyclic | kNotTopSorted); 106f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 107f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return acyclic; 108f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 109f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 110f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} // namespace fst 111f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 112f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#endif // FST_LIB_TOPSORT_H__ 113