Changeset 2437:02c7076bf894 in lemon-0.x
- Timestamp:
- 05/07/07 10:47:38 (17 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3274
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/min_mean_cycle.h
r2413 r2437 22 22 /// \ingroup min_cost_flow 23 23 /// 24 /// \file 24 /// \file 25 25 /// \brief Karp algorithm for finding a minimum mean cycle. 26 26 … … 45 45 /// \author Peter Kovacs 46 46 47 #ifdef DOXYGEN48 template <typename Graph, typename LengthMap>49 #else50 47 template <typename Graph, 51 48 typename LengthMap = typename Graph::template EdgeMap<int> > 52 #endif53 54 49 class MinMeanCycle 55 50 { … … 66 61 typedef Path<Graph> Path; 67 62 typedef std::vector<Node> NodeVector; 68 typedef typename NodeVector::iterator NodeVectorIt;69 63 70 64 protected: … … 90 84 91 85 /// \brief Node map for storing path data. 92 /// 86 /// 93 87 /// Node map for storing path data of all nodes in the current 94 /// component. dmap[v][k] is the length of a shortest directed walk 88 /// component. dmap[v][k] is the length of a shortest directed walk 95 89 /// to node v from the starting node containing exactly k edges. 96 90 PathDataNodeMap dmap; 97 91 98 92 /// \brief The directed graph the algorithm runs on. 99 const Graph &graph;93 const Graph &graph; 100 94 /// \brief The length of the edges. 101 const LengthMap &length;102 95 const LengthMap &length; 96 103 97 /// \brief The total length of the found cycle. 104 98 Length cycle_length; 105 99 /// \brief The number of edges in the found cycle. 106 100 int cycle_size; 107 /// \brief A node for obtaining a minimum mean cycle. 101 /// \brief A node for obtaining a minimum mean cycle. 108 102 Node cycle_node; 109 103 110 104 /// \brief The found cycle. 111 105 Path *cycle_path; 112 /// \brief The algorithm uses local \ref lemon::Path "Path" 106 /// \brief The algorithm uses local \ref lemon::Path "Path" 113 107 /// structure to store the found cycle. 114 108 bool local_path; 115 109 116 110 /// \brief Node map for identifying strongly connected components. 117 111 IntNodeMap comp; … … 124 118 /// \brief The processed nodes in the last round. 125 119 NodeVector process; 126 120 127 121 public : 128 122 … … 133 127 /// \param _graph The directed graph the algorithm runs on. 134 128 /// \param _length The length (cost) of the edges. 135 MinMeanCycle( const Graph &_graph,136 const LengthMap &_length ) :129 MinMeanCycle( const Graph &_graph, 130 const LengthMap &_length ) : 137 131 graph(_graph), length(_length), dmap(_graph), comp(_graph), 138 132 cycle_length(0), cycle_size(-1), cycle_node(INVALID), … … 141 135 142 136 /// \brief The destructor of the class. 143 ~MinMeanCycle() { 137 ~MinMeanCycle() { 144 138 if (local_path) delete cycle_path; 145 139 } … … 157 151 // Creating vectors for all nodes 158 152 int n = nodes.size(); 159 for ( NodeVectorIt vi = nodes.begin(); vi != nodes.end(); ++vi) {160 dmap[ *vi].resize(n + 1);161 } 162 } 163 164 /// \brief Processes all rounds of computing required path data for 153 for (int i = 0; i < nodes.size(); ++i) { 154 dmap[nodes[i]].resize(n + 1); 155 } 156 } 157 158 /// \brief Processes all rounds of computing required path data for 165 159 /// the current component. 166 160 void processRounds() { … … 174 168 process.push_back(v); 175 169 } 176 // Processing other rounds 170 // Processing other rounds 177 171 int n = nodes.size(), k; 178 for (k = 2; k <= n && process.size() < n; ++k) {172 for (k = 2; k <= n && process.size() < n; ++k) 179 173 processNextBuildRound(k); 180 } 181 for ( ; k <= n; ++k) { 174 for ( ; k <= n; ++k) 182 175 processNextFullRound(k); 183 } 184 } 185 176 } 177 186 178 /// \brief Processes one round of computing required path data and 187 179 /// rebuilds \ref process vector. 188 180 void processNextBuildRound(int k) { 189 181 NodeVector next; 190 for ( NodeVectorIt ui = process.begin(); ui != process.end(); ++ui) {191 for (OutEdgeIt e(graph, *ui); e != INVALID; ++e) {182 for (int i = 0; i < process.size(); ++i) { 183 for (OutEdgeIt e(graph, process[i]); e != INVALID; ++e) { 192 184 Node v = graph.target(e); 193 185 if (comp[v] != comp_cnt) continue; 194 186 if (!dmap[v][k].found) { 195 187 next.push_back(v); 196 dmap[v][k] = PathData(true, dmap[ *ui][k-1].dist + length[e], e);188 dmap[v][k] = PathData(true, dmap[process[i]][k-1].dist + length[e], e); 197 189 } 198 else if (dmap[ *ui][k-1].dist + length[e] < dmap[v][k].dist) {199 dmap[v][k] = PathData(true, dmap[ *ui][k-1].dist + length[e], e);190 else if (dmap[process[i]][k-1].dist + length[e] < dmap[v][k].dist) { 191 dmap[v][k] = PathData(true, dmap[process[i]][k-1].dist + length[e], e); 200 192 } 201 193 } … … 207 199 /// using \ref nodes vector instead of \ref process vector. 208 200 void processNextFullRound(int k) { 209 for ( NodeVectorIt ui = nodes.begin(); ui != nodes.end(); ++ui) {210 for (OutEdgeIt e(graph, *ui); e != INVALID; ++e) {201 for (int i = 0; i < nodes.size(); ++i) { 202 for (OutEdgeIt e(graph, nodes[i]); e != INVALID; ++e) { 211 203 Node v = graph.target(e); 212 204 if (comp[v] != comp_cnt) continue; 213 if ( !dmap[v][k].found || 214 dmap[ *ui][k-1].dist + length[e] < dmap[v][k].dist ) {215 dmap[v][k] = PathData(true, dmap[ *ui][k-1].dist + length[e], e);205 if ( !dmap[v][k].found || 206 dmap[nodes[i]][k-1].dist + length[e] < dmap[v][k].dist ) { 207 dmap[v][k] = PathData(true, dmap[nodes[i]][k-1].dist + length[e], e); 216 208 } 217 209 } 218 210 } 219 211 } 220 221 /// \brief Finds the minimum cycle mean value in the current 212 213 /// \brief Finds the minimum cycle mean value in the current 222 214 /// component. 223 215 bool findCurrentMin(Length &min_length, int &min_size, Node &min_node) { 224 216 bool found_min = false; 225 for ( NodeVectorIt vi = nodes.begin(); vi != nodes.end(); ++vi) {217 for (int i = 0; i < nodes.size(); ++i) { 226 218 int n = nodes.size(); 227 if (!dmap[ *vi][n].found) continue;219 if (!dmap[nodes[i]][n].found) continue; 228 220 Length len; 229 221 int size; 230 222 bool found_one = false; 231 223 for (int k = 0; k < n; ++k) { 232 if (!dmap[ *vi][k].found) continue;233 Length _len = dmap[ *vi][n].dist - dmap[*vi][k].dist;234 int _size = n - k; 224 if (!dmap[nodes[i]][k].found) continue; 225 Length _len = dmap[nodes[i]][n].dist - dmap[nodes[i]][k].dist; 226 int _size = n - k; 235 227 if (!found_one || len * _size < _len * size) { 236 228 found_one = true; … … 239 231 } 240 232 } 241 if ( found_one && 233 if ( found_one && 242 234 (!found_min || len * min_size < min_length * size) ) { 243 235 found_min = true; 244 236 min_length = len; 245 237 min_size = size; 246 min_node = *vi;238 min_node = nodes[i]; 247 239 } 248 240 } 249 241 return found_min; 250 242 } 251 252 public: 253 243 244 public: 245 254 246 /// \brief Runs the algorithm. 255 247 /// … … 258 250 /// \return \c true if a cycle exists in the graph. 259 251 /// 260 /// \note Apart from the return value, m.run() is just a shortcut 252 /// \note Apart from the return value, m.run() is just a shortcut 261 253 /// of the following code. 262 254 /// \code … … 270 262 return findCycle(); 271 263 } 272 264 273 265 /// \brief Initializes the internal data structures. 274 266 void init() { … … 286 278 /// 287 279 /// \return \c true if a cycle exists in the graph. 288 /// 280 /// 289 281 /// \pre \ref init() must be called before using this function. 290 282 bool findMinMean() { … … 293 285 initCurrent(); 294 286 processRounds(); 295 287 296 288 Length min_length; 297 289 int min_size; 298 290 Node min_node; 299 291 bool found_min = findCurrentMin(min_length, min_size, min_node); 300 301 if ( found_min && (cycle_node == INVALID || 292 293 if ( found_min && (cycle_node == INVALID || 302 294 min_length * cycle_size < cycle_length * min_size) ) { 303 295 cycle_length = min_length; … … 308 300 return (cycle_node != INVALID); 309 301 } 310 302 311 303 /// \brief Finds a critical (minimum mean) cycle. 312 304 /// … … 315 307 /// 316 308 /// \return \c true if a cycle exists in the graph. 317 /// 318 /// \pre \ref init() and \ref findMinMean() must be called before 309 /// 310 /// \pre \ref init() and \ref findMinMean() must be called before 319 311 /// using this function. 320 312 bool findCycle() { … … 346 338 /// \brief Resets the internal data structures. 347 339 /// 348 /// Resets the internal data structures so that \ref findMinMean() 349 /// and \ref findCycle() can be called again (e.g. when the 340 /// Resets the internal data structures so that \ref findMinMean() 341 /// and \ref findCycle() can be called again (e.g. when the 350 342 /// underlaying graph has been modified). 351 343 void reset() { … … 356 348 comp_num = stronglyConnectedComponents(graph, comp); 357 349 } 358 350 359 351 /// \brief Returns the total length of the found cycle. 360 352 /// … … 362 354 /// 363 355 /// \pre \ref run() must be called before using this function. 364 Length cycleLength() const { 356 Length cycleLength() const { 365 357 return cycle_length; 366 358 } 367 359 368 360 /// \brief Returns the number of edges in the found cycle. 369 361 /// … … 371 363 /// 372 364 /// \pre \ref run() must be called before using this function. 373 int cycleEdgeNum() const { 365 int cycleEdgeNum() const { 374 366 return cycle_size; 375 367 } 376 368 377 369 /// \brief Returns the mean length of the found cycle. 378 370 /// … … 387 379 /// return m.cycleEdgeNum() / double(m.cycleLength()); 388 380 /// \endcode 389 double minMean() const { 381 double minMean() const { 390 382 return cycle_length / (double)cycle_size; 391 383 } … … 400 392 /// 401 393 /// \sa \ref cyclePath() 402 const Path &cycle() const {394 const Path& cycle() const { 403 395 return *cycle_path; 404 396 } 405 406 /// \brief Sets the \ref lemon::Path "Path" structure storing the 397 398 /// \brief Sets the \ref lemon::Path "Path" structure storing the 407 399 /// found cycle. 408 /// 409 /// Sets the \ref lemon::Path "Path" structure storing the found 410 /// cycle. If you don't use this function before calling 411 /// \ref run(), it will allocate one. The destuctor deallocates 400 /// 401 /// Sets the \ref lemon::Path "Path" structure storing the found 402 /// cycle. If you don't use this function before calling 403 /// \ref run(), it will allocate one. The destuctor deallocates 412 404 /// this automatically allocated map, of course. 413 405 /// 414 406 /// \note The algorithm calls only the \ref lemon::Path::addFront() 415 /// "addFront()" method of the given \ref lemon::Path "Path" 407 /// "addFront()" method of the given \ref lemon::Path "Path" 416 408 /// structure. 417 /// 409 /// 418 410 /// \return \c (*this) 419 MinMeanCycle &cyclePath(Path&path) {411 MinMeanCycle& cyclePath(Path &path) { 420 412 if (local_path) { 421 413 delete cycle_path;
Note: See TracChangeset
for help on using the changeset viewer.