Difference: TopSortDoc (2 vs. 3)

Revision 32018-04-27 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

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);
Changed:
<
<
| %DOX{namespacefst.html#Topsort[doc]}% |
>
>
|
 |
fsttopsort a.fst out.fst
Changed:
<
<
| |
>
>
|
 

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

META FILEATTACHMENT attachment="topsort1.jpg" attr="" comment="" date="1183423016" name="topsort1.jpg" path="topsort1.jpg" size="15785" stream="topsort1.jpg" user="Main.MichaelRiley" version="1"
META FILEATTACHMENT attachment="topsort2.jpg" attr="" comment="" date="1183423042" name="topsort2.jpg" path="topsort2.jpg" size="15705" stream="topsort2.jpg" user="Main.MichaelRiley" version="1"
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback