Epsilon Cycle Detection Algorithm

Recently, there was a question on the OpenFst forum asking how to detect epsilon cycles in finite state transducer (Fst). One solution is to start a depth first search (DFS) from every state and only traverse the epsilon transitions. Fortunately, OpenFst already has this implemented using a combination of the DfsVisit and TopOrderVisitor. The TopOrderVisitor takes a boolean reference parameter to indicate if the Fst is acyclic and if a topological ordering is possible. We can restrict the DFS to the epsilon input graph using the InputEpsilonArcFilter filter. The DfsVisit will create a DFS forest and will automatically start the DFS from any state hasn't been visited yet.

template<class Arc>
  bool HasInputEpsilonCycle(const Fst<Arc>& fst) {
  vector<typename Arc::StateId> order;
  bool acyclic = false;
  TopOrderVisitor<Arc> top_order_visitor(&order, &acyclic);
  DfsVisit(fst, &top_order_visitor, InputEpsilonArcFilter<Arc>());
  return !acyclic;
}