Difference: TopSortDoc (1 vs. 3)

Revision 32018-04-27 - MichaelRiley

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

Topsort

Line: 11 to 11
 |
template<class Arc>
void TopSort(MutableFst<Arc> *fst);
Changed:
<
<
| %DOX{namespacefst.html#Topsort[doc]}% |
>
>
|
 |
fsttopsort a.fst out.fst
Changed:
<
<
| |
>
>
|
 

Examples

A:

Revision 22017-02-10 - KyleGorman

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

Topsort

Description

Line: 11 to 10
 

Usage

|
template<class Arc>
Changed:
<
<
void Topsort(MutableFst *fst);
>
>
void TopSort(MutableFst *fst);
 | %DOX{namespacefst.html#Topsort[doc]}% | |
fsttopsort a.fst out.fst

Revision 12007-07-03 - MichaelRiley

Line: 1 to 1
Added:
>
>
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);
%DOX{namespacefst.html#Topsort[doc]}%
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

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