TWiki> FST Web>FstQuickTour>TopSortDoc (revision 1)EditAttach

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);
doc [bad link?]
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  
Edit | Attach | Watch | Print version | History: r3 < r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r1 - 2007-07-03 - MichaelRiley
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2020 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback