Changeset 2638:61bf01404ede in lemon0.x for lemon/network_simplex.h
 Timestamp:
 06/04/09 03:19:06 (10 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@3523
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/network_simplex.h
r2635 r2638 242 242 _edge(ns._edge), _source(ns._source), _target(ns._target), 243 243 _cost(ns._cost), _state(ns._state), _pi(ns._pi), 244 _in_edge(ns._in_edge), _edge_num(ns._edge_num + ns._node_num), _next_edge(0)244 _in_edge(ns._in_edge), _edge_num(ns._edge_num), _next_edge(0) 245 245 { 246 246 // The main parameters of the pivot rule 247 const double BLOCK_SIZE_FACTOR = 2.0;247 const double BLOCK_SIZE_FACTOR = 0.5; 248 248 const int MIN_BLOCK_SIZE = 10; 249 249 … … 256 256 Cost c, min = 0; 257 257 int cnt = _block_size; 258 int e , min_edge = _next_edge;258 int e; 259 259 for (e = _next_edge; e < _edge_num; ++e) { 260 260 c = _state[e] * (_cost[e] + _pi[_source[e]]  _pi[_target[e]]); 261 261 if (c < min) { 262 262 min = c; 263 min_edge = e;263 _in_edge = e; 264 264 } 265 265 if (cnt == 0) { 266 if (min < 0) break;266 if (min < 0) goto search_end; 267 267 cnt = _block_size; 268 268 } 269 269 } 270 if (min == 0  cnt > 0) { 271 for (e = 0; e < _next_edge; ++e) { 272 c = _state[e] * (_cost[e] + _pi[_source[e]]  _pi[_target[e]]); 273 if (c < min) { 274 min = c; 275 min_edge = e; 276 } 277 if (cnt == 0) { 278 if (min < 0) break; 279 cnt = _block_size; 280 } 270 for (e = 0; e < _next_edge; ++e) { 271 c = _state[e] * (_cost[e] + _pi[_source[e]]  _pi[_target[e]]); 272 if (c < min) { 273 min = c; 274 _in_edge = e; 275 } 276 if (cnt == 0) { 277 if (min < 0) goto search_end; 278 cnt = _block_size; 281 279 } 282 280 } 283 281 if (min >= 0) return false; 284 _in_edge = min_edge; 282 283 search_end: 285 284 _next_edge = e; 286 285 return true; … … 326 325 { 327 326 // The main parameters of the pivot rule 328 const double LIST_LENGTH_FACTOR = 1.0;327 const double LIST_LENGTH_FACTOR = 0.25; 329 328 const int MIN_LIST_LENGTH = 10; 330 329 const double MINOR_LIMIT_FACTOR = 0.1; … … 342 341 bool findEnteringEdge() { 343 342 Cost min, c; 344 int e , min_edge = _next_edge;343 int e; 345 344 if (_curr_length > 0 && _minor_count < _minor_limit) { 346 345 // Minor iteration: select the best eligible edge from the … … 353 352 if (c < min) { 354 353 min = c; 355 min_edge = e;354 _in_edge = e; 356 355 } 357 if (c >= 0) {356 else if (c >= 0) { 358 357 _candidates[i] = _candidates[_curr_length]; 359 358 } 360 359 } 361 if (min < 0) { 362 _in_edge = min_edge; 363 return true; 364 } 360 if (min < 0) return true; 365 361 } 366 362 … … 374 370 if (c < min) { 375 371 min = c; 376 min_edge = e;372 _in_edge = e; 377 373 } 378 if (_curr_length == _list_length) break; 379 } 380 } 381 if (_curr_length < _list_length) { 382 for (e = 0; e < _next_edge; ++e) { 383 c = _state[e] * (_cost[e] + _pi[_source[e]]  _pi[_target[e]]); 384 if (c < 0) { 385 _candidates[_curr_length++] = e; 386 if (c < min) { 387 min = c; 388 min_edge = e; 389 } 390 if (_curr_length == _list_length) break; 374 if (_curr_length == _list_length) goto search_end; 375 } 376 } 377 for (e = 0; e < _next_edge; ++e) { 378 c = _state[e] * (_cost[e] + _pi[_source[e]]  _pi[_target[e]]); 379 if (c < 0) { 380 _candidates[_curr_length++] = e; 381 if (c < min) { 382 min = c; 383 _in_edge = e; 391 384 } 385 if (_curr_length == _list_length) goto search_end; 392 386 } 393 387 } 394 388 if (_curr_length == 0) return false; 389 390 search_end: 395 391 _minor_count = 1; 396 _in_edge = min_edge;397 392 _next_edge = e; 398 393 return true; … … 452 447 { 453 448 // The main parameters of the pivot rule 454 const double BLOCK_SIZE_FACTOR = 1. 5;449 const double BLOCK_SIZE_FACTOR = 1.0; 455 450 const int MIN_BLOCK_SIZE = 10; 456 451 const double HEAD_LENGTH_FACTOR = 0.1; … … 480 475 // Extend the list 481 476 int cnt = _block_size; 482 int last_edge = 0;483 477 int limit = _head_length; 484 478 485 for ( inte = _next_edge; e < _edge_num; ++e) {479 for (e = _next_edge; e < _edge_num; ++e) { 486 480 _cand_cost[e] = _state[e] * 487 481 (_cost[e] + _pi[_source[e]]  _pi[_target[e]]); 488 482 if (_cand_cost[e] < 0) { 489 483 _candidates[_curr_length++] = e; 490 last_edge = e;491 484 } 492 485 if (cnt == 0) { 493 if (_curr_length > limit) break;486 if (_curr_length > limit) goto search_end; 494 487 limit = 0; 495 488 cnt = _block_size; 496 489 } 497 490 } 498 if (_curr_length <= limit) { 499 for (int e = 0; e < _next_edge; ++e) { 500 _cand_cost[e] = _state[e] * 501 (_cost[e] + _pi[_source[e]]  _pi[_target[e]]); 502 if (_cand_cost[e] < 0) { 503 _candidates[_curr_length++] = e; 504 last_edge = e; 505 } 506 if (cnt == 0) { 507 if (_curr_length > limit) break; 508 limit = 0; 509 cnt = _block_size; 510 } 491 for (e = 0; e < _next_edge; ++e) { 492 _cand_cost[e] = _state[e] * 493 (_cost[e] + _pi[_source[e]]  _pi[_target[e]]); 494 if (_cand_cost[e] < 0) { 495 _candidates[_curr_length++] = e; 496 } 497 if (cnt == 0) { 498 if (_curr_length > limit) goto search_end; 499 limit = 0; 500 cnt = _block_size; 511 501 } 512 502 } 513 503 if (_curr_length == 0) return false; 514 _next_edge = last_edge + 1; 504 505 search_end: 515 506 516 507 // Make heap of the candidate list (approximating a partial sort) … … 520 511 // Pop the first element of the heap 521 512 _in_edge = _candidates[0]; 513 _next_edge = e; 522 514 pop_heap( _candidates.begin(), _candidates.begin() + _curr_length, 523 515 _sort_func ); … … 932 924 _pi[_root] = 0; 933 925 934 // Store the edges in a mixed order 935 int k = std::max(int(sqrt(_edge_num)), 10); 926 // Store the edges 936 927 int i = 0; 937 928 for (EdgeIt e(_orig_graph); e != INVALID; ++e) { 938 _edge[i] = e; 939 if ((i += k) >= _edge_num) i = (i % k) + 1; 929 _edge[i++] = e; 940 930 } 941 931 … … 962 952 963 953 // Add artificial edges and initialize the spanning tree data structure 964 Cost max_cost = std::numeric_limits<Cost>::max() / 4;954 Cost max_cost = std::numeric_limits<Cost>::max() / 2 + 1; 965 955 Capacity max_cap = std::numeric_limits<Capacity>::max(); 966 956 for (int u = 0, e = _edge_num; u != _node_num; ++u, ++e) {
Note: See TracChangeset
for help on using the changeset viewer.