r775:e2bdd1a988f3
Thu, 02 Jul 2009 17:36:29
[Not Reviewed]
0 comments (0 inline)
0
1
0
| ... | ... |
@@ -622,13 +622,17 @@ |
| 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 |
| ... | ... |
@@ -660,24 +664,35 @@ |
| 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 |
} |
0 comments (0 inline)