Changeset 2581:054566ac0934 in lemon-0.x for lemon/cycle_canceling.h
- Timestamp:
- 02/28/08 03:54:27 (16 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3463
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/cycle_canceling.h
r2573 r2581 53 53 /// - Edge capacities and costs should be \e non-negative \e integers. 54 54 /// - Supply values should be \e signed \e integers. 55 /// - \c LowerMap::Value must be convertible to \c CapacityMap::Value. 56 /// - \c CapacityMap::Value and \c SupplyMap::Value must be 57 /// convertible to each other. 58 /// - All value types must be convertible to \c CostMap::Value, which 59 /// must be signed type. 55 /// - The value types of the maps should be convertible to each other. 56 /// - \c CostMap::Value must be signed type. 60 57 /// 61 58 /// \note By default the \ref BellmanFord "Bellman-Ford" algorithm is … … 95 92 /// The type of the flow map. 96 93 typedef typename Graph::template EdgeMap<Capacity> FlowMap; 94 /// The type of the potential map. 95 typedef typename Graph::template NodeMap<Cost> PotentialMap; 97 96 98 97 private: … … 144 143 145 144 // Edge map of the current flow 146 FlowMap _flow; 145 FlowMap *_flow; 146 bool _local_flow; 147 // Node map of the current potentials 148 PotentialMap *_potential; 149 bool _local_potential; 147 150 148 151 // The residual graph 149 ResGraph _res_graph;152 ResGraph *_res_graph; 150 153 // The residual cost map 151 154 ResidualCostMap _res_cost; … … 153 156 public: 154 157 155 /// \brief General constructor of the class(with lower bounds).156 /// 157 /// General constructor of the class(with lower bounds).158 /// \brief General constructor (with lower bounds). 159 /// 160 /// General constructor (with lower bounds). 158 161 /// 159 162 /// \param graph The directed graph the algorithm runs on. … … 168 171 const SupplyMap &supply ) : 169 172 _graph(graph), _lower(&lower), _capacity(graph), _cost(cost), 170 _supply(graph), _flow( graph, 0),171 _ res_graph(graph, _capacity, _flow), _res_cost(_cost)173 _supply(graph), _flow(0), _local_flow(false), 174 _potential(0), _local_potential(false), _res_cost(_cost) 172 175 { 173 176 // Removing non-zero lower bounds … … 185 188 } 186 189 187 /// \brief General constructor of the class(without lower bounds).188 /// 189 /// General constructor of the class(without lower bounds).190 /// \brief General constructor (without lower bounds). 191 /// 192 /// General constructor (without lower bounds). 190 193 /// 191 194 /// \param graph The directed graph the algorithm runs on. … … 198 201 const SupplyMap &supply ) : 199 202 _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost), 200 _supply(supply), _flow( graph, 0),201 _ res_graph(graph, _capacity, _flow), _res_cost(_cost)203 _supply(supply), _flow(0), _local_flow(false), 204 _potential(0), _local_potential(false), _res_cost(_cost) 202 205 { 203 206 // Checking the sum of supply values … … 207 210 } 208 211 209 /// \brief Simple constructor of the class(with lower bounds).210 /// 211 /// Simple constructor of the class(with lower bounds).212 /// \brief Simple constructor (with lower bounds). 213 /// 214 /// Simple constructor (with lower bounds). 212 215 /// 213 216 /// \param graph The directed graph the algorithm runs on. … … 226 229 Supply flow_value ) : 227 230 _graph(graph), _lower(&lower), _capacity(graph), _cost(cost), 228 _supply(graph), _flow( graph, 0),229 _ res_graph(graph, _capacity, _flow), _res_cost(_cost)231 _supply(graph), _flow(0), _local_flow(false), 232 _potential(0), _local_potential(false), _res_cost(_cost) 230 233 { 231 234 // Removing non-zero lower bounds … … 244 247 } 245 248 246 /// \brief Simple constructor of the class(without lower bounds).247 /// 248 /// Simple constructor of the class(without lower bounds).249 /// \brief Simple constructor (without lower bounds). 250 /// 251 /// Simple constructor (without lower bounds). 249 252 /// 250 253 /// \param graph The directed graph the algorithm runs on. … … 261 264 Supply flow_value ) : 262 265 _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost), 263 _supply(graph, 0), _flow( graph, 0),264 _ res_graph(graph, _capacity, _flow), _res_cost(_cost)266 _supply(graph, 0), _flow(0), _local_flow(false), 267 _potential(0), _local_potential(false), _res_cost(_cost) 265 268 { 266 269 _supply[s] = flow_value; … … 269 272 } 270 273 274 /// Destructor. 275 ~CycleCanceling() { 276 if (_local_flow) delete _flow; 277 if (_local_potential) delete _potential; 278 delete _res_graph; 279 } 280 281 /// \brief Sets the flow map. 282 /// 283 /// Sets the flow map. 284 /// 285 /// \return \c (*this) 286 CycleCanceling& flowMap(FlowMap &map) { 287 if (_local_flow) { 288 delete _flow; 289 _local_flow = false; 290 } 291 _flow = ↦ 292 return *this; 293 } 294 295 /// \brief Sets the potential map. 296 /// 297 /// Sets the potential map. 298 /// 299 /// \return \c (*this) 300 CycleCanceling& potentialMap(PotentialMap &map) { 301 if (_local_potential) { 302 delete _potential; 303 _local_potential = false; 304 } 305 _potential = ↦ 306 return *this; 307 } 308 309 /// \name Execution control 310 /// The only way to execute the algorithm is to call the run() 311 /// function. 312 313 /// @{ 314 271 315 /// \brief Runs the algorithm. 272 316 /// … … 282 326 } 283 327 328 /// @} 329 330 /// \name Query Functions 331 /// The result of the algorithm can be obtained using these 332 /// functions. 333 /// \n run() must be called before using them. 334 335 /// @{ 336 284 337 /// \brief Returns a const reference to the edge map storing the 285 338 /// found flow. … … 289 342 /// \pre \ref run() must be called before using this function. 290 343 const FlowMap& flowMap() const { 291 return _flow; 344 return *_flow; 345 } 346 347 /// \brief Returns a const reference to the node map storing the 348 /// found potentials (the dual solution). 349 /// 350 /// Returns a const reference to the node map storing the found 351 /// potentials (the dual solution). 352 /// 353 /// \pre \ref run() must be called before using this function. 354 const PotentialMap& potentialMap() const { 355 return *_potential; 356 } 357 358 /// \brief Returns the flow on the edge. 359 /// 360 /// Returns the flow on the edge. 361 /// 362 /// \pre \ref run() must be called before using this function. 363 Capacity flow(const Edge& edge) const { 364 return (*_flow)[edge]; 365 } 366 367 /// \brief Returns the potential of the node. 368 /// 369 /// Returns the potential of the node. 370 /// 371 /// \pre \ref run() must be called before using this function. 372 Cost potential(const Node& node) const { 373 return (*_potential)[node]; 292 374 } 293 375 … … 301 383 Cost c = 0; 302 384 for (EdgeIt e(_graph); e != INVALID; ++e) 303 c += _flow[e] * _cost[e];385 c += (*_flow)[e] * _cost[e]; 304 386 return c; 305 387 } 388 389 /// @} 306 390 307 391 private: … … 311 395 if (!_valid_supply) return false; 312 396 397 // Initializing flow and potential maps 398 if (!_flow) { 399 _flow = new FlowMap(_graph); 400 _local_flow = true; 401 } 402 if (!_potential) { 403 _potential = new PotentialMap(_graph); 404 _local_potential = true; 405 } 406 407 _res_graph = new ResGraph(_graph, _capacity, *_flow); 408 313 409 // Finding a feasible flow using Circulation 314 410 Circulation< Graph, ConstMap<Edge, Capacity>, CapacityEdgeMap, 315 411 SupplyMap > 316 circulation( _graph, constMap<Edge>( (Capacity)0), _capacity,412 circulation( _graph, constMap<Edge>(Capacity(0)), _capacity, 317 413 _supply ); 318 return circulation.flowMap( _flow).run();414 return circulation.flowMap(*_flow).run(); 319 415 } 320 416 321 417 bool start(bool min_mean_cc) { 322 418 if (min_mean_cc) 323 returnstartMinMean();419 startMinMean(); 324 420 else 325 return start(); 421 start(); 422 423 // Handling non-zero lower bounds 424 if (_lower) { 425 for (EdgeIt e(_graph); e != INVALID; ++e) 426 (*_flow)[e] += (*_lower)[e]; 427 } 428 return true; 326 429 } 327 430 … … 331 434 /// "Bellman-Ford" algorithm for negative cycle detection with 332 435 /// successively larger limit for the number of iterations. 333 boolstart() {334 typename BellmanFord<ResGraph, ResidualCostMap>::PredMap pred( _res_graph);335 typename ResGraph::template NodeMap<int> visited( _res_graph);436 void start() { 437 typename BellmanFord<ResGraph, ResidualCostMap>::PredMap pred(*_res_graph); 438 typename ResGraph::template NodeMap<int> visited(*_res_graph); 336 439 std::vector<ResEdge> cycle; 337 440 int node_num = countNodes(_graph); … … 340 443 bool optimal = false; 341 444 while (!optimal) { 342 BellmanFord<ResGraph, ResidualCostMap> bf( _res_graph, _res_cost);445 BellmanFord<ResGraph, ResidualCostMap> bf(*_res_graph, _res_cost); 343 446 bf.predMap(pred); 344 447 bf.init(0); … … 357 460 } 358 461 if (real_iter_num < curr_iter_num) { 462 // Optimal flow is found 359 463 optimal = true; 464 // Setting node potentials 465 for (NodeIt n(_graph); n != INVALID; ++n) 466 (*_potential)[n] = bf.dist(n); 360 467 break; 361 468 } else { 362 469 // Searching for node disjoint negative cycles 363 for (ResNodeIt n( _res_graph); n != INVALID; ++n)470 for (ResNodeIt n(*_res_graph); n != INVALID; ++n) 364 471 visited[n] = 0; 365 472 int id = 0; 366 for (ResNodeIt n( _res_graph); n != INVALID; ++n) {473 for (ResNodeIt n(*_res_graph); n != INVALID; ++n) { 367 474 if (visited[n] > 0) continue; 368 475 visited[n] = ++id; 369 476 ResNode u = pred[n] == INVALID ? 370 INVALID : _res_graph .source(pred[n]);477 INVALID : _res_graph->source(pred[n]); 371 478 while (u != INVALID && visited[u] == 0) { 372 479 visited[u] = id; 373 480 u = pred[u] == INVALID ? 374 INVALID : _res_graph .source(pred[u]);481 INVALID : _res_graph->source(pred[u]); 375 482 } 376 483 if (u != INVALID && visited[u] == id) { … … 380 487 ResEdge e = pred[u]; 381 488 cycle.push_back(e); 382 Capacity d = _res_graph .rescap(e);383 while (_res_graph .source(e) != u) {384 cycle.push_back(e = pred[_res_graph .source(e)]);385 if (_res_graph .rescap(e) < d)386 d = _res_graph .rescap(e);489 Capacity d = _res_graph->rescap(e); 490 while (_res_graph->source(e) != u) { 491 cycle.push_back(e = pred[_res_graph->source(e)]); 492 if (_res_graph->rescap(e) < d) 493 d = _res_graph->rescap(e); 387 494 } 388 495 389 496 // Augmenting along the cycle 390 497 for (int i = 0; i < int(cycle.size()); ++i) 391 _res_graph .augment(cycle[i], d);498 _res_graph->augment(cycle[i], d); 392 499 } 393 500 } … … 398 505 } 399 506 } 400 401 // Handling non-zero lower bounds402 if (_lower) {403 for (EdgeIt e(_graph); e != INVALID; ++e)404 _flow[e] += (*_lower)[e];405 }406 return true;407 507 } 408 508 … … 411 511 /// Executes the algorithm using \ref MinMeanCycle for negative 412 512 /// cycle detection. 413 boolstartMinMean() {513 void startMinMean() { 414 514 typedef Path<ResGraph> ResPath; 415 MinMeanCycle<ResGraph, ResidualCostMap> mmc( _res_graph, _res_cost);515 MinMeanCycle<ResGraph, ResidualCostMap> mmc(*_res_graph, _res_cost); 416 516 ResPath cycle; 417 517 … … 426 526 Capacity delta = 0; 427 527 for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) { 428 if (delta == 0 || _res_graph .rescap(e) < delta)429 delta = _res_graph .rescap(e);528 if (delta == 0 || _res_graph->rescap(e) < delta) 529 delta = _res_graph->rescap(e); 430 530 } 431 531 432 532 // Augmenting along the cycle 433 533 for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) 434 _res_graph .augment(e, delta);534 _res_graph->augment(e, delta); 435 535 436 536 // Finding the minimum cycle mean for the modified residual … … 441 541 } 442 542 443 // Handling non-zero lower bounds 444 if (_lower) { 445 for (EdgeIt e(_graph); e != INVALID; ++e) 446 _flow[e] += (*_lower)[e]; 447 } 448 return true; 543 // Computing node potentials 544 BellmanFord<ResGraph, ResidualCostMap> bf(*_res_graph, _res_cost); 545 bf.init(0); bf.start(); 546 for (NodeIt n(_graph); n != INVALID; ++n) 547 (*_potential)[n] = bf.dist(n); 449 548 } 450 549
Note: See TracChangeset
for help on using the changeset viewer.