equal
deleted
inserted
replaced
17 */ |
17 */ |
18 |
18 |
19 #ifndef LEMON_HOWARD_H |
19 #ifndef LEMON_HOWARD_H |
20 #define LEMON_HOWARD_H |
20 #define LEMON_HOWARD_H |
21 |
21 |
22 /// \ingroup shortest_path |
22 /// \ingroup min_mean_cycle |
23 /// |
23 /// |
24 /// \file |
24 /// \file |
25 /// \brief Howard's algorithm for finding a minimum mean cycle. |
25 /// \brief Howard's algorithm for finding a minimum mean cycle. |
26 |
26 |
27 #include <vector> |
27 #include <vector> |
88 typedef lemon::Tolerance<LargeValue> Tolerance; |
88 typedef lemon::Tolerance<LargeValue> Tolerance; |
89 typedef lemon::Path<Digraph> Path; |
89 typedef lemon::Path<Digraph> Path; |
90 }; |
90 }; |
91 |
91 |
92 |
92 |
93 /// \addtogroup shortest_path |
93 /// \addtogroup min_mean_cycle |
94 /// @{ |
94 /// @{ |
95 |
95 |
96 /// \brief Implementation of Howard's algorithm for finding a minimum |
96 /// \brief Implementation of Howard's algorithm for finding a minimum |
97 /// mean cycle. |
97 /// mean cycle. |
98 /// |
98 /// |
99 /// This class implements Howard's policy iteration algorithm for finding |
99 /// This class implements Howard's policy iteration algorithm for finding |
100 /// a directed cycle of minimum mean length (cost) in a digraph. |
100 /// a directed cycle of minimum mean length (cost) in a digraph. |
|
101 /// This class provides the most efficient algorithm for the |
|
102 /// minimum mean cycle problem, though the best known theoretical |
|
103 /// bound on its running time is exponential. |
101 /// |
104 /// |
102 /// \tparam GR The type of the digraph the algorithm runs on. |
105 /// \tparam GR The type of the digraph the algorithm runs on. |
103 /// \tparam LEN The type of the length map. The default |
106 /// \tparam LEN The type of the length map. The default |
104 /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". |
107 /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". |
105 #ifdef DOXYGEN |
108 #ifdef DOXYGEN |