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:

topsort1.jpg

Topsort of A:

topsort2.jpg

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

Topic attachments
I Attachment History Action Size Date Who Comment
JPEGjpg topsort1.jpg r1 manage 15.4 K 2007-07-03 - 00:36 MichaelRiley  
JPEGjpg topsort2.jpg r1 manage 15.3 K 2007-07-03 - 00:37 MichaelRiley  

This topic: FST > WebHome > FstQuickTour > TopSortDoc
Topic revision: r3 - 2018-04-27 - MichaelRiley
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback