30 #include <lemon/tolerance.h> |
30 #include <lemon/tolerance.h> |
31 #include <lemon/connectivity.h> |
31 #include <lemon/connectivity.h> |
32 |
32 |
33 namespace lemon { |
33 namespace lemon { |
34 |
34 |
|
35 /// \brief Default traits class of MinMeanCycle class. |
|
36 /// |
|
37 /// Default traits class of MinMeanCycle class. |
|
38 /// \tparam GR The type of the digraph. |
|
39 /// \tparam LEN The type of the length map. |
|
40 /// It must conform to the \ref concepts::ReadMap "ReadMap" concept. |
|
41 #ifdef DOXYGEN |
|
42 template <typename GR, typename LEN> |
|
43 #else |
|
44 template <typename GR, typename LEN, |
|
45 bool integer = std::numeric_limits<typename LEN::Value>::is_integer> |
|
46 #endif |
|
47 struct MinMeanCycleDefaultTraits |
|
48 { |
|
49 /// The type of the digraph |
|
50 typedef GR Digraph; |
|
51 /// The type of the length map |
|
52 typedef LEN LengthMap; |
|
53 /// The type of the arc lengths |
|
54 typedef typename LengthMap::Value Value; |
|
55 |
|
56 /// \brief The large value type used for internal computations |
|
57 /// |
|
58 /// The large value type used for internal computations. |
|
59 /// It is \c long \c long if the \c Value type is integer, |
|
60 /// otherwise it is \c double. |
|
61 /// \c Value must be convertible to \c LargeValue. |
|
62 typedef double LargeValue; |
|
63 |
|
64 /// The tolerance type used for internal computations |
|
65 typedef lemon::Tolerance<LargeValue> Tolerance; |
|
66 |
|
67 /// \brief The path type of the found cycles |
|
68 /// |
|
69 /// The path type of the found cycles. |
|
70 /// It must conform to the \ref lemon::concepts::Path "Path" concept |
|
71 /// and it must have an \c addBack() function. |
|
72 typedef lemon::Path<Digraph> Path; |
|
73 }; |
|
74 |
|
75 // Default traits class for integer value types |
|
76 template <typename GR, typename LEN> |
|
77 struct MinMeanCycleDefaultTraits<GR, LEN, true> |
|
78 { |
|
79 typedef GR Digraph; |
|
80 typedef LEN LengthMap; |
|
81 typedef typename LengthMap::Value Value; |
|
82 #ifdef LEMON_HAVE_LONG_LONG |
|
83 typedef long long LargeValue; |
|
84 #else |
|
85 typedef long LargeValue; |
|
86 #endif |
|
87 typedef lemon::Tolerance<LargeValue> Tolerance; |
|
88 typedef lemon::Path<Digraph> Path; |
|
89 }; |
|
90 |
|
91 |
35 /// \addtogroup shortest_path |
92 /// \addtogroup shortest_path |
36 /// @{ |
93 /// @{ |
37 |
94 |
38 /// \brief Implementation of Howard's algorithm for finding a minimum |
95 /// \brief Implementation of Howard's algorithm for finding a minimum |
39 /// mean cycle. |
96 /// mean cycle. |
42 /// directed cycle of minimum mean length (cost) in a digraph. |
99 /// directed cycle of minimum mean length (cost) in a digraph. |
43 /// |
100 /// |
44 /// \tparam GR The type of the digraph the algorithm runs on. |
101 /// \tparam GR The type of the digraph the algorithm runs on. |
45 /// \tparam LEN The type of the length map. The default |
102 /// \tparam LEN The type of the length map. The default |
46 /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". |
103 /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". |
47 /// |
|
48 /// \warning \c LEN::Value must be convertible to \c double. |
|
49 #ifdef DOXYGEN |
104 #ifdef DOXYGEN |
50 template <typename GR, typename LEN> |
105 template <typename GR, typename LEN, typename TR> |
51 #else |
106 #else |
52 template < typename GR, |
107 template < typename GR, |
53 typename LEN = typename GR::template ArcMap<int> > |
108 typename LEN = typename GR::template ArcMap<int>, |
|
109 typename TR = MinMeanCycleDefaultTraits<GR, LEN> > |
54 #endif |
110 #endif |
55 class MinMeanCycle |
111 class MinMeanCycle |
56 { |
112 { |
57 public: |
113 public: |
58 |
114 |
59 /// The type of the digraph the algorithm runs on |
115 /// The type of the digraph |
60 typedef GR Digraph; |
116 typedef typename TR::Digraph Digraph; |
61 /// The type of the length map |
117 /// The type of the length map |
62 typedef LEN LengthMap; |
118 typedef typename TR::LengthMap LengthMap; |
63 /// The type of the arc lengths |
119 /// The type of the arc lengths |
64 typedef typename LengthMap::Value Value; |
120 typedef typename TR::Value Value; |
65 /// The type of the paths |
121 |
66 typedef lemon::Path<Digraph> Path; |
122 /// \brief The large value type |
|
123 /// |
|
124 /// The large value type used for internal computations. |
|
125 /// Using the \ref MinMeanCycleDefaultTraits "default traits class", |
|
126 /// it is \c long \c long if the \c Value type is integer, |
|
127 /// otherwise it is \c double. |
|
128 typedef typename TR::LargeValue LargeValue; |
|
129 |
|
130 /// The tolerance type |
|
131 typedef typename TR::Tolerance Tolerance; |
|
132 |
|
133 /// \brief The path type of the found cycles |
|
134 /// |
|
135 /// The path type of the found cycles. |
|
136 /// Using the \ref MinMeanCycleDefaultTraits "default traits class", |
|
137 /// it is \ref lemon::Path "Path<Digraph>". |
|
138 typedef typename TR::Path Path; |
|
139 |
|
140 /// The \ref MinMeanCycleDefaultTraits "traits class" of the algorithm |
|
141 typedef TR Traits; |
67 |
142 |
68 private: |
143 private: |
69 |
144 |
70 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
145 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
71 |
146 |
74 // The length of the arcs |
149 // The length of the arcs |
75 const LengthMap &_length; |
150 const LengthMap &_length; |
76 |
151 |
77 // Data for the found cycles |
152 // Data for the found cycles |
78 bool _curr_found, _best_found; |
153 bool _curr_found, _best_found; |
79 Value _curr_length, _best_length; |
154 LargeValue _curr_length, _best_length; |
80 int _curr_size, _best_size; |
155 int _curr_size, _best_size; |
81 Node _curr_node, _best_node; |
156 Node _curr_node, _best_node; |
82 |
157 |
83 Path *_cycle_path; |
158 Path *_cycle_path; |
84 bool _local_path; |
159 bool _local_path; |
85 |
160 |
86 // Internal data used by the algorithm |
161 // Internal data used by the algorithm |
87 typename Digraph::template NodeMap<Arc> _policy; |
162 typename Digraph::template NodeMap<Arc> _policy; |
88 typename Digraph::template NodeMap<bool> _reached; |
163 typename Digraph::template NodeMap<bool> _reached; |
89 typename Digraph::template NodeMap<int> _level; |
164 typename Digraph::template NodeMap<int> _level; |
90 typename Digraph::template NodeMap<double> _dist; |
165 typename Digraph::template NodeMap<LargeValue> _dist; |
91 |
166 |
92 // Data for storing the strongly connected components |
167 // Data for storing the strongly connected components |
93 int _comp_num; |
168 int _comp_num; |
94 typename Digraph::template NodeMap<int> _comp; |
169 typename Digraph::template NodeMap<int> _comp; |
95 std::vector<std::vector<Node> > _comp_nodes; |
170 std::vector<std::vector<Node> > _comp_nodes; |
97 typename Digraph::template NodeMap<std::vector<Arc> > _in_arcs; |
172 typename Digraph::template NodeMap<std::vector<Arc> > _in_arcs; |
98 |
173 |
99 // Queue used for BFS search |
174 // Queue used for BFS search |
100 std::vector<Node> _queue; |
175 std::vector<Node> _queue; |
101 int _qfront, _qback; |
176 int _qfront, _qback; |
|
177 |
|
178 Tolerance _tolerance; |
|
179 |
|
180 public: |
|
181 |
|
182 /// \name Named Template Parameters |
|
183 /// @{ |
|
184 |
|
185 template <typename T> |
|
186 struct SetLargeValueTraits : public Traits { |
|
187 typedef T LargeValue; |
|
188 typedef lemon::Tolerance<T> Tolerance; |
|
189 }; |
|
190 |
|
191 /// \brief \ref named-templ-param "Named parameter" for setting |
|
192 /// \c LargeValue type. |
|
193 /// |
|
194 /// \ref named-templ-param "Named parameter" for setting \c LargeValue |
|
195 /// type. It is used for internal computations in the algorithm. |
|
196 template <typename T> |
|
197 struct SetLargeValue |
|
198 : public MinMeanCycle<GR, LEN, SetLargeValueTraits<T> > { |
|
199 typedef MinMeanCycle<GR, LEN, SetLargeValueTraits<T> > Create; |
|
200 }; |
|
201 |
|
202 template <typename T> |
|
203 struct SetPathTraits : public Traits { |
|
204 typedef T Path; |
|
205 }; |
|
206 |
|
207 /// \brief \ref named-templ-param "Named parameter" for setting |
|
208 /// \c %Path type. |
|
209 /// |
|
210 /// \ref named-templ-param "Named parameter" for setting the \c %Path |
|
211 /// type of the found cycles. |
|
212 /// It must conform to the \ref lemon::concepts::Path "Path" concept |
|
213 /// and it must have an \c addBack() function. |
|
214 template <typename T> |
|
215 struct SetPath |
|
216 : public MinMeanCycle<GR, LEN, SetPathTraits<T> > { |
|
217 typedef MinMeanCycle<GR, LEN, SetPathTraits<T> > Create; |
|
218 }; |
102 |
219 |
103 Tolerance<double> _tol; |
220 /// @} |
104 |
221 |
105 public: |
222 public: |
106 |
223 |
107 /// \brief Constructor. |
224 /// \brief Constructor. |
108 /// |
225 /// |
233 /// |
350 /// |
234 /// This function returns the total length of the found cycle. |
351 /// This function returns the total length of the found cycle. |
235 /// |
352 /// |
236 /// \pre \ref run() or \ref findMinMean() must be called before |
353 /// \pre \ref run() or \ref findMinMean() must be called before |
237 /// using this function. |
354 /// using this function. |
238 Value cycleLength() const { |
355 LargeValue cycleLength() const { |
239 return _best_length; |
356 return _best_length; |
240 } |
357 } |
241 |
358 |
242 /// \brief Return the number of arcs on the found cycle. |
359 /// \brief Return the number of arcs on the found cycle. |
243 /// |
360 /// |
331 if (_nodes->size() < 1 || |
447 if (_nodes->size() < 1 || |
332 (_nodes->size() == 1 && _in_arcs[(*_nodes)[0]].size() == 0)) { |
448 (_nodes->size() == 1 && _in_arcs[(*_nodes)[0]].size() == 0)) { |
333 return false; |
449 return false; |
334 } |
450 } |
335 for (int i = 0; i < int(_nodes->size()); ++i) { |
451 for (int i = 0; i < int(_nodes->size()); ++i) { |
336 _dist[(*_nodes)[i]] = std::numeric_limits<double>::max(); |
452 _dist[(*_nodes)[i]] = std::numeric_limits<LargeValue>::max(); |
337 } |
453 } |
338 Node u, v; |
454 Node u, v; |
339 Arc e; |
455 Arc e; |
340 for (int i = 0; i < int(_nodes->size()); ++i) { |
456 for (int i = 0; i < int(_nodes->size()); ++i) { |
341 v = (*_nodes)[i]; |
457 v = (*_nodes)[i]; |
390 // Find the component of the main cycle and compute node distances |
506 // Find the component of the main cycle and compute node distances |
391 // using reverse BFS |
507 // using reverse BFS |
392 for (int i = 0; i < int(_nodes->size()); ++i) { |
508 for (int i = 0; i < int(_nodes->size()); ++i) { |
393 _reached[(*_nodes)[i]] = false; |
509 _reached[(*_nodes)[i]] = false; |
394 } |
510 } |
395 double curr_mean = double(_curr_length) / _curr_size; |
|
396 _qfront = _qback = 0; |
511 _qfront = _qback = 0; |
397 _queue[0] = _curr_node; |
512 _queue[0] = _curr_node; |
398 _reached[_curr_node] = true; |
513 _reached[_curr_node] = true; |
399 _dist[_curr_node] = 0; |
514 _dist[_curr_node] = 0; |
400 Node u, v; |
515 Node u, v; |