Changes in lemon/network_simplex.h [840:2914b6f0fde0:830:75c97c3786d6] in lemon-main
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/network_simplex.h
r840 r830 165 165 166 166 typedef std::vector<int> IntVector; 167 typedef std::vector<char> CharVector; 167 168 typedef std::vector<Value> ValueVector; 168 169 typedef std::vector<Cost> CostVector; 169 typedef std::vector<char> BoolVector;170 // Note: vector<char> is used instead of vector<bool> for efficiency reasons171 170 172 171 // State constants for arcs … … 215 214 IntVector _last_succ; 216 215 IntVector _dirty_revs; 217 BoolVector _forward;218 BoolVector _state;216 CharVector _forward; 217 CharVector _state; 219 218 int _root; 220 219 … … 247 246 const IntVector &_target; 248 247 const CostVector &_cost; 249 const BoolVector &_state;248 const CharVector &_state; 250 249 const CostVector &_pi; 251 250 int &_in_arc; … … 268 267 bool findEnteringArc() { 269 268 Cost c; 270 for (int e = _next_arc; e !=_search_arc_num; ++e) {269 for (int e = _next_arc; e < _search_arc_num; ++e) { 271 270 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 272 271 if (c < 0) { … … 276 275 } 277 276 } 278 for (int e = 0; e !=_next_arc; ++e) {277 for (int e = 0; e < _next_arc; ++e) { 279 278 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 280 279 if (c < 0) { … … 299 298 const IntVector &_target; 300 299 const CostVector &_cost; 301 const BoolVector &_state;300 const CharVector &_state; 302 301 const CostVector &_pi; 303 302 int &_in_arc; … … 316 315 bool findEnteringArc() { 317 316 Cost c, min = 0; 318 for (int e = 0; e !=_search_arc_num; ++e) {317 for (int e = 0; e < _search_arc_num; ++e) { 319 318 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 320 319 if (c < min) { … … 338 337 const IntVector &_target; 339 338 const CostVector &_cost; 340 const BoolVector &_state;339 const CharVector &_state; 341 340 const CostVector &_pi; 342 341 int &_in_arc; … … 357 356 { 358 357 // The main parameters of the pivot rule 359 const double BLOCK_SIZE_FACTOR = 1.0;358 const double BLOCK_SIZE_FACTOR = 0.5; 360 359 const int MIN_BLOCK_SIZE = 10; 361 360 … … 370 369 int cnt = _block_size; 371 370 int e; 372 for (e = _next_arc; e !=_search_arc_num; ++e) {371 for (e = _next_arc; e < _search_arc_num; ++e) { 373 372 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 374 373 if (c < min) { … … 381 380 } 382 381 } 383 for (e = 0; e !=_next_arc; ++e) {382 for (e = 0; e < _next_arc; ++e) { 384 383 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 385 384 if (c < min) { … … 411 410 const IntVector &_target; 412 411 const CostVector &_cost; 413 const BoolVector &_state;412 const CharVector &_state; 414 413 const CostVector &_pi; 415 414 int &_in_arc; … … 472 471 min = 0; 473 472 _curr_length = 0; 474 for (e = _next_arc; e !=_search_arc_num; ++e) {473 for (e = _next_arc; e < _search_arc_num; ++e) { 475 474 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 476 475 if (c < 0) { … … 483 482 } 484 483 } 485 for (e = 0; e !=_next_arc; ++e) {484 for (e = 0; e < _next_arc; ++e) { 486 485 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 487 486 if (c < 0) { … … 514 513 const IntVector &_target; 515 514 const CostVector &_cost; 516 const BoolVector &_state;515 const CharVector &_state; 517 516 const CostVector &_pi; 518 517 int &_in_arc; … … 567 566 // Check the current candidate list 568 567 int e; 569 for (int i = 0; i !=_curr_length; ++i) {568 for (int i = 0; i < _curr_length; ++i) { 570 569 e = _candidates[i]; 571 570 _cand_cost[e] = _state[e] * … … 580 579 int limit = _head_length; 581 580 582 for (e = _next_arc; e !=_search_arc_num; ++e) {581 for (e = _next_arc; e < _search_arc_num; ++e) { 583 582 _cand_cost[e] = _state[e] * 584 583 (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); … … 592 591 } 593 592 } 594 for (e = 0; e !=_next_arc; ++e) {593 for (e = 0; e < _next_arc; ++e) { 595 594 _cand_cost[e] = _state[e] * 596 595 (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); … … 1362 1361 1363 1362 // Update _rev_thread using the new _thread values 1364 for (int i = 0; i !=int(_dirty_revs.size()); ++i) {1363 for (int i = 0; i < int(_dirty_revs.size()); ++i) { 1365 1364 u = _dirty_revs[i]; 1366 1365 _rev_thread[_thread[u]] = u; … … 1432 1431 _pi[u] += sigma; 1433 1432 } 1434 }1435 1436 // Heuristic initial pivots1437 bool initialPivots() {1438 Value curr, total = 0;1439 std::vector<Node> supply_nodes, demand_nodes;1440 for (NodeIt u(_graph); u != INVALID; ++u) {1441 curr = _supply[_node_id[u]];1442 if (curr > 0) {1443 total += curr;1444 supply_nodes.push_back(u);1445 }1446 else if (curr < 0) {1447 demand_nodes.push_back(u);1448 }1449 }1450 if (_sum_supply > 0) total -= _sum_supply;1451 if (total <= 0) return true;1452 1453 IntVector arc_vector;1454 if (_sum_supply >= 0) {1455 if (supply_nodes.size() == 1 && demand_nodes.size() == 1) {1456 // Perform a reverse graph search from the sink to the source1457 typename GR::template NodeMap<bool> reached(_graph, false);1458 Node s = supply_nodes[0], t = demand_nodes[0];1459 std::vector<Node> stack;1460 reached[t] = true;1461 stack.push_back(t);1462 while (!stack.empty()) {1463 Node u, v = stack.back();1464 stack.pop_back();1465 if (v == s) break;1466 for (InArcIt a(_graph, v); a != INVALID; ++a) {1467 if (reached[u = _graph.source(a)]) continue;1468 int j = _arc_id[a];1469 if (_cap[j] >= total) {1470 arc_vector.push_back(j);1471 reached[u] = true;1472 stack.push_back(u);1473 }1474 }1475 }1476 } else {1477 // Find the min. cost incomming arc for each demand node1478 for (int i = 0; i != int(demand_nodes.size()); ++i) {1479 Node v = demand_nodes[i];1480 Cost c, min_cost = std::numeric_limits<Cost>::max();1481 Arc min_arc = INVALID;1482 for (InArcIt a(_graph, v); a != INVALID; ++a) {1483 c = _cost[_arc_id[a]];1484 if (c < min_cost) {1485 min_cost = c;1486 min_arc = a;1487 }1488 }1489 if (min_arc != INVALID) {1490 arc_vector.push_back(_arc_id[min_arc]);1491 }1492 }1493 }1494 } else {1495 // Find the min. cost outgoing arc for each supply node1496 for (int i = 0; i != int(supply_nodes.size()); ++i) {1497 Node u = supply_nodes[i];1498 Cost c, min_cost = std::numeric_limits<Cost>::max();1499 Arc min_arc = INVALID;1500 for (OutArcIt a(_graph, u); a != INVALID; ++a) {1501 c = _cost[_arc_id[a]];1502 if (c < min_cost) {1503 min_cost = c;1504 min_arc = a;1505 }1506 }1507 if (min_arc != INVALID) {1508 arc_vector.push_back(_arc_id[min_arc]);1509 }1510 }1511 }1512 1513 // Perform heuristic initial pivots1514 for (int i = 0; i != int(arc_vector.size()); ++i) {1515 in_arc = arc_vector[i];1516 if (_state[in_arc] * (_cost[in_arc] + _pi[_source[in_arc]] -1517 _pi[_target[in_arc]]) >= 0) continue;1518 findJoinNode();1519 bool change = findLeavingArc();1520 if (delta >= MAX) return false;1521 changeFlow(change);1522 if (change) {1523 updateTreeStructure();1524 updatePotential();1525 }1526 }1527 return true;1528 1433 } 1529 1434 … … 1550 1455 PivotRuleImpl pivot(*this); 1551 1456 1552 // Perform heuristic initial pivots1553 if (!initialPivots()) return UNBOUNDED;1554 1555 1457 // Execute the Network Simplex algorithm 1556 1458 while (pivot.findEnteringArc()) {
Note: See TracChangeset
for help on using the changeset viewer.