97 /// a minimum mean cycle. |
97 /// a minimum mean cycle. |
98 /// |
98 /// |
99 /// This class implements the Hartmann-Orlin algorithm for finding |
99 /// This class implements the Hartmann-Orlin algorithm for finding |
100 /// a directed cycle of minimum mean cost in a digraph |
100 /// a directed cycle of minimum mean cost in a digraph |
101 /// \ref hartmann93finding, \ref dasdan98minmeancycle. |
101 /// \ref hartmann93finding, \ref dasdan98minmeancycle. |
102 /// It is an improved version of \ref KarpMmc "Karp"'s original algorithm, |
102 /// This method is based on \ref KarpMmc "Karp"'s original algorithm, but |
103 /// it applies an efficient early termination scheme. |
103 /// applies an early termination scheme. It makes the algorithm |
104 /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e). |
104 /// significantly faster for some problem instances, but slower for others. |
|
105 /// The algorithm runs in time O(ne) and uses space O(n<sup>2</sup>+e). |
105 /// |
106 /// |
106 /// \tparam GR The type of the digraph the algorithm runs on. |
107 /// \tparam GR The type of the digraph the algorithm runs on. |
107 /// \tparam CM The type of the cost map. The default |
108 /// \tparam CM The type of the cost map. The default |
108 /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". |
109 /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". |
109 /// \tparam TR The traits class that defines various types used by the |
110 /// \tparam TR The traits class that defines various types used by the |
272 /// |
273 /// |
273 /// This function sets an external path structure for storing the |
274 /// This function sets an external path structure for storing the |
274 /// found cycle. |
275 /// found cycle. |
275 /// |
276 /// |
276 /// If you don't call this function before calling \ref run() or |
277 /// If you don't call this function before calling \ref run() or |
277 /// \ref findCycleMean(), it will allocate a local \ref Path "path" |
278 /// \ref findCycleMean(), a local \ref Path "path" structure |
278 /// structure. The destuctor deallocates this automatically |
279 /// will be allocated. The destuctor deallocates this automatically |
279 /// allocated object, of course. |
280 /// allocated object, of course. |
280 /// |
281 /// |
281 /// \note The algorithm calls only the \ref lemon::Path::addFront() |
282 /// \note The algorithm calls only the \ref lemon::Path::addFront() |
282 /// "addFront()" function of the given path structure. |
283 /// "addFront()" function of the given path structure. |
283 /// |
284 /// |