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@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>
26using std::vector;
27
28
29#include <fst/dfs-visit.h>
30#include <fst/fst.h>
31#include <fst/statesort.h>
32
33
34namespace fst {
35
36// DFS visitor class to return topological ordering.
37template <class A>
38class 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.
90template <class Arc>
91bool 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