r775:e2bdd1a988f3
Thu, 02 Jul 2009 17:36:29
[Not Reviewed]
0 comments (0 inline)
0
1
0
| ... | ... |
@@ -616,25 +616,29 @@ |
| 616 | 616 |
return true; |
| 617 | 617 |
} |
| 618 | 618 |
|
| 619 | 619 |
}; //class AlteringListPivotRule |
| 620 | 620 |
|
| 621 | 621 |
public: |
| 622 | 622 |
|
| 623 | 623 |
/// \brief Constructor. |
| 624 | 624 |
/// |
| 625 | 625 |
/// The constructor of the class. |
| 626 | 626 |
/// |
| 627 | 627 |
/// \param graph The digraph the algorithm runs on. |
| 628 |
|
|
| 628 |
/// \param arc_mixing Indicate if the arcs have to be stored in a |
|
| 629 |
/// mixed order in the internal data structure. |
|
| 630 |
/// In special cases, it could lead to better overall performance, |
|
| 631 |
/// but it is usually slower. Therefore it is disabled by default. |
|
| 632 |
NetworkSimplex(const GR& graph, bool arc_mixing = false) : |
|
| 629 | 633 |
_graph(graph), _node_id(graph), _arc_id(graph), |
| 630 | 634 |
INF(std::numeric_limits<Value>::has_infinity ? |
| 631 | 635 |
std::numeric_limits<Value>::infinity() : |
| 632 | 636 |
std::numeric_limits<Value>::max()) |
| 633 | 637 |
{
|
| 634 | 638 |
// Check the value types |
| 635 | 639 |
LEMON_ASSERT(std::numeric_limits<Value>::is_signed, |
| 636 | 640 |
"The flow type of NetworkSimplex must be signed"); |
| 637 | 641 |
LEMON_ASSERT(std::numeric_limits<Cost>::is_signed, |
| 638 | 642 |
"The cost type of NetworkSimplex must be signed"); |
| 639 | 643 |
|
| 640 | 644 |
// Resize vectors |
| ... | ... |
@@ -654,36 +658,47 @@ |
| 654 | 658 |
_flow.resize(max_arc_num); |
| 655 | 659 |
_pi.resize(all_node_num); |
| 656 | 660 |
|
| 657 | 661 |
_parent.resize(all_node_num); |
| 658 | 662 |
_pred.resize(all_node_num); |
| 659 | 663 |
_forward.resize(all_node_num); |
| 660 | 664 |
_thread.resize(all_node_num); |
| 661 | 665 |
_rev_thread.resize(all_node_num); |
| 662 | 666 |
_succ_num.resize(all_node_num); |
| 663 | 667 |
_last_succ.resize(all_node_num); |
| 664 | 668 |
_state.resize(max_arc_num); |
| 665 | 669 |
|
| 666 |
// Copy the graph |
|
| 670 |
// Copy the graph |
|
| 667 | 671 |
int i = 0; |
| 668 | 672 |
for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
|
| 669 | 673 |
_node_id[n] = i; |
| 670 | 674 |
} |
| 671 |
int k = std::max(int(std::sqrt(double(_arc_num))), 10); |
|
| 672 |
i = 0; |
|
| 673 |
for (ArcIt a(_graph); a != INVALID; ++a) {
|
|
| 674 |
_arc_id[a] = i; |
|
| 675 |
_source[i] = _node_id[_graph.source(a)]; |
|
| 676 |
_target[i] = _node_id[_graph.target(a)]; |
|
| 677 |
|
|
| 675 |
if (arc_mixing) {
|
|
| 676 |
// Store the arcs in a mixed order |
|
| 677 |
int k = std::max(int(std::sqrt(double(_arc_num))), 10); |
|
| 678 |
int i = 0, j = 0; |
|
| 679 |
for (ArcIt a(_graph); a != INVALID; ++a) {
|
|
| 680 |
_arc_id[a] = i; |
|
| 681 |
_source[i] = _node_id[_graph.source(a)]; |
|
| 682 |
_target[i] = _node_id[_graph.target(a)]; |
|
| 683 |
if ((i += k) >= _arc_num) i = ++j; |
|
| 684 |
} |
|
| 685 |
} else {
|
|
| 686 |
// Store the arcs in the original order |
|
| 687 |
int i = 0; |
|
| 688 |
for (ArcIt a(_graph); a != INVALID; ++a, ++i) {
|
|
| 689 |
_arc_id[a] = i; |
|
| 690 |
_source[i] = _node_id[_graph.source(a)]; |
|
| 691 |
_target[i] = _node_id[_graph.target(a)]; |
|
| 692 |
} |
|
| 678 | 693 |
} |
| 679 | 694 |
|
| 680 | 695 |
// Initialize maps |
| 681 | 696 |
for (int i = 0; i != _node_num; ++i) {
|
| 682 | 697 |
_supply[i] = 0; |
| 683 | 698 |
} |
| 684 | 699 |
for (int i = 0; i != _arc_num; ++i) {
|
| 685 | 700 |
_lower[i] = 0; |
| 686 | 701 |
_upper[i] = INF; |
| 687 | 702 |
_cost[i] = 1; |
| 688 | 703 |
} |
| 689 | 704 |
_have_lower = false; |
0 comments (0 inline)