Changeset 2583:7216b6a52ab9 in lemon0.x
 Timestamp:
 02/28/08 03:57:36 (15 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@3465
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/min_mean_cycle.h
r2555 r2583 27 27 #include <vector> 28 28 #include <lemon/graph_utils.h> 29 #include <lemon/topology.h>30 29 #include <lemon/path.h> 31 30 #include <lemon/tolerance.h> 31 #include <lemon/topology.h> 32 32 33 33 namespace lemon { … … 42 42 /// minimum mean directed cycle. 43 43 /// 44 /// \ param Graph The directed graph type the algorithm runs on.45 /// \ param LengthMap The type of the length (cost) map.44 /// \tparam Graph The directed graph type the algorithm runs on. 45 /// \tparam LengthMap The type of the length (cost) map. 46 46 /// 47 47 /// \warning \c LengthMap::Value must be convertible to \c double. … … 58 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 78 typename Graph::template NodeMap<bool> _reached; 63 79 typename Graph::template NodeMap<double> _dist; 64 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 82 typename Graph::template NodeMap<int> _component; … … 97 97 MinMeanCycle( const Graph &graph, 98 98 const LengthMap &length ) : 99 _graph(graph), _length(length), _ dist(graph), _reached(graph),100 _ policy(graph), _component(graph), _cycle_length(0),101 _ cycle_size(1), _cycle_path(NULL), _local_path(false)102 { 99 _graph(graph), _length(length), _cycle_length(0), _cycle_size(1), 100 _cycle_path(NULL), _local_path(false), _reached(graph), 101 _dist(graph), _policy(graph), _component(graph) 102 {} 103 103 104 104 /// The destructor of the class. … … 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(1e6); 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 298 // Initializes the internal data structures for the current strongly … … 128 315 } 129 316 // Initializing _reached, _dist, _policy maps 130 for (int i = 0; i < _nodes.size(); ++i) {317 for (int i = 0; i < int(_nodes.size()); ++i) { 131 318 _reached[_nodes[i]] = false; 132 319 _policy[_nodes[i]] = INVALID; 133 320 } 134 321 Node u; Edge e; 135 for (int j = 0; j < _edges.size(); ++j) {322 for (int j = 0; j < int(_edges.size()); ++j) { 136 323 e = _edges[j]; 137 324 u = _graph.source(e); … … 149 336 // _cycle_length, _cycle_size, _cycle_node to represent the minimum 150 337 // mean cycle in the policy graph. 151 bool findPolicyCycles( int comp) {338 bool findPolicyCycles() { 152 339 typename Graph::template NodeMap<int> level(_graph, 1); 153 _cycle_found = false;340 bool curr_cycle_found = false; 154 341 Length clength; 155 342 int csize; … … 157 344 Node u, v; 158 345 // Searching for cycles 159 for (int i = 0; i < _nodes.size(); ++i) {346 for (int i = 0; i < int(_nodes.size()); ++i) { 160 347 if (level[_nodes[i]] < 0) { 161 348 u = _nodes[i]; … … 165 352 if (level[u] == path_cnt) { 166 353 // A cycle is found 354 curr_cycle_found = true; 167 355 clength = _length[_policy[u]]; 168 356 csize = 1; … … 182 370 } 183 371 } 184 return _cycle_found;372 return curr_cycle_found; 185 373 } 186 374 … … 208 396 // reverse BFS search 209 397 queue.clear(); 210 for (int i = 0; i < _nodes.size(); ++i)398 for (int i = 0; i < int(_nodes.size()); ++i) 211 399 if (found[_nodes[i]]) queue.push_back(_nodes[i]); 212 400 int found_cnt = queue.size(); 213 while (found_cnt < _nodes.size() && !queue.empty()) {401 while (found_cnt < int(_nodes.size()) && !queue.empty()) { 214 402 v = queue.front(); queue.pop_front(); 215 403 for (InEdgeIt e(_graph, v); e != INVALID; ++e) { … … 229 417 bool computeNodeDistances(int comp) { 230 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 420 typename Graph::template NodeMap<int> found(_graph, false); 233 421 std::deque<Node> queue; 234 422 queue.push_back(_cycle_node); 235 423 found[_cycle_node] = true; 424 _dist[_cycle_node] = 0; 236 425 Node u, v; 237 426 while (!queue.empty()) { … … 248 437 // Improving node distances 249 438 bool improved = false; 250 for (int j = 0; j < _edges.size(); ++j) {439 for (int j = 0; j < int(_edges.size()); ++j) { 251 440 Edge e = _edges[j]; 252 441 u = _graph.source(e); v = _graph.target(e); … … 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 a272 /// shortcut of the following code.273 /// \code274 /// mmc.init();275 /// mmc.findMinMean();276 /// mmc.findCycle();277 /// \endcode278 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(1e8);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 the302 /// 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 mean314 /// 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 components321 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 data334 /// 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 before339 /// 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 before355 /// 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 before365 /// 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 before375 /// using this function.376 ///377 /// \note <tt>mmc.cycleMean()</tt> is just a shortcut of the378 /// following code.379 /// \code380 /// return double(mmc.cycleLength()) / mmc.cycleEdgeNum();381 /// \endcode382 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 using393 /// 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 found401 /// cycle.402 ///403 /// Sets an external \ref Path "path" structure for storing the404 /// found cycle.405 ///406 /// If you don't call this function before calling \ref run() or407 /// \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 452 }; //class MinMeanCycle 428 453
Note: See TracChangeset
for help on using the changeset viewer.