r898:75c97c3786d6
Wed, 10 Feb 2010 19:05:20
[Not Reviewed]
0 comments (0 inline)
0
5
0
107
78
104
82
109
80
| ... | ... |
@@ -316,65 +316,3 @@ |
| 316 | 316 |
|
| 317 |
// Resize vectors |
|
| 318 |
_node_num = countNodes(_graph); |
|
| 319 |
_arc_num = countArcs(_graph); |
|
| 320 |
_res_arc_num = 2 * (_arc_num + _node_num); |
|
| 321 |
_root = _node_num; |
|
| 322 |
++_node_num; |
|
| 323 |
|
|
| 324 |
_first_out.resize(_node_num + 1); |
|
| 325 |
_forward.resize(_res_arc_num); |
|
| 326 |
_source.resize(_res_arc_num); |
|
| 327 |
_target.resize(_res_arc_num); |
|
| 328 |
_reverse.resize(_res_arc_num); |
|
| 329 |
|
|
| 330 |
_lower.resize(_res_arc_num); |
|
| 331 |
_upper.resize(_res_arc_num); |
|
| 332 |
_cost.resize(_res_arc_num); |
|
| 333 |
_supply.resize(_node_num); |
|
| 334 |
|
|
| 335 |
_res_cap.resize(_res_arc_num); |
|
| 336 |
_pi.resize(_node_num); |
|
| 337 |
_excess.resize(_node_num); |
|
| 338 |
_pred.resize(_node_num); |
|
| 339 |
|
|
| 340 |
// Copy the graph |
|
| 341 |
int i = 0, j = 0, k = 2 * _arc_num + _node_num - 1; |
|
| 342 |
for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
|
|
| 343 |
_node_id[n] = i; |
|
| 344 |
} |
|
| 345 |
i = 0; |
|
| 346 |
for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
|
|
| 347 |
_first_out[i] = j; |
|
| 348 |
for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {
|
|
| 349 |
_arc_idf[a] = j; |
|
| 350 |
_forward[j] = true; |
|
| 351 |
_source[j] = i; |
|
| 352 |
_target[j] = _node_id[_graph.runningNode(a)]; |
|
| 353 |
} |
|
| 354 |
for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {
|
|
| 355 |
_arc_idb[a] = j; |
|
| 356 |
_forward[j] = false; |
|
| 357 |
_source[j] = i; |
|
| 358 |
_target[j] = _node_id[_graph.runningNode(a)]; |
|
| 359 |
} |
|
| 360 |
_forward[j] = false; |
|
| 361 |
_source[j] = i; |
|
| 362 |
_target[j] = _root; |
|
| 363 |
_reverse[j] = k; |
|
| 364 |
_forward[k] = true; |
|
| 365 |
_source[k] = _root; |
|
| 366 |
_target[k] = i; |
|
| 367 |
_reverse[k] = j; |
|
| 368 |
++j; ++k; |
|
| 369 |
} |
|
| 370 |
_first_out[i] = j; |
|
| 371 |
_first_out[_node_num] = k; |
|
| 372 |
for (ArcIt a(_graph); a != INVALID; ++a) {
|
|
| 373 |
int fi = _arc_idf[a]; |
|
| 374 |
int bi = _arc_idb[a]; |
|
| 375 |
_reverse[fi] = bi; |
|
| 376 |
_reverse[bi] = fi; |
|
| 377 |
} |
|
| 378 |
|
|
| 379 |
// Reset |
|
| 317 |
// Reset data structures |
|
| 380 | 318 |
reset(); |
| ... | ... |
@@ -513,8 +451,8 @@ |
| 513 | 451 |
/// |
| 514 |
/// This function can be called more than once. All the parameters |
|
| 515 |
/// that have been given are kept for the next call, unless |
|
| 516 |
/// \ref reset() is called, thus only the modified parameters |
|
| 517 |
/// have to be set again. See \ref reset() for examples. |
|
| 518 |
/// However, the underlying digraph must not be modified after this |
|
| 519 |
/// class have been constructed, since it copies and extends the graph. |
|
| 452 |
/// This function can be called more than once. All the given parameters |
|
| 453 |
/// are kept for the next call, unless \ref resetParams() or \ref reset() |
|
| 454 |
/// is used, thus only the modified parameters have to be set again. |
|
| 455 |
/// If the underlying digraph was also modified after the construction |
|
| 456 |
/// of the class (or the last \ref reset() call), then the \ref reset() |
|
| 457 |
/// function must be called. |
|
| 520 | 458 |
/// |
| ... | ... |
@@ -535,2 +473,3 @@ |
| 535 | 473 |
/// \see ProblemType |
| 474 |
/// \see resetParams(), reset() |
|
| 536 | 475 |
ProblemType run(int factor = 4) {
|
| ... | ... |
@@ -548,7 +487,8 @@ |
| 548 | 487 |
/// |
| 549 |
/// It is useful for multiple run() calls. If this function is not |
|
| 550 |
/// used, all the parameters given before are kept for the next |
|
| 551 |
/// \ref run() call. |
|
| 552 |
/// However, the underlying digraph must not be modified after this |
|
| 553 |
/// |
|
| 488 |
/// It is useful for multiple \ref run() calls. Basically, all the given |
|
| 489 |
/// parameters are kept for the next \ref run() call, unless |
|
| 490 |
/// \ref resetParams() or \ref reset() is used. |
|
| 491 |
/// If the underlying digraph was also modified after the construction |
|
| 492 |
/// of the class or the last \ref reset() call, then the \ref reset() |
|
| 493 |
/// function must be used, otherwise \ref resetParams() is sufficient. |
|
| 554 | 494 |
/// |
| ... | ... |
@@ -562,3 +502,3 @@ |
| 562 | 502 |
/// |
| 563 |
/// // Run again with modified cost map ( |
|
| 503 |
/// // Run again with modified cost map (resetParams() is not called, |
|
| 564 | 504 |
/// // so only the cost map have to be set again) |
| ... | ... |
@@ -567,5 +507,5 @@ |
| 567 | 507 |
/// |
| 568 |
/// // Run again from scratch using |
|
| 508 |
/// // Run again from scratch using resetParams() |
|
| 569 | 509 |
/// // (the lower bounds will be set to zero on all arcs) |
| 570 |
/// cs. |
|
| 510 |
/// cs.resetParams(); |
|
| 571 | 511 |
/// cs.upperMap(capacity).costMap(cost) |
| ... | ... |
@@ -575,3 +515,5 @@ |
| 575 | 515 |
/// \return <tt>(*this)</tt> |
| 576 |
|
|
| 516 |
/// |
|
| 517 |
/// \see reset(), run() |
|
| 518 |
CapacityScaling& resetParams() {
|
|
| 577 | 519 |
for (int i = 0; i != _node_num; ++i) {
|
| ... | ... |
@@ -588,2 +530,89 @@ |
| 588 | 530 |
|
| 531 |
/// \brief Reset the internal data structures and all the parameters |
|
| 532 |
/// that have been given before. |
|
| 533 |
/// |
|
| 534 |
/// This function resets the internal data structures and all the |
|
| 535 |
/// paramaters that have been given before using functions \ref lowerMap(), |
|
| 536 |
/// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(). |
|
| 537 |
/// |
|
| 538 |
/// It is useful for multiple \ref run() calls. Basically, all the given |
|
| 539 |
/// parameters are kept for the next \ref run() call, unless |
|
| 540 |
/// \ref resetParams() or \ref reset() is used. |
|
| 541 |
/// If the underlying digraph was also modified after the construction |
|
| 542 |
/// of the class or the last \ref reset() call, then the \ref reset() |
|
| 543 |
/// function must be used, otherwise \ref resetParams() is sufficient. |
|
| 544 |
/// |
|
| 545 |
/// See \ref resetParams() for examples. |
|
| 546 |
/// |
|
| 547 |
/// \return <tt>(*this)</tt> |
|
| 548 |
/// |
|
| 549 |
/// \see resetParams(), run() |
|
| 550 |
CapacityScaling& reset() {
|
|
| 551 |
// Resize vectors |
|
| 552 |
_node_num = countNodes(_graph); |
|
| 553 |
_arc_num = countArcs(_graph); |
|
| 554 |
_res_arc_num = 2 * (_arc_num + _node_num); |
|
| 555 |
_root = _node_num; |
|
| 556 |
++_node_num; |
|
| 557 |
|
|
| 558 |
_first_out.resize(_node_num + 1); |
|
| 559 |
_forward.resize(_res_arc_num); |
|
| 560 |
_source.resize(_res_arc_num); |
|
| 561 |
_target.resize(_res_arc_num); |
|
| 562 |
_reverse.resize(_res_arc_num); |
|
| 563 |
|
|
| 564 |
_lower.resize(_res_arc_num); |
|
| 565 |
_upper.resize(_res_arc_num); |
|
| 566 |
_cost.resize(_res_arc_num); |
|
| 567 |
_supply.resize(_node_num); |
|
| 568 |
|
|
| 569 |
_res_cap.resize(_res_arc_num); |
|
| 570 |
_pi.resize(_node_num); |
|
| 571 |
_excess.resize(_node_num); |
|
| 572 |
_pred.resize(_node_num); |
|
| 573 |
|
|
| 574 |
// Copy the graph |
|
| 575 |
int i = 0, j = 0, k = 2 * _arc_num + _node_num - 1; |
|
| 576 |
for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
|
|
| 577 |
_node_id[n] = i; |
|
| 578 |
} |
|
| 579 |
i = 0; |
|
| 580 |
for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
|
|
| 581 |
_first_out[i] = j; |
|
| 582 |
for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {
|
|
| 583 |
_arc_idf[a] = j; |
|
| 584 |
_forward[j] = true; |
|
| 585 |
_source[j] = i; |
|
| 586 |
_target[j] = _node_id[_graph.runningNode(a)]; |
|
| 587 |
} |
|
| 588 |
for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {
|
|
| 589 |
_arc_idb[a] = j; |
|
| 590 |
_forward[j] = false; |
|
| 591 |
_source[j] = i; |
|
| 592 |
_target[j] = _node_id[_graph.runningNode(a)]; |
|
| 593 |
} |
|
| 594 |
_forward[j] = false; |
|
| 595 |
_source[j] = i; |
|
| 596 |
_target[j] = _root; |
|
| 597 |
_reverse[j] = k; |
|
| 598 |
_forward[k] = true; |
|
| 599 |
_source[k] = _root; |
|
| 600 |
_target[k] = i; |
|
| 601 |
_reverse[k] = j; |
|
| 602 |
++j; ++k; |
|
| 603 |
} |
|
| 604 |
_first_out[i] = j; |
|
| 605 |
_first_out[_node_num] = k; |
|
| 606 |
for (ArcIt a(_graph); a != INVALID; ++a) {
|
|
| 607 |
int fi = _arc_idf[a]; |
|
| 608 |
int bi = _arc_idb[a]; |
|
| 609 |
_reverse[fi] = bi; |
|
| 610 |
_reverse[bi] = fi; |
|
| 611 |
} |
|
| 612 |
|
|
| 613 |
// Reset parameters |
|
| 614 |
resetParams(); |
|
| 615 |
return *this; |
|
| 616 |
} |
|
| 617 |
|
|
| 589 | 618 |
/// @} |
| ... | ... |
@@ -334,70 +334,4 @@ |
| 334 | 334 |
"The cost type of CostScaling must be signed"); |
| 335 |
|
|
| 336 |
// Resize vectors |
|
| 337 |
_node_num = countNodes(_graph); |
|
| 338 |
_arc_num = countArcs(_graph); |
|
| 339 |
_res_node_num = _node_num + 1; |
|
| 340 |
_res_arc_num = 2 * (_arc_num + _node_num); |
|
| 341 |
_root = _node_num; |
|
| 342 |
|
|
| 343 |
_first_out.resize(_res_node_num + 1); |
|
| 344 |
_forward.resize(_res_arc_num); |
|
| 345 |
_source.resize(_res_arc_num); |
|
| 346 |
_target.resize(_res_arc_num); |
|
| 347 |
_reverse.resize(_res_arc_num); |
|
| 348 |
|
|
| 349 |
_lower.resize(_res_arc_num); |
|
| 350 |
_upper.resize(_res_arc_num); |
|
| 351 |
_scost.resize(_res_arc_num); |
|
| 352 |
_supply.resize(_res_node_num); |
|
| 353 | 335 |
|
| 354 |
_res_cap.resize(_res_arc_num); |
|
| 355 |
_cost.resize(_res_arc_num); |
|
| 356 |
_pi.resize(_res_node_num); |
|
| 357 |
_excess.resize(_res_node_num); |
|
| 358 |
_next_out.resize(_res_node_num); |
|
| 359 |
|
|
| 360 |
_arc_vec.reserve(_res_arc_num); |
|
| 361 |
_cost_vec.reserve(_res_arc_num); |
|
| 362 |
|
|
| 363 |
// Copy the graph |
|
| 364 |
int i = 0, j = 0, k = 2 * _arc_num + _node_num; |
|
| 365 |
for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
|
|
| 366 |
_node_id[n] = i; |
|
| 367 |
} |
|
| 368 |
i = 0; |
|
| 369 |
for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
|
|
| 370 |
_first_out[i] = j; |
|
| 371 |
for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {
|
|
| 372 |
_arc_idf[a] = j; |
|
| 373 |
_forward[j] = true; |
|
| 374 |
_source[j] = i; |
|
| 375 |
_target[j] = _node_id[_graph.runningNode(a)]; |
|
| 376 |
} |
|
| 377 |
for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {
|
|
| 378 |
_arc_idb[a] = j; |
|
| 379 |
_forward[j] = false; |
|
| 380 |
_source[j] = i; |
|
| 381 |
_target[j] = _node_id[_graph.runningNode(a)]; |
|
| 382 |
} |
|
| 383 |
_forward[j] = false; |
|
| 384 |
_source[j] = i; |
|
| 385 |
_target[j] = _root; |
|
| 386 |
_reverse[j] = k; |
|
| 387 |
_forward[k] = true; |
|
| 388 |
_source[k] = _root; |
|
| 389 |
_target[k] = i; |
|
| 390 |
_reverse[k] = j; |
|
| 391 |
++j; ++k; |
|
| 392 |
} |
|
| 393 |
_first_out[i] = j; |
|
| 394 |
_first_out[_res_node_num] = k; |
|
| 395 |
for (ArcIt a(_graph); a != INVALID; ++a) {
|
|
| 396 |
int fi = _arc_idf[a]; |
|
| 397 |
int bi = _arc_idb[a]; |
|
| 398 |
_reverse[fi] = bi; |
|
| 399 |
_reverse[bi] = fi; |
|
| 400 |
} |
|
| 401 |
|
|
| 402 |
// Reset |
|
| 336 |
// Reset data structures |
|
| 403 | 337 |
reset(); |
| ... | ... |
@@ -536,8 +470,8 @@ |
| 536 | 470 |
/// |
| 537 |
/// This function can be called more than once. All the parameters |
|
| 538 |
/// that have been given are kept for the next call, unless |
|
| 539 |
/// \ref reset() is called, thus only the modified parameters |
|
| 540 |
/// have to be set again. See \ref reset() for examples. |
|
| 541 |
/// However, the underlying digraph must not be modified after this |
|
| 542 |
/// class have been constructed, since it copies and extends the graph. |
|
| 471 |
/// This function can be called more than once. All the given parameters |
|
| 472 |
/// are kept for the next call, unless \ref resetParams() or \ref reset() |
|
| 473 |
/// is used, thus only the modified parameters have to be set again. |
|
| 474 |
/// If the underlying digraph was also modified after the construction |
|
| 475 |
/// of the class (or the last \ref reset() call), then the \ref reset() |
|
| 476 |
/// function must be called. |
|
| 543 | 477 |
/// |
| ... | ... |
@@ -558,2 +492,3 @@ |
| 558 | 492 |
/// \see ProblemType, Method |
| 493 |
/// \see resetParams(), reset() |
|
| 559 | 494 |
ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) {
|
| ... | ... |
@@ -572,7 +507,8 @@ |
| 572 | 507 |
/// |
| 573 |
/// It is useful for multiple run() calls. If this function is not |
|
| 574 |
/// used, all the parameters given before are kept for the next |
|
| 575 |
/// \ref run() call. |
|
| 576 |
/// However, the underlying digraph must not be modified after this |
|
| 577 |
/// |
|
| 508 |
/// It is useful for multiple \ref run() calls. Basically, all the given |
|
| 509 |
/// parameters are kept for the next \ref run() call, unless |
|
| 510 |
/// \ref resetParams() or \ref reset() is used. |
|
| 511 |
/// If the underlying digraph was also modified after the construction |
|
| 512 |
/// of the class or the last \ref reset() call, then the \ref reset() |
|
| 513 |
/// function must be used, otherwise \ref resetParams() is sufficient. |
|
| 578 | 514 |
/// |
| ... | ... |
@@ -586,3 +522,3 @@ |
| 586 | 522 |
/// |
| 587 |
/// // Run again with modified cost map ( |
|
| 523 |
/// // Run again with modified cost map (resetParams() is not called, |
|
| 588 | 524 |
/// // so only the cost map have to be set again) |
| ... | ... |
@@ -591,5 +527,5 @@ |
| 591 | 527 |
/// |
| 592 |
/// // Run again from scratch using |
|
| 528 |
/// // Run again from scratch using resetParams() |
|
| 593 | 529 |
/// // (the lower bounds will be set to zero on all arcs) |
| 594 |
/// cs. |
|
| 530 |
/// cs.resetParams(); |
|
| 595 | 531 |
/// cs.upperMap(capacity).costMap(cost) |
| ... | ... |
@@ -599,3 +535,5 @@ |
| 599 | 535 |
/// \return <tt>(*this)</tt> |
| 600 |
|
|
| 536 |
/// |
|
| 537 |
/// \see reset(), run() |
|
| 538 |
CostScaling& resetParams() {
|
|
| 601 | 539 |
for (int i = 0; i != _res_node_num; ++i) {
|
| ... | ... |
@@ -619,2 +557,86 @@ |
| 619 | 557 |
|
| 558 |
/// \brief Reset all the parameters that have been given before. |
|
| 559 |
/// |
|
| 560 |
/// This function resets all the paramaters that have been given |
|
| 561 |
/// before using functions \ref lowerMap(), \ref upperMap(), |
|
| 562 |
/// \ref costMap(), \ref supplyMap(), \ref stSupply(). |
|
| 563 |
/// |
|
| 564 |
/// It is useful for multiple run() calls. If this function is not |
|
| 565 |
/// used, all the parameters given before are kept for the next |
|
| 566 |
/// \ref run() call. |
|
| 567 |
/// However, the underlying digraph must not be modified after this |
|
| 568 |
/// class have been constructed, since it copies and extends the graph. |
|
| 569 |
/// \return <tt>(*this)</tt> |
|
| 570 |
CostScaling& reset() {
|
|
| 571 |
// Resize vectors |
|
| 572 |
_node_num = countNodes(_graph); |
|
| 573 |
_arc_num = countArcs(_graph); |
|
| 574 |
_res_node_num = _node_num + 1; |
|
| 575 |
_res_arc_num = 2 * (_arc_num + _node_num); |
|
| 576 |
_root = _node_num; |
|
| 577 |
|
|
| 578 |
_first_out.resize(_res_node_num + 1); |
|
| 579 |
_forward.resize(_res_arc_num); |
|
| 580 |
_source.resize(_res_arc_num); |
|
| 581 |
_target.resize(_res_arc_num); |
|
| 582 |
_reverse.resize(_res_arc_num); |
|
| 583 |
|
|
| 584 |
_lower.resize(_res_arc_num); |
|
| 585 |
_upper.resize(_res_arc_num); |
|
| 586 |
_scost.resize(_res_arc_num); |
|
| 587 |
_supply.resize(_res_node_num); |
|
| 588 |
|
|
| 589 |
_res_cap.resize(_res_arc_num); |
|
| 590 |
_cost.resize(_res_arc_num); |
|
| 591 |
_pi.resize(_res_node_num); |
|
| 592 |
_excess.resize(_res_node_num); |
|
| 593 |
_next_out.resize(_res_node_num); |
|
| 594 |
|
|
| 595 |
_arc_vec.reserve(_res_arc_num); |
|
| 596 |
_cost_vec.reserve(_res_arc_num); |
|
| 597 |
|
|
| 598 |
// Copy the graph |
|
| 599 |
int i = 0, j = 0, k = 2 * _arc_num + _node_num; |
|
| 600 |
for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
|
|
| 601 |
_node_id[n] = i; |
|
| 602 |
} |
|
| 603 |
i = 0; |
|
| 604 |
for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
|
|
| 605 |
_first_out[i] = j; |
|
| 606 |
for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {
|
|
| 607 |
_arc_idf[a] = j; |
|
| 608 |
_forward[j] = true; |
|
| 609 |
_source[j] = i; |
|
| 610 |
_target[j] = _node_id[_graph.runningNode(a)]; |
|
| 611 |
} |
|
| 612 |
for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {
|
|
| 613 |
_arc_idb[a] = j; |
|
| 614 |
_forward[j] = false; |
|
| 615 |
_source[j] = i; |
|
| 616 |
_target[j] = _node_id[_graph.runningNode(a)]; |
|
| 617 |
} |
|
| 618 |
_forward[j] = false; |
|
| 619 |
_source[j] = i; |
|
| 620 |
_target[j] = _root; |
|
| 621 |
_reverse[j] = k; |
|
| 622 |
_forward[k] = true; |
|
| 623 |
_source[k] = _root; |
|
| 624 |
_target[k] = i; |
|
| 625 |
_reverse[k] = j; |
|
| 626 |
++j; ++k; |
|
| 627 |
} |
|
| 628 |
_first_out[i] = j; |
|
| 629 |
_first_out[_res_node_num] = k; |
|
| 630 |
for (ArcIt a(_graph); a != INVALID; ++a) {
|
|
| 631 |
int fi = _arc_idf[a]; |
|
| 632 |
int bi = _arc_idb[a]; |
|
| 633 |
_reverse[fi] = bi; |
|
| 634 |
_reverse[bi] = fi; |
|
| 635 |
} |
|
| 636 |
|
|
| 637 |
// Reset parameters |
|
| 638 |
resetParams(); |
|
| 639 |
return *this; |
|
| 640 |
} |
|
| 641 |
|
|
| 620 | 642 |
/// @} |
| ... | ... |
@@ -252,67 +252,3 @@ |
| 252 | 252 |
|
| 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 |
|
| 253 |
// Reset data structures |
|
| 318 | 254 |
reset(); |
| ... | ... |
@@ -451,8 +387,8 @@ |
| 451 | 387 |
/// |
| 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. |
|
| 388 |
/// This function can be called more than once. All the given parameters |
|
| 389 |
/// 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 construction |
|
| 392 |
/// of the class (or the last \ref reset() call), then the \ref reset() |
|
| 393 |
/// function must be called. |
|
| 458 | 394 |
/// |
| ... | ... |
@@ -472,2 +408,3 @@ |
| 472 | 408 |
/// \see ProblemType, Method |
| 409 |
/// \see resetParams(), reset() |
|
| 473 | 410 |
ProblemType run(Method method = CANCEL_AND_TIGHTEN) {
|
| ... | ... |
@@ -485,7 +422,8 @@ |
| 485 | 422 |
/// |
| 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 |
/// |
|
| 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. |
|
| 491 | 429 |
/// |
| ... | ... |
@@ -499,3 +437,3 @@ |
| 499 | 437 |
/// |
| 500 |
/// // Run again with modified cost map ( |
|
| 438 |
/// // Run again with modified cost map (resetParams() is not called, |
|
| 501 | 439 |
/// // so only the cost map have to be set again) |
| ... | ... |
@@ -504,5 +442,5 @@ |
| 504 | 442 |
/// |
| 505 |
/// // Run again from scratch using |
|
| 443 |
/// // Run again from scratch using resetParams() |
|
| 506 | 444 |
/// // (the lower bounds will be set to zero on all arcs) |
| 507 |
/// cc. |
|
| 445 |
/// cc.resetParams(); |
|
| 508 | 446 |
/// cc.upperMap(capacity).costMap(cost) |
| ... | ... |
@@ -512,3 +450,5 @@ |
| 512 | 450 |
/// \return <tt>(*this)</tt> |
| 513 |
|
|
| 451 |
/// |
|
| 452 |
/// \see reset(), run() |
|
| 453 |
CycleCanceling& resetParams() {
|
|
| 514 | 454 |
for (int i = 0; i != _res_node_num; ++i) {
|
| ... | ... |
@@ -532,2 +472,91 @@ |
| 532 | 472 |
|
| 473 |
/// \brief Reset the internal data structures and all the parameters |
|
| 474 |
/// that have been given before. |
|
| 475 |
/// |
|
| 476 |
/// This function resets the internal data structures and all the |
|
| 477 |
/// 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 given |
|
| 481 |
/// parameters are kept for the next \ref run() call, unless |
|
| 482 |
/// \ref resetParams() or \ref reset() is used. |
|
| 483 |
/// If the underlying digraph was also modified after the construction |
|
| 484 |
/// 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 vectors |
|
| 494 |
_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 graph |
|
| 519 |
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 parameters |
|
| 558 |
resetParams(); |
|
| 559 |
return *this; |
|
| 560 |
} |
|
| 561 |
|
|
| 533 | 562 |
/// @} |
| ... | ... |
@@ -196,2 +196,3 @@ |
| 196 | 196 |
IntVector _target; |
| 197 |
bool _arc_mixing; |
|
| 197 | 198 |
|
| ... | ... |
@@ -635,2 +636,3 @@ |
| 635 | 636 |
_graph(graph), _node_id(graph), _arc_id(graph), |
| 637 |
_arc_mixing(arc_mixing), |
|
| 636 | 638 |
MAX(std::numeric_limits<Value>::max()), |
| ... | ... |
@@ -645,54 +647,3 @@ |
| 645 | 647 |
|
| 646 |
// Resize vectors |
|
| 647 |
_node_num = countNodes(_graph); |
|
| 648 |
_arc_num = countArcs(_graph); |
|
| 649 |
int all_node_num = _node_num + 1; |
|
| 650 |
int max_arc_num = _arc_num + 2 * _node_num; |
|
| 651 |
|
|
| 652 |
_source.resize(max_arc_num); |
|
| 653 |
_target.resize(max_arc_num); |
|
| 654 |
|
|
| 655 |
_lower.resize(_arc_num); |
|
| 656 |
_upper.resize(_arc_num); |
|
| 657 |
_cap.resize(max_arc_num); |
|
| 658 |
_cost.resize(max_arc_num); |
|
| 659 |
_supply.resize(all_node_num); |
|
| 660 |
_flow.resize(max_arc_num); |
|
| 661 |
_pi.resize(all_node_num); |
|
| 662 |
|
|
| 663 |
_parent.resize(all_node_num); |
|
| 664 |
_pred.resize(all_node_num); |
|
| 665 |
_forward.resize(all_node_num); |
|
| 666 |
_thread.resize(all_node_num); |
|
| 667 |
_rev_thread.resize(all_node_num); |
|
| 668 |
_succ_num.resize(all_node_num); |
|
| 669 |
_last_succ.resize(all_node_num); |
|
| 670 |
_state.resize(max_arc_num); |
|
| 671 |
|
|
| 672 |
// Copy the graph |
|
| 673 |
int i = 0; |
|
| 674 |
for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
|
|
| 675 |
_node_id[n] = i; |
|
| 676 |
} |
|
| 677 |
if (arc_mixing) {
|
|
| 678 |
// Store the arcs in a mixed order |
|
| 679 |
int k = std::max(int(std::sqrt(double(_arc_num))), 10); |
|
| 680 |
int i = 0, j = 0; |
|
| 681 |
for (ArcIt a(_graph); a != INVALID; ++a) {
|
|
| 682 |
_arc_id[a] = i; |
|
| 683 |
_source[i] = _node_id[_graph.source(a)]; |
|
| 684 |
_target[i] = _node_id[_graph.target(a)]; |
|
| 685 |
if ((i += k) >= _arc_num) i = ++j; |
|
| 686 |
} |
|
| 687 |
} else {
|
|
| 688 |
// Store the arcs in the original order |
|
| 689 |
int i = 0; |
|
| 690 |
for (ArcIt a(_graph); a != INVALID; ++a, ++i) {
|
|
| 691 |
_arc_id[a] = i; |
|
| 692 |
_source[i] = _node_id[_graph.source(a)]; |
|
| 693 |
_target[i] = _node_id[_graph.target(a)]; |
|
| 694 |
} |
|
| 695 |
} |
|
| 696 |
|
|
| 697 |
// Reset parameters |
|
| 648 |
// Reset data structures |
|
| 698 | 649 |
reset(); |
| ... | ... |
@@ -844,8 +795,8 @@ |
| 844 | 795 |
/// |
| 845 |
/// This function can be called more than once. All the parameters |
|
| 846 |
/// that have been given are kept for the next call, unless |
|
| 847 |
/// \ref reset() is called, thus only the modified parameters |
|
| 848 |
/// have to be set again. See \ref reset() for examples. |
|
| 849 |
/// However, the underlying digraph must not be modified after this |
|
| 850 |
/// class have been constructed, since it copies and extends the graph. |
|
| 796 |
/// This function can be called more than once. All the given parameters |
|
| 797 |
/// are kept for the next call, unless \ref resetParams() or \ref reset() |
|
| 798 |
/// is used, thus only the modified parameters have to be set again. |
|
| 799 |
/// If the underlying digraph was also modified after the construction |
|
| 800 |
/// of the class (or the last \ref reset() call), then the \ref reset() |
|
| 801 |
/// function must be called. |
|
| 851 | 802 |
/// |
| ... | ... |
@@ -863,2 +814,3 @@ |
| 863 | 814 |
/// \see ProblemType, PivotRule |
| 815 |
/// \see resetParams(), reset() |
|
| 864 | 816 |
ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) {
|
| ... | ... |
@@ -874,7 +826,8 @@ |
| 874 | 826 |
/// |
| 875 |
/// It is useful for multiple run() calls. If this function is not |
|
| 876 |
/// used, all the parameters given before are kept for the next |
|
| 877 |
/// \ref run() call. |
|
| 878 |
/// However, the underlying digraph must not be modified after this |
|
| 879 |
/// |
|
| 827 |
/// It is useful for multiple \ref run() calls. Basically, all the given |
|
| 828 |
/// parameters are kept for the next \ref run() call, unless |
|
| 829 |
/// \ref resetParams() or \ref reset() is used. |
|
| 830 |
/// If the underlying digraph was also modified after the construction |
|
| 831 |
/// of the class or the last \ref reset() call, then the \ref reset() |
|
| 832 |
/// function must be used, otherwise \ref resetParams() is sufficient. |
|
| 880 | 833 |
/// |
| ... | ... |
@@ -888,3 +841,3 @@ |
| 888 | 841 |
/// |
| 889 |
/// // Run again with modified cost map ( |
|
| 842 |
/// // Run again with modified cost map (resetParams() is not called, |
|
| 890 | 843 |
/// // so only the cost map have to be set again) |
| ... | ... |
@@ -893,5 +846,5 @@ |
| 893 | 846 |
/// |
| 894 |
/// // Run again from scratch using |
|
| 847 |
/// // Run again from scratch using resetParams() |
|
| 895 | 848 |
/// // (the lower bounds will be set to zero on all arcs) |
| 896 |
/// ns. |
|
| 849 |
/// ns.resetParams(); |
|
| 897 | 850 |
/// ns.upperMap(capacity).costMap(cost) |
| ... | ... |
@@ -901,3 +854,5 @@ |
| 901 | 854 |
/// \return <tt>(*this)</tt> |
| 902 |
|
|
| 855 |
/// |
|
| 856 |
/// \see reset(), run() |
|
| 857 |
NetworkSimplex& resetParams() {
|
|
| 903 | 858 |
for (int i = 0; i != _node_num; ++i) {
|
| ... | ... |
@@ -915,2 +870,79 @@ |
| 915 | 870 |
|
| 871 |
/// \brief Reset the internal data structures and all the parameters |
|
| 872 |
/// that have been given before. |
|
| 873 |
/// |
|
| 874 |
/// This function resets the internal data structures and all the |
|
| 875 |
/// paramaters that have been given before using functions \ref lowerMap(), |
|
| 876 |
/// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(), |
|
| 877 |
/// \ref supplyType(). |
|
| 878 |
/// |
|
| 879 |
/// It is useful for multiple \ref run() calls. Basically, all the given |
|
| 880 |
/// parameters are kept for the next \ref run() call, unless |
|
| 881 |
/// \ref resetParams() or \ref reset() is used. |
|
| 882 |
/// If the underlying digraph was also modified after the construction |
|
| 883 |
/// of the class or the last \ref reset() call, then the \ref reset() |
|
| 884 |
/// function must be used, otherwise \ref resetParams() is sufficient. |
|
| 885 |
/// |
|
| 886 |
/// See \ref resetParams() for examples. |
|
| 887 |
/// |
|
| 888 |
/// \return <tt>(*this)</tt> |
|
| 889 |
/// |
|
| 890 |
/// \see resetParams(), run() |
|
| 891 |
NetworkSimplex& reset() {
|
|
| 892 |
// Resize vectors |
|
| 893 |
_node_num = countNodes(_graph); |
|
| 894 |
_arc_num = countArcs(_graph); |
|
| 895 |
int all_node_num = _node_num + 1; |
|
| 896 |
int max_arc_num = _arc_num + 2 * _node_num; |
|
| 897 |
|
|
| 898 |
_source.resize(max_arc_num); |
|
| 899 |
_target.resize(max_arc_num); |
|
| 900 |
|
|
| 901 |
_lower.resize(_arc_num); |
|
| 902 |
_upper.resize(_arc_num); |
|
| 903 |
_cap.resize(max_arc_num); |
|
| 904 |
_cost.resize(max_arc_num); |
|
| 905 |
_supply.resize(all_node_num); |
|
| 906 |
_flow.resize(max_arc_num); |
|
| 907 |
_pi.resize(all_node_num); |
|
| 908 |
|
|
| 909 |
_parent.resize(all_node_num); |
|
| 910 |
_pred.resize(all_node_num); |
|
| 911 |
_forward.resize(all_node_num); |
|
| 912 |
_thread.resize(all_node_num); |
|
| 913 |
_rev_thread.resize(all_node_num); |
|
| 914 |
_succ_num.resize(all_node_num); |
|
| 915 |
_last_succ.resize(all_node_num); |
|
| 916 |
_state.resize(max_arc_num); |
|
| 917 |
|
|
| 918 |
// Copy the graph |
|
| 919 |
int i = 0; |
|
| 920 |
for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
|
|
| 921 |
_node_id[n] = i; |
|
| 922 |
} |
|
| 923 |
if (_arc_mixing) {
|
|
| 924 |
// Store the arcs in a mixed order |
|
| 925 |
int k = std::max(int(std::sqrt(double(_arc_num))), 10); |
|
| 926 |
int i = 0, j = 0; |
|
| 927 |
for (ArcIt a(_graph); a != INVALID; ++a) {
|
|
| 928 |
_arc_id[a] = i; |
|
| 929 |
_source[i] = _node_id[_graph.source(a)]; |
|
| 930 |
_target[i] = _node_id[_graph.target(a)]; |
|
| 931 |
if ((i += k) >= _arc_num) i = ++j; |
|
| 932 |
} |
|
| 933 |
} else {
|
|
| 934 |
// Store the arcs in the original order |
|
| 935 |
int i = 0; |
|
| 936 |
for (ArcIt a(_graph); a != INVALID; ++a, ++i) {
|
|
| 937 |
_arc_id[a] = i; |
|
| 938 |
_source[i] = _node_id[_graph.source(a)]; |
|
| 939 |
_target[i] = _node_id[_graph.target(a)]; |
|
| 940 |
} |
|
| 941 |
} |
|
| 942 |
|
|
| 943 |
// Reset parameters |
|
| 944 |
resetParams(); |
|
| 945 |
return *this; |
|
| 946 |
} |
|
| 947 |
|
|
| 916 | 948 |
/// @} |
| ... | ... |
@@ -159,3 +159,3 @@ |
| 159 | 159 |
|
| 160 |
b = mcf.reset() |
|
| 160 |
b = mcf.reset().resetParams() |
|
| 161 | 161 |
.lowerMap(me.lower) |
| ... | ... |
@@ -348,3 +348,3 @@ |
| 348 | 348 |
mcf1.OPTIMAL, true, 8010, test_str + "-4"); |
| 349 |
mcf1. |
|
| 349 |
mcf1.resetParams().supplyMap(s1); |
|
| 350 | 350 |
checkMcf(mcf1, mcf1.run(param), gr, l1, cu, cc, s1, |
| ... | ... |
@@ -365,3 +365,3 @@ |
| 365 | 365 |
// Tests for the GEQ form |
| 366 |
mcf1. |
|
| 366 |
mcf1.resetParams().upperMap(u).costMap(c).supplyMap(s5); |
|
| 367 | 367 |
checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s5, |
| ... | ... |
@@ -382,3 +382,3 @@ |
| 382 | 382 |
mcf2.OPTIMAL, true, -40000, test_str + "-14"); |
| 383 |
mcf2. |
|
| 383 |
mcf2.resetParams().lowerMap(neg1_l2).costMap(neg1_c).supplyMap(neg1_s); |
|
| 384 | 384 |
checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l2, neg1_u1, neg1_c, neg1_s, |
0 comments (0 inline)