r896:fb932bcfd803
Sat, 04 Sep 2010 23:58:03
[Not Reviewed]
0 comments (0 inline)
0
1
0
| ... | ... |
@@ -627,29 +627,30 @@ |
| 627 | 627 |
return true; |
| 628 | 628 |
} |
| 629 | 629 |
|
| 630 | 630 |
}; //class AlteringListPivotRule |
| 631 | 631 |
|
| 632 | 632 |
public: |
| 633 | 633 |
|
| 634 | 634 |
/// \brief Constructor. |
| 635 | 635 |
/// |
| 636 | 636 |
/// The constructor of the class. |
| 637 | 637 |
/// |
| 638 | 638 |
/// \param graph The digraph the algorithm runs on. |
| 639 |
/// \param arc_mixing Indicate if the arcs |
|
| 639 |
/// \param arc_mixing Indicate if the arcs will be stored in a |
|
| 640 | 640 |
/// mixed order in the internal data structure. |
| 641 |
/// In special cases, it could lead to better overall performance, |
|
| 642 |
/// but it is usually slower. Therefore it is disabled by default. |
|
| 643 |
|
|
| 641 |
/// In general, it leads to similar performance as using the original |
|
| 642 |
/// arc order, but it makes the algorithm more robust and in special |
|
| 643 |
/// cases, even significantly faster. Therefore, it is enabled by default. |
|
| 644 |
NetworkSimplex(const GR& graph, bool arc_mixing = true) : |
|
| 644 | 645 |
_graph(graph), _node_id(graph), _arc_id(graph), |
| 645 | 646 |
_arc_mixing(arc_mixing), |
| 646 | 647 |
MAX(std::numeric_limits<Value>::max()), |
| 647 | 648 |
INF(std::numeric_limits<Value>::has_infinity ? |
| 648 | 649 |
std::numeric_limits<Value>::infinity() : MAX) |
| 649 | 650 |
{
|
| 650 | 651 |
// Check the number types |
| 651 | 652 |
LEMON_ASSERT(std::numeric_limits<Value>::is_signed, |
| 652 | 653 |
"The flow type of NetworkSimplex must be signed"); |
| 653 | 654 |
LEMON_ASSERT(std::numeric_limits<Cost>::is_signed, |
| 654 | 655 |
"The cost type of NetworkSimplex must be signed"); |
| 655 | 656 |
|
| ... | ... |
@@ -921,31 +922,31 @@ |
| 921 | 922 |
_rev_thread.resize(all_node_num); |
| 922 | 923 |
_succ_num.resize(all_node_num); |
| 923 | 924 |
_last_succ.resize(all_node_num); |
| 924 | 925 |
_state.resize(max_arc_num); |
| 925 | 926 |
|
| 926 | 927 |
// Copy the graph |
| 927 | 928 |
int i = 0; |
| 928 | 929 |
for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
|
| 929 | 930 |
_node_id[n] = i; |
| 930 | 931 |
} |
| 931 | 932 |
if (_arc_mixing) {
|
| 932 | 933 |
// Store the arcs in a mixed order |
| 933 |
int |
|
| 934 |
const int skip = std::max(_arc_num / _node_num, 3); |
|
| 934 | 935 |
int i = 0, j = 0; |
| 935 | 936 |
for (ArcIt a(_graph); a != INVALID; ++a) {
|
| 936 | 937 |
_arc_id[a] = i; |
| 937 | 938 |
_source[i] = _node_id[_graph.source(a)]; |
| 938 | 939 |
_target[i] = _node_id[_graph.target(a)]; |
| 939 |
if ((i += |
|
| 940 |
if ((i += skip) >= _arc_num) i = ++j; |
|
| 940 | 941 |
} |
| 941 | 942 |
} else {
|
| 942 | 943 |
// Store the arcs in the original order |
| 943 | 944 |
int i = 0; |
| 944 | 945 |
for (ArcIt a(_graph); a != INVALID; ++a, ++i) {
|
| 945 | 946 |
_arc_id[a] = i; |
| 946 | 947 |
_source[i] = _node_id[_graph.source(a)]; |
| 947 | 948 |
_target[i] = _node_id[_graph.target(a)]; |
| 948 | 949 |
} |
| 949 | 950 |
} |
| 950 | 951 |
|
| 951 | 952 |
// Reset parameters |
0 comments (0 inline)