# 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[]}% |
>
>
|
|
`fsttopsort a.fst out.fst`
Changed:
<
<
| |
>
>
|

## Examples

### `A`:

#### Revision 22017-02-10 - KyleGorman

Line: 1 to 1

 META TOPICPARENT name="FstQuickTour"
Deleted:
<
<

# Topsort

Line: 11 to 10

## Usage

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

#### Revision 12007-07-03 - 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 void Topsort(MutableFst *fst); ``` %DOX{namespacefst.html#Topsort[]}% ```fsttopsort a.fst out.fst ```

## Examples

### `Topsort of A`:

```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" attachment="topsort2.jpg" attr="" comment="" date="1183423042" name="topsort2.jpg" path="topsort2.jpg" size="15705" stream="topsort2.jpg" user="Main.MichaelRiley" version="1"

Copyright © 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