Heuristic initial pivots
| 1454 | |
| 1455 | // Heuristic initial pivots |
| 1456 | bool initialPivots() { |
| 1457 | Value curr, total = 0; |
| 1458 | std::vector<Node> supply_nodes, demand_nodes; |
| 1459 | Node u; _graph.first(u); |
| 1460 | for (; u != INVALIDNODE; _graph.next(u)) { |
| 1461 | curr = _supply[_node_id(u)]; |
| 1462 | if (curr > 0) { |
| 1463 | total += curr; |
| 1464 | supply_nodes.push_back(u); |
| 1465 | } else if (curr < 0) { |
| 1466 | demand_nodes.push_back(u); |
| 1467 | } |
| 1468 | } |
| 1469 | if (_sum_supply > 0) total -= _sum_supply; |
| 1470 | if (total <= 0) return true; |
| 1471 | |
| 1472 | ArcVector arc_vector; |
| 1473 | if (_sum_supply >= 0) { |
| 1474 | if (supply_nodes.size() == 1 && demand_nodes.size() == 1) { |
| 1475 | // Perform a reverse graph search from the sink to the source |
| 1476 | //typename GR::template NodeMap<bool> reached(_graph, false); |
| 1477 | BoolVector reached(_node_num, false); |
| 1478 | Node s = supply_nodes[0], t = demand_nodes[0]; |
| 1479 | std::vector<Node> stack; |
| 1480 | reached[t] = true; |
| 1481 | stack.push_back(t); |
| 1482 | while (!stack.empty()) { |
| 1483 | Node u, v = stack.back(); |
| 1484 | stack.pop_back(); |
| 1485 | if (v == s) break; |
| 1486 | Arc a; _graph.firstIn(a, v); |
| 1487 | for (; a != INVALID; _graph.nextIn(a)) { |
| 1488 | if (reached[u = _graph.source(a)]) continue; |
| 1489 | ArcsType j = getArcID(a); |
| 1490 | arc_vector.push_back(j); |
| 1491 | reached[u] = true; |
| 1492 | stack.push_back(u); |
| 1493 | } |
| 1494 | } |
| 1495 | } else { |
| 1496 | arc_vector.resize(demand_nodes.size()); |
| 1497 | // Find the min. cost incomming arc for each demand node |
| 1498 | #pragma omp parallel for |
| 1499 | for (int i = 0; i < demand_nodes.size(); ++i) { |
| 1500 | Node v = demand_nodes[i]; |
| 1501 | Cost min_cost = std::numeric_limits<Cost>::max(); |
| 1502 | Arc min_arc = INVALID; |
| 1503 | Arc a; _graph.firstIn(a, v); |
| 1504 | for (; a != INVALID; _graph.nextIn(a)) { |
| 1505 | Cost c = _cost[getArcID(a)]; |
| 1506 | if (c < min_cost) { |
| 1507 | min_cost = c; |
| 1508 | min_arc = a; |
| 1509 | } |
| 1510 | } |
| 1511 | arc_vector[i] = getArcID(min_arc); |
| 1512 | } |
| 1513 | arc_vector.erase(std::remove(arc_vector.begin(), arc_vector.end(), INVALID), arc_vector.end()); |