Difference: ShortestPathDoc (1 vs. 11)

Revision 112018-04-27 - MichaelRiley

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

ShortestPath

Line: 16 to 16
 |
template<class Arc>
void ShortestPath(const Fst<Arc> &ifst, MutableFst<Arc> *ofst, size_t n = 1);
Changed:
<
<
| %DOX{namespacefst.html#ShortestPath[doc]}% |
>
>
|
 |
fstshortestpath [--opts] a.fst out.fst
    --nshortest: type = int64, default = 1
      Return N-shortest paths
    --unique: default = false
      Return only distinct strings (NB: must be acceptor; epsilons treated as regular symbols)
Changed:
<
<
| |
>
>
|
 

Examples

Revision 102014-04-23 - MichaelRiley

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

ShortestPath

Line: 58 to 58
  See here for a discussion on efficient usage.
Added:
>
>

See Also

ShortestDistance, State Queues

 

References

Revision 92012-06-01 - MichaelRiley

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

ShortestPath

Revision 82012-05-13 - MichaelRiley

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

ShortestPath

Line: 51 to 51
 
  • n-shortest paths:
    • Time: O(V log V + n V + n E)
    • Space: O(n V)
Changed:
<
<
where V = # of states and E = # of arcs.
>
>
where V = # of states and E = # of arcs.See here for more discussion on efficiency.
 
Added:
>
>

Caveats

See here for a discussion on efficient usage.

 

References

Revision 72011-12-06 - MichaelRiley

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

ShortestPath

Line: 32 to 32
  shortestpath1.jpg
Added:
>
>
(TropicalWeight)
 

Shortest path in A:

shortestpath2.jpg

Revision 62011-02-01 - MichaelRiley

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

ShortestPath

Line: 9 to 9
 The single path that can be read from the ith of at most n transitions leaving the initial state of the resulting FST is the ith shortest path.

The weights need to be right distributive and have the path property. They also need to be left distributive as well for n -shortest

Changed:
<
<
with n > 1 (valid for TropicalWeight).
>
>
with n > 1 (valid for TropicalWeight).
 

Usage

Revision 52010-12-09 - MichaelRiley

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

ShortestPath

Line: 21 to 21
 fstshortestpath [--opts] a.fst out.fst --nshortest: type = int64, default = 1 Return N-shortest paths
Added:
>
>
--unique: default = false Return only distinct strings (NB: must be acceptor; epsilons treated as regular symbols)
  | |

Revision 42009-03-03 - MichaelRiley

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

ShortestPath

Line: 8 to 8
 The n -shortest paths are the n -lowest weight paths w.r.t. the natural semiring order. The single path that can be read from the ith of at most n transitions leaving the initial state of the resulting FST is the ith shortest path.
Changed:
<
<
The weights need to be right distributive and have the path property. They also need to be left distributive as well for n -shortest
>
>
The weights need to be right distributive and have the path property. They also need to be left distributive as well for n -shortest
 with n > 1 (valid for TropicalWeight).

Usage

Revision 32007-07-11 - MichaelRiley

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

ShortestPath

Line: 8 to 8
 The n -shortest paths are the n -lowest weight paths w.r.t. the natural semiring order. The single path that can be read from the ith of at most n transitions leaving the initial state of the resulting FST is the ith shortest path.
Changed:
<
<
The weights need to be right distributive and have the path property. They also need to be left distributive as well for n -shortest with n > 1.
>
>
The weights need to be right distributive and have the path property. They also need to be left distributive as well for n -shortest with n > 1 (valid for TropicalWeight).
 

Usage

Line: 59 to 59
  -- CyrilAllauzen - 05 Jul 2007
Added:
>
>
META FILEATTACHMENT attr="" autoattached="1" comment="2-shortest path example" date="1184014286" name="shortestpath3.jpg" path="shortestpath3.jpg" size="18910" user="Main.CyrilAllauzen" version="1"
 
META FILEATTACHMENT attr="" autoattached="1" comment="shortest path input example" date="1184014217" name="shortestpath1.jpg" path="shortestpath1.jpg" size="9583" user="Main.CyrilAllauzen" version="1"
META FILEATTACHMENT attr="" autoattached="1" comment="1-shortest path example" date="1184014250" name="shortestpath2.jpg" path="shortestpath2.jpg" size="6231" user="Main.CyrilAllauzen" version="1"
Deleted:
<
<
META FILEATTACHMENT attachment="shortestpath3.jpg" attr="" comment="2-shortest path example" date="1184014285" name="shortestpath3.jpg" path="shortestpath3.jpg" size="18910" stream="shortestpath3.jpg" user="Main.CyrilAllauzen" version="1"

Revision 22007-07-09 - CyrilAllauzen

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

ShortestPath

Line: 23 to 23
  Return N-shortest paths | |
Added:
>
>

Examples

A:

shortestpath1.jpg

Shortest path in A:

shortestpath2.jpg

2-shortest paths in A:

shortestpath3.jpg

 

Complexity

ShortestPath:

Line: 43 to 58
 

-- CyrilAllauzen - 05 Jul 2007

Added:
>
>
META FILEATTACHMENT attr="" autoattached="1" comment="shortest path input example" date="1184014217" name="shortestpath1.jpg" path="shortestpath1.jpg" size="9583" user="Main.CyrilAllauzen" version="1"
META FILEATTACHMENT attr="" autoattached="1" comment="1-shortest path example" date="1184014250" name="shortestpath2.jpg" path="shortestpath2.jpg" size="6231" user="Main.CyrilAllauzen" version="1"
META FILEATTACHMENT attachment="shortestpath3.jpg" attr="" comment="2-shortest path example" date="1184014285" name="shortestpath3.jpg" path="shortestpath3.jpg" size="18910" stream="shortestpath3.jpg" user="Main.CyrilAllauzen" version="1"

Revision 12007-07-05 - CyrilAllauzen

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

ShortestPath

Description

This operation produces an FST containing the n -shortest paths in the input FST. The n -shortest paths are the n -lowest weight paths w.r.t. the natural semiring order. The single path that can be read from the ith of at most n transitions leaving the initial state of the resulting FST is the ith shortest path.

The weights need to be right distributive and have the path property. They also need to be left distributive as well for n -shortest with n > 1.

Usage

template<class Arc>
void ShortestPath(const Fst<Arc> &ifst, MutableFst<Arc> *ofst, size_t n = 1);
%DOX{namespacefst.html#ShortestPath[doc]}%
fstshortestpath [--opts] a.fst out.fst
    --nshortest: type = int64, default = 1
      Return N-shortest paths
 

Complexity

ShortestPath:

  • 1-shortest path:
    • Time: O(V log V + E)
    • Space: O(V)
  • n-shortest paths:
    • Time: O(V log V + n V + n E)
    • Space: O(n V)
where V = # of states and E = # of arcs.

References

-- CyrilAllauzen - 05 Jul 2007

 
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