Changes in lemon/cycle_canceling.h [898:75c97c3786d6:886:7ef7a5fbb85d] in lemon
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/cycle_canceling.h
r898 r886 251 251 "The cost type of CycleCanceling must be signed"); 252 252 253 // Reset data structures 253 // Resize vectors 254 _node_num = countNodes(_graph); 255 _arc_num = countArcs(_graph); 256 _res_node_num = _node_num + 1; 257 _res_arc_num = 2 * (_arc_num + _node_num); 258 _root = _node_num; 259 260 _first_out.resize(_res_node_num + 1); 261 _forward.resize(_res_arc_num); 262 _source.resize(_res_arc_num); 263 _target.resize(_res_arc_num); 264 _reverse.resize(_res_arc_num); 265 266 _lower.resize(_res_arc_num); 267 _upper.resize(_res_arc_num); 268 _cost.resize(_res_arc_num); 269 _supply.resize(_res_node_num); 270 271 _res_cap.resize(_res_arc_num); 272 _pi.resize(_res_node_num); 273 274 _arc_vec.reserve(_res_arc_num); 275 _cost_vec.reserve(_res_arc_num); 276 _id_vec.reserve(_res_arc_num); 277 278 // Copy the graph 279 int i = 0, j = 0, k = 2 * _arc_num + _node_num; 280 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { 281 _node_id[n] = i; 282 } 283 i = 0; 284 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { 285 _first_out[i] = j; 286 for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) { 287 _arc_idf[a] = j; 288 _forward[j] = true; 289 _source[j] = i; 290 _target[j] = _node_id[_graph.runningNode(a)]; 291 } 292 for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) { 293 _arc_idb[a] = j; 294 _forward[j] = false; 295 _source[j] = i; 296 _target[j] = _node_id[_graph.runningNode(a)]; 297 } 298 _forward[j] = false; 299 _source[j] = i; 300 _target[j] = _root; 301 _reverse[j] = k; 302 _forward[k] = true; 303 _source[k] = _root; 304 _target[k] = i; 305 _reverse[k] = j; 306 ++j; ++k; 307 } 308 _first_out[i] = j; 309 _first_out[_res_node_num] = k; 310 for (ArcIt a(_graph); a != INVALID; ++a) { 311 int fi = _arc_idf[a]; 312 int bi = _arc_idb[a]; 313 _reverse[fi] = bi; 314 _reverse[bi] = fi; 315 } 316 317 // Reset parameters 254 318 reset(); 255 319 } … … 386 450 /// \endcode 387 451 /// 388 /// This function can be called more than once. All the givenparameters389 /// are kept for the next call, unless \ref resetParams() or \ref reset()390 /// is used, thus only the modified parameters have to be set again.391 /// If the underlying digraph was also modified after the construction392 /// of the class (or the last \ref reset() call), then the \ref reset()393 /// function must be called.452 /// This function can be called more than once. All the parameters 453 /// that have been given are kept for the next call, unless 454 /// \ref reset() is called, thus only the modified parameters 455 /// have to be set again. See \ref reset() for examples. 456 /// However, the underlying digraph must not be modified after this 457 /// class have been constructed, since it copies and extends the graph. 394 458 /// 395 459 /// \param method The cycle-canceling method that will be used. … … 407 471 /// 408 472 /// \see ProblemType, Method 409 /// \see resetParams(), reset()410 473 ProblemType run(Method method = CANCEL_AND_TIGHTEN) { 411 474 ProblemType pt = init(); … … 421 484 /// \ref costMap(), \ref supplyMap(), \ref stSupply(). 422 485 /// 423 /// It is useful for multiple \ref run() calls. Basically, all the given 424 /// parameters are kept for the next \ref run() call, unless 425 /// \ref resetParams() or \ref reset() is used. 426 /// If the underlying digraph was also modified after the construction 427 /// of the class or the last \ref reset() call, then the \ref reset() 428 /// function must be used, otherwise \ref resetParams() is sufficient. 486 /// It is useful for multiple run() calls. If this function is not 487 /// used, all the parameters given before are kept for the next 488 /// \ref run() call. 489 /// However, the underlying digraph must not be modified after this 490 /// class have been constructed, since it copies and extends the graph. 429 491 /// 430 492 /// For example, … … 436 498 /// .supplyMap(sup).run(); 437 499 /// 438 /// // Run again with modified cost map (reset Params() is not called,500 /// // Run again with modified cost map (reset() is not called, 439 501 /// // so only the cost map have to be set again) 440 502 /// cost[e] += 100; 441 503 /// cc.costMap(cost).run(); 442 504 /// 443 /// // Run again from scratch using reset Params()505 /// // Run again from scratch using reset() 444 506 /// // (the lower bounds will be set to zero on all arcs) 445 /// cc.reset Params();507 /// cc.reset(); 446 508 /// cc.upperMap(capacity).costMap(cost) 447 509 /// .supplyMap(sup).run(); … … 449 511 /// 450 512 /// \return <tt>(*this)</tt> 451 /// 452 /// \see reset(), run() 453 CycleCanceling& resetParams() { 513 CycleCanceling& reset() { 454 514 for (int i = 0; i != _res_node_num; ++i) { 455 515 _supply[i] = 0; … … 468 528 } 469 529 _have_lower = false; 470 return *this;471 }472 473 /// \brief Reset the internal data structures and all the parameters474 /// that have been given before.475 ///476 /// This function resets the internal data structures and all the477 /// paramaters that have been given before using functions \ref lowerMap(),478 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().479 ///480 /// It is useful for multiple \ref run() calls. Basically, all the given481 /// parameters are kept for the next \ref run() call, unless482 /// \ref resetParams() or \ref reset() is used.483 /// If the underlying digraph was also modified after the construction484 /// of the class or the last \ref reset() call, then the \ref reset()485 /// function must be used, otherwise \ref resetParams() is sufficient.486 ///487 /// See \ref resetParams() for examples.488 ///489 /// \return <tt>(*this)</tt>490 ///491 /// \see resetParams(), run()492 CycleCanceling& reset() {493 // Resize vectors494 _node_num = countNodes(_graph);495 _arc_num = countArcs(_graph);496 _res_node_num = _node_num + 1;497 _res_arc_num = 2 * (_arc_num + _node_num);498 _root = _node_num;499 500 _first_out.resize(_res_node_num + 1);501 _forward.resize(_res_arc_num);502 _source.resize(_res_arc_num);503 _target.resize(_res_arc_num);504 _reverse.resize(_res_arc_num);505 506 _lower.resize(_res_arc_num);507 _upper.resize(_res_arc_num);508 _cost.resize(_res_arc_num);509 _supply.resize(_res_node_num);510 511 _res_cap.resize(_res_arc_num);512 _pi.resize(_res_node_num);513 514 _arc_vec.reserve(_res_arc_num);515 _cost_vec.reserve(_res_arc_num);516 _id_vec.reserve(_res_arc_num);517 518 // Copy the graph519 int i = 0, j = 0, k = 2 * _arc_num + _node_num;520 for (NodeIt n(_graph); n != INVALID; ++n, ++i) {521 _node_id[n] = i;522 }523 i = 0;524 for (NodeIt n(_graph); n != INVALID; ++n, ++i) {525 _first_out[i] = j;526 for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {527 _arc_idf[a] = j;528 _forward[j] = true;529 _source[j] = i;530 _target[j] = _node_id[_graph.runningNode(a)];531 }532 for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {533 _arc_idb[a] = j;534 _forward[j] = false;535 _source[j] = i;536 _target[j] = _node_id[_graph.runningNode(a)];537 }538 _forward[j] = false;539 _source[j] = i;540 _target[j] = _root;541 _reverse[j] = k;542 _forward[k] = true;543 _source[k] = _root;544 _target[k] = i;545 _reverse[k] = j;546 ++j; ++k;547 }548 _first_out[i] = j;549 _first_out[_res_node_num] = k;550 for (ArcIt a(_graph); a != INVALID; ++a) {551 int fi = _arc_idf[a];552 int bi = _arc_idb[a];553 _reverse[fi] = bi;554 _reverse[bi] = fi;555 }556 557 // Reset parameters558 resetParams();559 530 return *this; 560 531 }
Note: See TracChangeset
for help on using the changeset viewer.