Topsort

Description

This operation topologically sorts its input if acyclic, modifying it. Otherwise, the input is unchanged. When sorted, all transitions are from lower to higher state IDs.

Usage

template<class Arc> void Topsort(MutableFst<Arc> *fst);
fsttopsort a.fst out.fst

Examples

A:

Topsort of A:

Topsort(&A);
fsttopsort a.fst out.fst

Complexity

Topsort:

• Time: O(V + E)
• Space: O(V + E)
  

where V = # of states and E = # of arcs.

-- MichaelRiley - 02 Jul 2007