1 files changed, 112 insertions, 0 deletions
diff --git a/src/include/fst/topsort.h b/src/include/fst/topsort.h
new file mode 100644
index 0000000..53735e5
--- /dev/null
+++ b/src/include/fst/topsort.h
@@ -0,0 +1,112 @@
+// topsort.h
+
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+// Copyright 2005-2010 Google, Inc.
+// Author: riley@google.com (Michael Riley)
+//
+// \file
+// Topological sort of FSTs
+
+#ifndef FST_LIB_TOPSORT_H__
+#define FST_LIB_TOPSORT_H__
+
+#include <algorithm>
+#include <vector>
+using std::vector;
+
+
+#include <fst/dfs-visit.h>
+#include <fst/fst.h>
+#include <fst/statesort.h>
+
+
+namespace fst {
+
+// DFS visitor class to return topological ordering.
+template <class A>
+class TopOrderVisitor {
+ public:
+  typedef A Arc;
+  typedef typename A::StateId StateId;
+
+  // If acyclic, ORDER[i] gives the topological position of state Id i;
+  // otherwise unchanged. ACYCLIC will be true iff the FST has
+  // no cycles.
+  TopOrderVisitor(vector<StateId> *order, bool *acyclic)
+      : order_(order), acyclic_(acyclic) {}
+
+  void InitVisit(const Fst<A> &fst) {
+    finish_ = new vector<StateId>;
+    *acyclic_ = true;
+  }
+
+  bool InitState(StateId s, StateId r) { return true; }
+
+  bool TreeArc(StateId s, const A &arc) { return true; }
+
+  bool BackArc(StateId s, const A &arc) { return (*acyclic_ = false); }
+
+  bool ForwardOrCrossArc(StateId s, const A &arc) { return true; }
+
+  void FinishState(StateId s, StateId p, const A *) { finish_->push_back(s); }
+
+  void FinishVisit() {
+    if (*acyclic_) {
+      order_->clear();
+      for (StateId s = 0; s < finish_->size(); ++s)
+        order_->push_back(kNoStateId);
+      for (StateId s = 0; s < finish_->size(); ++s)
+        (*order_)[(*finish_)[finish_->size() - s - 1]] = s;
+    }
+    delete finish_;
+  }
+
+ private:
+  vector<StateId> *order_;
+  bool *acyclic_;
+  vector<StateId> *finish_;  // states in finishing-time order
+};
+
+
+// Topologically sorts its input if acyclic, modifying it.  Otherwise,
+// the input is unchanged.  When sorted, all transitions are from
+// lower to higher state IDs.
+//
+// Complexity:
+// - Time:  O(V + E)
+// - Space: O(V + E)
+// where V = # of states and E = # of arcs.
+template <class Arc>
+bool TopSort(MutableFst<Arc> *fst) {
+  typedef typename Arc::StateId StateId;
+
+  vector<StateId> order;
+  bool acyclic;
+
+  TopOrderVisitor<Arc> top_order_visitor(&order, &acyclic);
+  DfsVisit(*fst, &top_order_visitor);
+
+  if (acyclic) {
+    StateSort(fst, order);
+    fst->SetProperties(kAcyclic | kInitialAcyclic | kTopSorted,
+                       kAcyclic | kInitialAcyclic | kTopSorted);
+  } else {
+    fst->SetProperties(kCyclic | kNotTopSorted, kCyclic | kNotTopSorted);
+  }
+  return acyclic;
+}
+
+}  // namespace fst
+
+#endif  // FST_LIB_TOPSORT_H__