Heuristic initial pivots
| 1316 | |
| 1317 | // Heuristic initial pivots |
| 1318 | bool initialPivots() { |
| 1319 | Value curr, total = 0; |
| 1320 | std::vector<Node> supply_nodes, demand_nodes; |
| 1321 | Node u; _graph.first(u); |
| 1322 | for (; u != INVALIDNODE; _graph.next(u)) { |
| 1323 | curr = _supply[_node_id(u)]; |
| 1324 | if (curr > 0) { |
| 1325 | total += curr; |
| 1326 | supply_nodes.push_back(u); |
| 1327 | } |
| 1328 | else if (curr < 0) { |
| 1329 | demand_nodes.push_back(u); |
| 1330 | } |
| 1331 | } |
| 1332 | if (_sum_supply > 0) total -= _sum_supply; |
| 1333 | if (total <= 0) return true; |
| 1334 | |
| 1335 | ArcVector arc_vector; |
| 1336 | if (_sum_supply >= 0) { |
| 1337 | if (supply_nodes.size() == 1 && demand_nodes.size() == 1) { |
| 1338 | // Perform a reverse graph search from the sink to the source |
| 1339 | //typename GR::template NodeMap<bool> reached(_graph, false); |
| 1340 | BoolVector reached(_node_num, false); |
| 1341 | Node s = supply_nodes[0], t = demand_nodes[0]; |
| 1342 | std::vector<Node> stack; |
| 1343 | reached[t] = true; |
| 1344 | stack.push_back(t); |
| 1345 | while (!stack.empty()) { |
| 1346 | Node u, v = stack.back(); |
| 1347 | stack.pop_back(); |
| 1348 | if (v == s) break; |
| 1349 | Arc a; _graph.firstIn(a, v); |
| 1350 | for (; a != INVALID; _graph.nextIn(a)) { |
| 1351 | if (reached[u = _graph.source(a)]) continue; |
| 1352 | ArcsType j = getArcID(a); |
| 1353 | if (INF >= total) { |
| 1354 | arc_vector.push_back(j); |
| 1355 | reached[u] = true; |
| 1356 | stack.push_back(u); |
| 1357 | } |
| 1358 | } |
| 1359 | } |
| 1360 | } else { |
| 1361 | // Find the min. cost incomming arc for each demand node |
| 1362 | for (int i = 0; i != demand_nodes.size(); ++i) { |
| 1363 | Node v = demand_nodes[i]; |
| 1364 | Cost c, min_cost = std::numeric_limits<Cost>::max(); |
| 1365 | Arc min_arc = INVALID; |
| 1366 | Arc a; _graph.firstIn(a, v); |
| 1367 | for (; a != INVALID; _graph.nextIn(a)) { |
| 1368 | c = _cost[getArcID(a)]; |
| 1369 | if (c < min_cost) { |
| 1370 | min_cost = c; |
| 1371 | min_arc = a; |
| 1372 | } |
| 1373 | } |
| 1374 | if (min_arc != INVALID) { |
| 1375 | arc_vector.push_back(getArcID(min_arc)); |