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