r775:e2bdd1a988f3
Thu, 02 Jul 2009 17:36:29
[Not Reviewed]
0 comments (0 inline)
0
1
0
| ... | ... |
@@ -626,5 +626,9 @@ |
| 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 ? |
| ... | ... |
@@ -664,16 +668,27 @@ |
| 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 |
|
0 comments (0 inline)