Home | History | Annotate | Download | only in fst 
      1 // topsort.h
      2 
      3 // Licensed under the Apache License, Version 2.0 (the "License");
      4 // you may not use this file except in compliance with the License.
      5 // You may obtain a copy of the License at
      6 //
      7 //     http://www.apache.org/licenses/LICENSE-2.0
      8 //
      9 // Unless required by applicable law or agreed to in writing, software
     10 // distributed under the License is distributed on an "AS IS" BASIS,
     11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     12 // See the License for the specific language governing permissions and
     13 // limitations under the License.
     14 //
     15 // Copyright 2005-2010 Google, Inc.
     16 // Author: riley (at) google.com (Michael Riley)
     17 //
     18 // \file
     19 // Topological sort of FSTs
     20 
     21 #ifndef FST_LIB_TOPSORT_H__
     22 #define FST_LIB_TOPSORT_H__
     23 
     24 #include <algorithm>
     25 #include <vector>
     26 using std::vector;
     27 
     28 
     29 #include <fst/dfs-visit.h>
     30 #include <fst/fst.h>
     31 #include <fst/statesort.h>
     32 
     33 
     34 namespace fst {
     35 
     36 // DFS visitor class to return topological ordering.
     37 template <class A>
     38 class TopOrderVisitor {
     39  public:
     40   typedef A Arc;
     41   typedef typename A::StateId StateId;
     42 
     43   // If acyclic, ORDER[i] gives the topological position of state Id i;
     44   // otherwise unchanged. ACYCLIC will be true iff the FST has
     45   // no cycles.
     46   TopOrderVisitor(vector<StateId> *order, bool *acyclic)
     47       : order_(order), acyclic_(acyclic) {}
     48 
     49   void InitVisit(const Fst<A> &fst) {
     50     finish_ = new vector<StateId>;
     51     *acyclic_ = true;
     52   }
     53 
     54   bool InitState(StateId s, StateId r) { return true; }
     55 
     56   bool TreeArc(StateId s, const A &arc) { return true; }
     57 
     58   bool BackArc(StateId s, const A &arc) { return (*acyclic_ = false); }
     59 
     60   bool ForwardOrCrossArc(StateId s, const A &arc) { return true; }
     61 
     62   void FinishState(StateId s, StateId p, const A *) { finish_->push_back(s); }
     63 
     64   void FinishVisit() {
     65     if (*acyclic_) {
     66       order_->clear();
     67       for (StateId s = 0; s < finish_->size(); ++s)
     68         order_->push_back(kNoStateId);
     69       for (StateId s = 0; s < finish_->size(); ++s)
     70         (*order_)[(*finish_)[finish_->size() - s - 1]] = s;
     71     }
     72     delete finish_;
     73   }
     74 
     75  private:
     76   vector<StateId> *order_;
     77   bool *acyclic_;
     78   vector<StateId> *finish_;  // states in finishing-time order
     79 };
     80 
     81 
     82 // Topologically sorts its input if acyclic, modifying it.  Otherwise,
     83 // the input is unchanged.  When sorted, all transitions are from
     84 // lower to higher state IDs.
     85 //
     86 // Complexity:
     87 // - Time:  O(V + E)
     88 // - Space: O(V + E)
     89 // where V = # of states and E = # of arcs.
     90 template <class Arc>
     91 bool TopSort(MutableFst<Arc> *fst) {
     92   typedef typename Arc::StateId StateId;
     93 
     94   vector<StateId> order;
     95   bool acyclic;
     96 
     97   TopOrderVisitor<Arc> top_order_visitor(&order, &acyclic);
     98   DfsVisit(*fst, &top_order_visitor);
     99 
    100   if (acyclic) {
    101     StateSort(fst, order);
    102     fst->SetProperties(kAcyclic | kInitialAcyclic | kTopSorted,
    103                        kAcyclic | kInitialAcyclic | kTopSorted);
    104   } else {
    105     fst->SetProperties(kCyclic | kNotTopSorted, kCyclic | kNotTopSorted);
    106   }
    107   return acyclic;
    108 }
    109 
    110 }  // namespace fst
    111 
    112 #endif  // FST_LIB_TOPSORT_H__
    113