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 WhoSorted ascending 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 | WYSIWYG | More topic actions
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