55 GRAPH_TYPEDEFS(typename Graph); |
55 GRAPH_TYPEDEFS(typename Graph); |
56 |
56 |
57 typedef typename LengthMap::Value Length; |
57 typedef typename LengthMap::Value Length; |
58 typedef Path<Graph> Path; |
58 typedef Path<Graph> Path; |
59 |
59 |
60 protected: |
60 private: |
|
61 |
|
62 // The directed graph the algorithm runs on |
|
63 const Graph &_graph; |
|
64 // The length of the edges |
|
65 const LengthMap &_length; |
|
66 |
|
67 // The total length of the found cycle |
|
68 Length _cycle_length; |
|
69 // The number of edges on the found cycle |
|
70 int _cycle_size; |
|
71 // The found cycle |
|
72 Path *_cycle_path; |
|
73 |
|
74 bool _local_path; |
|
75 bool _cycle_found; |
|
76 Node _cycle_node; |
61 |
77 |
62 typename Graph::template NodeMap<bool> _reached; |
78 typename Graph::template NodeMap<bool> _reached; |
63 typename Graph::template NodeMap<double> _dist; |
79 typename Graph::template NodeMap<double> _dist; |
64 typename Graph::template NodeMap<Edge> _policy; |
80 typename Graph::template NodeMap<Edge> _policy; |
65 |
|
66 /// The directed graph the algorithm runs on. |
|
67 const Graph &_graph; |
|
68 /// The length of the edges. |
|
69 const LengthMap &_length; |
|
70 |
|
71 /// The total length of the found cycle. |
|
72 Length _cycle_length; |
|
73 /// The number of edges on the found cycle. |
|
74 int _cycle_size; |
|
75 /// The found cycle. |
|
76 Path *_cycle_path; |
|
77 |
|
78 bool _local_path; |
|
79 bool _cycle_found; |
|
80 Node _cycle_node; |
|
81 |
81 |
82 typename Graph::template NodeMap<int> _component; |
82 typename Graph::template NodeMap<int> _component; |
83 int _component_num; |
83 int _component_num; |
84 |
84 |
85 std::vector<Node> _nodes; |
85 std::vector<Node> _nodes; |
94 /// |
94 /// |
95 /// \param graph The directed graph the algorithm runs on. |
95 /// \param graph The directed graph the algorithm runs on. |
96 /// \param length The length (cost) of the edges. |
96 /// \param length The length (cost) of the edges. |
97 MinMeanCycle( const Graph &graph, |
97 MinMeanCycle( const Graph &graph, |
98 const LengthMap &length ) : |
98 const LengthMap &length ) : |
99 _graph(graph), _length(length), _dist(graph), _reached(graph), |
99 _graph(graph), _length(length), _cycle_length(0), _cycle_size(-1), |
100 _policy(graph), _component(graph), _cycle_length(0), |
100 _cycle_path(NULL), _local_path(false), _reached(graph), |
101 _cycle_size(-1), _cycle_path(NULL), _local_path(false) |
101 _dist(graph), _policy(graph), _component(graph) |
102 { } |
102 {} |
103 |
103 |
104 /// The destructor of the class. |
104 /// The destructor of the class. |
105 ~MinMeanCycle() { |
105 ~MinMeanCycle() { |
106 if (_local_path) delete _cycle_path; |
106 if (_local_path) delete _cycle_path; |
107 } |
107 } |
108 |
108 |
109 protected: |
109 /// \brief Sets the \ref Path "path" structure for storing the found |
|
110 /// cycle. |
|
111 /// |
|
112 /// Sets an external \ref Path "path" structure for storing the |
|
113 /// found cycle. |
|
114 /// |
|
115 /// If you don't call this function before calling \ref run() or |
|
116 /// \ref init(), it will allocate a local \ref Path "path" |
|
117 /// structure. |
|
118 /// The destuctor deallocates this automatically allocated map, |
|
119 /// of course. |
|
120 /// |
|
121 /// \note The algorithm calls only the \ref lemon::Path::addBack() |
|
122 /// "addBack()" function of the given \ref Path "path" structure. |
|
123 /// |
|
124 /// \return <tt>(*this)</tt> |
|
125 /// |
|
126 /// \sa cycle() |
|
127 MinMeanCycle& cyclePath(Path &path) { |
|
128 if (_local_path) { |
|
129 delete _cycle_path; |
|
130 _local_path = false; |
|
131 } |
|
132 _cycle_path = &path; |
|
133 return *this; |
|
134 } |
|
135 |
|
136 /// \name Execution control |
|
137 /// The simplest way to execute the algorithm is to call run(). |
|
138 /// \n |
|
139 /// If you only need the minimum mean value, you may call init() |
|
140 /// and findMinMean(). |
|
141 /// \n |
|
142 /// If you would like to run the algorithm again (e.g. the |
|
143 /// underlaying graph and/or the edge costs were modified), you may |
|
144 /// not create a new instance of the class, rather call reset(), |
|
145 /// findMinMean(), and findCycle() instead. |
|
146 |
|
147 /// @{ |
|
148 |
|
149 /// \brief Runs the algorithm. |
|
150 /// |
|
151 /// Runs the algorithm. |
|
152 /// |
|
153 /// \return Returns \c true if a directed cycle exists in the graph. |
|
154 /// |
|
155 /// \note Apart from the return value, <tt>mmc.run()</tt> is just a |
|
156 /// shortcut of the following code. |
|
157 /// \code |
|
158 /// mmc.init(); |
|
159 /// mmc.findMinMean(); |
|
160 /// mmc.findCycle(); |
|
161 /// \endcode |
|
162 bool run() { |
|
163 init(); |
|
164 return findMinMean() && findCycle(); |
|
165 } |
|
166 |
|
167 /// \brief Initializes the internal data structures. |
|
168 /// |
|
169 /// Initializes the internal data structures. |
|
170 /// |
|
171 /// \sa reset() |
|
172 void init() { |
|
173 _tolerance.epsilon(1e-6); |
|
174 if (!_cycle_path) { |
|
175 _local_path = true; |
|
176 _cycle_path = new Path; |
|
177 } |
|
178 _cycle_found = false; |
|
179 _component_num = stronglyConnectedComponents(_graph, _component); |
|
180 } |
|
181 |
|
182 /// \brief Resets the internal data structures. |
|
183 /// |
|
184 /// Resets the internal data structures so that \ref findMinMean() |
|
185 /// and \ref findCycle() can be called again (e.g. when the |
|
186 /// underlaying graph has been modified). |
|
187 /// |
|
188 /// \sa init() |
|
189 void reset() { |
|
190 if (_cycle_path) _cycle_path->clear(); |
|
191 _cycle_found = false; |
|
192 _component_num = stronglyConnectedComponents(_graph, _component); |
|
193 } |
|
194 |
|
195 /// \brief Finds the minimum cycle mean length in the graph. |
|
196 /// |
|
197 /// Computes all the required data and finds the minimum cycle mean |
|
198 /// length in the graph. |
|
199 /// |
|
200 /// \return Returns \c true if a directed cycle exists in the graph. |
|
201 /// |
|
202 /// \pre \ref init() must be called before using this function. |
|
203 bool findMinMean() { |
|
204 // Finding the minimum mean cycle in the components |
|
205 for (int comp = 0; comp < _component_num; ++comp) { |
|
206 if (!initCurrentComponent(comp)) continue; |
|
207 while (true) { |
|
208 if (!findPolicyCycles()) break; |
|
209 contractPolicyGraph(comp); |
|
210 if (!computeNodeDistances(comp)) break; |
|
211 } |
|
212 } |
|
213 return _cycle_found; |
|
214 } |
|
215 |
|
216 /// \brief Finds a critical (minimum mean) directed cycle. |
|
217 /// |
|
218 /// Finds a critical (minimum mean) directed cycle using the data |
|
219 /// computed in the \ref findMinMean() function. |
|
220 /// |
|
221 /// \return Returns \c true if a directed cycle exists in the graph. |
|
222 /// |
|
223 /// \pre \ref init() and \ref findMinMean() must be called before |
|
224 /// using this function. |
|
225 bool findCycle() { |
|
226 if (!_cycle_found) return false; |
|
227 _cycle_path->addBack(_policy[_cycle_node]); |
|
228 for ( Node v = _cycle_node; |
|
229 (v = _graph.target(_policy[v])) != _cycle_node; ) { |
|
230 _cycle_path->addBack(_policy[v]); |
|
231 } |
|
232 return true; |
|
233 } |
|
234 |
|
235 /// @} |
|
236 |
|
237 /// \name Query Functions |
|
238 /// The result of the algorithm can be obtained using these |
|
239 /// functions. |
|
240 /// \n run() must be called before using them. |
|
241 |
|
242 /// @{ |
|
243 |
|
244 /// \brief Returns the total length of the found cycle. |
|
245 /// |
|
246 /// Returns the total length of the found cycle. |
|
247 /// |
|
248 /// \pre \ref run() or \ref findMinMean() must be called before |
|
249 /// using this function. |
|
250 Length cycleLength() const { |
|
251 return _cycle_length; |
|
252 } |
|
253 |
|
254 /// \brief Returns the number of edges on the found cycle. |
|
255 /// |
|
256 /// Returns the number of edges on the found cycle. |
|
257 /// |
|
258 /// \pre \ref run() or \ref findMinMean() must be called before |
|
259 /// using this function. |
|
260 int cycleEdgeNum() const { |
|
261 return _cycle_size; |
|
262 } |
|
263 |
|
264 /// \brief Returns the mean length of the found cycle. |
|
265 /// |
|
266 /// Returns the mean length of the found cycle. |
|
267 /// |
|
268 /// \pre \ref run() or \ref findMinMean() must be called before |
|
269 /// using this function. |
|
270 /// |
|
271 /// \note <tt>mmc.cycleMean()</tt> is just a shortcut of the |
|
272 /// following code. |
|
273 /// \code |
|
274 /// return double(mmc.cycleLength()) / mmc.cycleEdgeNum(); |
|
275 /// \endcode |
|
276 double cycleMean() const { |
|
277 return double(_cycle_length) / _cycle_size; |
|
278 } |
|
279 |
|
280 /// \brief Returns a const reference to the \ref Path "path" |
|
281 /// structure storing the found cycle. |
|
282 /// |
|
283 /// Returns a const reference to the \ref Path "path" |
|
284 /// structure storing the found cycle. |
|
285 /// |
|
286 /// \pre \ref run() or \ref findCycle() must be called before using |
|
287 /// this function. |
|
288 /// |
|
289 /// \sa cyclePath() |
|
290 const Path& cycle() const { |
|
291 return *_cycle_path; |
|
292 } |
|
293 |
|
294 ///@} |
|
295 |
|
296 private: |
110 |
297 |
111 // Initializes the internal data structures for the current strongly |
298 // Initializes the internal data structures for the current strongly |
112 // connected component and creating the policy graph. |
299 // connected component and creating the policy graph. |
113 // The policy graph can be represented by the _policy map because |
300 // The policy graph can be represented by the _policy map because |
114 // the out degree of every node is 1. |
301 // the out degree of every node is 1. |
146 |
333 |
147 // Finds all cycles in the policy graph. |
334 // Finds all cycles in the policy graph. |
148 // Sets _cycle_found to true if a cycle is found and sets |
335 // Sets _cycle_found to true if a cycle is found and sets |
149 // _cycle_length, _cycle_size, _cycle_node to represent the minimum |
336 // _cycle_length, _cycle_size, _cycle_node to represent the minimum |
150 // mean cycle in the policy graph. |
337 // mean cycle in the policy graph. |
151 bool findPolicyCycles(int comp) { |
338 bool findPolicyCycles() { |
152 typename Graph::template NodeMap<int> level(_graph, -1); |
339 typename Graph::template NodeMap<int> level(_graph, -1); |
153 _cycle_found = false; |
340 bool curr_cycle_found = false; |
154 Length clength; |
341 Length clength; |
155 int csize; |
342 int csize; |
156 int path_cnt = 0; |
343 int path_cnt = 0; |
157 Node u, v; |
344 Node u, v; |
158 // Searching for cycles |
345 // Searching for cycles |
159 for (int i = 0; i < _nodes.size(); ++i) { |
346 for (int i = 0; i < int(_nodes.size()); ++i) { |
160 if (level[_nodes[i]] < 0) { |
347 if (level[_nodes[i]] < 0) { |
161 u = _nodes[i]; |
348 u = _nodes[i]; |
162 level[u] = path_cnt; |
349 level[u] = path_cnt; |
163 while (level[u = _graph.target(_policy[u])] < 0) |
350 while (level[u = _graph.target(_policy[u])] < 0) |
164 level[u] = path_cnt; |
351 level[u] = path_cnt; |
165 if (level[u] == path_cnt) { |
352 if (level[u] == path_cnt) { |
166 // A cycle is found |
353 // A cycle is found |
|
354 curr_cycle_found = true; |
167 clength = _length[_policy[u]]; |
355 clength = _length[_policy[u]]; |
168 csize = 1; |
356 csize = 1; |
169 for (v = u; (v = _graph.target(_policy[v])) != u; ) { |
357 for (v = u; (v = _graph.target(_policy[v])) != u; ) { |
170 clength += _length[_policy[v]]; |
358 clength += _length[_policy[v]]; |
171 ++csize; |
359 ++csize; |
226 |
414 |
227 // Computes node distances in the policy graph and updates the |
415 // Computes node distances in the policy graph and updates the |
228 // policy graph if the node distances can be improved. |
416 // policy graph if the node distances can be improved. |
229 bool computeNodeDistances(int comp) { |
417 bool computeNodeDistances(int comp) { |
230 // Computing node distances using reverse BFS search |
418 // Computing node distances using reverse BFS search |
231 double cycle_mean = (double)_cycle_length / _cycle_size; |
419 double cycle_mean = double(_cycle_length) / _cycle_size; |
232 typename Graph::template NodeMap<int> found(_graph, false); |
420 typename Graph::template NodeMap<int> found(_graph, false); |
233 std::deque<Node> queue; |
421 std::deque<Node> queue; |
234 queue.push_back(_cycle_node); |
422 queue.push_back(_cycle_node); |
235 found[_cycle_node] = true; |
423 found[_cycle_node] = true; |
|
424 _dist[_cycle_node] = 0; |
236 Node u, v; |
425 Node u, v; |
237 while (!queue.empty()) { |
426 while (!queue.empty()) { |
238 v = queue.front(); queue.pop_front(); |
427 v = queue.front(); queue.pop_front(); |
239 for (InEdgeIt e(_graph, v); e != INVALID; ++e) { |
428 for (InEdgeIt e(_graph, v); e != INVALID; ++e) { |
240 u = _graph.source(e); |
429 u = _graph.source(e); |
258 } |
447 } |
259 } |
448 } |
260 return improved; |
449 return improved; |
261 } |
450 } |
262 |
451 |
263 public: |
|
264 |
|
265 /// \brief Runs the algorithm. |
|
266 /// |
|
267 /// Runs the algorithm. |
|
268 /// |
|
269 /// \return Returns \c true if a directed cycle exists in the graph. |
|
270 /// |
|
271 /// \note Apart from the return value, <tt>mmc.run()</tt> is just a |
|
272 /// shortcut of the following code. |
|
273 /// \code |
|
274 /// mmc.init(); |
|
275 /// mmc.findMinMean(); |
|
276 /// mmc.findCycle(); |
|
277 /// \endcode |
|
278 bool run() { |
|
279 init(); |
|
280 return findMinMean() && findCycle(); |
|
281 } |
|
282 |
|
283 /// \brief Initializes the internal data structures. |
|
284 /// |
|
285 /// Initializes the internal data structures. |
|
286 /// |
|
287 /// \sa reset() |
|
288 void init() { |
|
289 _tolerance.epsilon(1e-8); |
|
290 if (!_cycle_path) { |
|
291 _local_path = true; |
|
292 _cycle_path = new Path; |
|
293 } |
|
294 _cycle_found = false; |
|
295 _component_num = stronglyConnectedComponents(_graph, _component); |
|
296 } |
|
297 |
|
298 /// \brief Resets the internal data structures. |
|
299 /// |
|
300 /// Resets the internal data structures so that \ref findMinMean() |
|
301 /// and \ref findCycle() can be called again (e.g. when the |
|
302 /// underlaying graph has been modified). |
|
303 /// |
|
304 /// \sa init() |
|
305 void reset() { |
|
306 if (_cycle_path) _cycle_path->clear(); |
|
307 _cycle_found = false; |
|
308 _component_num = stronglyConnectedComponents(_graph, _component); |
|
309 } |
|
310 |
|
311 /// \brief Finds the minimum cycle mean length in the graph. |
|
312 /// |
|
313 /// Computes all the required data and finds the minimum cycle mean |
|
314 /// length in the graph. |
|
315 /// |
|
316 /// \return Returns \c true if a directed cycle exists in the graph. |
|
317 /// |
|
318 /// \pre \ref init() must be called before using this function. |
|
319 bool findMinMean() { |
|
320 // Finding the minimum mean cycle in the components |
|
321 for (int comp = 0; comp < _component_num; ++comp) { |
|
322 if (!initCurrentComponent(comp)) continue; |
|
323 while (true) { |
|
324 if (!findPolicyCycles(comp)) return false; |
|
325 contractPolicyGraph(comp); |
|
326 if (!computeNodeDistances(comp)) return true; |
|
327 } |
|
328 } |
|
329 } |
|
330 |
|
331 /// \brief Finds a critical (minimum mean) directed cycle. |
|
332 /// |
|
333 /// Finds a critical (minimum mean) directed cycle using the data |
|
334 /// computed in the \ref findMinMean() function. |
|
335 /// |
|
336 /// \return Returns \c true if a directed cycle exists in the graph. |
|
337 /// |
|
338 /// \pre \ref init() and \ref findMinMean() must be called before |
|
339 /// using this function. |
|
340 bool findCycle() { |
|
341 if (!_cycle_found) return false; |
|
342 _cycle_path->addBack(_policy[_cycle_node]); |
|
343 for ( Node v = _cycle_node; |
|
344 (v = _graph.target(_policy[v])) != _cycle_node; ) { |
|
345 _cycle_path->addBack(_policy[v]); |
|
346 } |
|
347 return true; |
|
348 } |
|
349 |
|
350 /// \brief Returns the total length of the found cycle. |
|
351 /// |
|
352 /// Returns the total length of the found cycle. |
|
353 /// |
|
354 /// \pre \ref run() or \ref findMinMean() must be called before |
|
355 /// using this function. |
|
356 Length cycleLength() const { |
|
357 return _cycle_length; |
|
358 } |
|
359 |
|
360 /// \brief Returns the number of edges on the found cycle. |
|
361 /// |
|
362 /// Returns the number of edges on the found cycle. |
|
363 /// |
|
364 /// \pre \ref run() or \ref findMinMean() must be called before |
|
365 /// using this function. |
|
366 int cycleEdgeNum() const { |
|
367 return _cycle_size; |
|
368 } |
|
369 |
|
370 /// \brief Returns the mean length of the found cycle. |
|
371 /// |
|
372 /// Returns the mean length of the found cycle. |
|
373 /// |
|
374 /// \pre \ref run() or \ref findMinMean() must be called before |
|
375 /// using this function. |
|
376 /// |
|
377 /// \note <tt>mmc.cycleMean()</tt> is just a shortcut of the |
|
378 /// following code. |
|
379 /// \code |
|
380 /// return double(mmc.cycleLength()) / mmc.cycleEdgeNum(); |
|
381 /// \endcode |
|
382 double cycleMean() const { |
|
383 return (double)_cycle_length / _cycle_size; |
|
384 } |
|
385 |
|
386 /// \brief Returns a const reference to the \ref Path "path" |
|
387 /// structure storing the found cycle. |
|
388 /// |
|
389 /// Returns a const reference to the \ref Path "path" |
|
390 /// structure storing the found cycle. |
|
391 /// |
|
392 /// \pre \ref run() or \ref findCycle() must be called before using |
|
393 /// this function. |
|
394 /// |
|
395 /// \sa cyclePath() |
|
396 const Path& cycle() const { |
|
397 return *_cycle_path; |
|
398 } |
|
399 |
|
400 /// \brief Sets the \ref Path "path" structure for storing the found |
|
401 /// cycle. |
|
402 /// |
|
403 /// Sets an external \ref Path "path" structure for storing the |
|
404 /// found cycle. |
|
405 /// |
|
406 /// If you don't call this function before calling \ref run() or |
|
407 /// \ref init(), it will allocate a local \ref Path "path" |
|
408 /// structure. |
|
409 /// The destuctor deallocates this automatically allocated map, |
|
410 /// of course. |
|
411 /// |
|
412 /// \note The algorithm calls only the \ref lemon::Path::addBack() |
|
413 /// "addBack()" function of the given \ref Path "path" structure. |
|
414 /// |
|
415 /// \return <tt>(*this)</tt> |
|
416 /// |
|
417 /// \sa cycle() |
|
418 MinMeanCycle& cyclePath(Path &path) { |
|
419 if (_local_path) { |
|
420 delete _cycle_path; |
|
421 _local_path = false; |
|
422 } |
|
423 _cycle_path = &path; |
|
424 return *this; |
|
425 } |
|
426 |
|
427 }; //class MinMeanCycle |
452 }; //class MinMeanCycle |
428 |
453 |
429 ///@} |
454 ///@} |
430 |
455 |
431 } //namespace lemon |
456 } //namespace lemon |