286 IntVector _bucket_next; |
285 IntVector _bucket_next; |
287 IntVector _bucket_prev; |
286 IntVector _bucket_prev; |
288 IntVector _rank; |
287 IntVector _rank; |
289 int _max_rank; |
288 int _max_rank; |
290 |
289 |
291 // Data for a StaticDigraph structure |
|
292 typedef std::pair<int, int> IntPair; |
|
293 StaticDigraph _sgr; |
|
294 std::vector<IntPair> _arc_vec; |
|
295 std::vector<LargeCost> _cost_vec; |
|
296 LargeCostArcMap _cost_map; |
|
297 LargeCostNodeMap _pi_map; |
|
298 |
|
299 public: |
290 public: |
300 |
291 |
301 /// \brief Constant for infinite upper bounds (capacities). |
292 /// \brief Constant for infinite upper bounds (capacities). |
302 /// |
293 /// |
303 /// Constant for infinite upper bounds (capacities). |
294 /// Constant for infinite upper bounds (capacities). |
340 /// The constructor of the class. |
331 /// The constructor of the class. |
341 /// |
332 /// |
342 /// \param graph The digraph the algorithm runs on. |
333 /// \param graph The digraph the algorithm runs on. |
343 CostScaling(const GR& graph) : |
334 CostScaling(const GR& graph) : |
344 _graph(graph), _node_id(graph), _arc_idf(graph), _arc_idb(graph), |
335 _graph(graph), _node_id(graph), _arc_idf(graph), _arc_idb(graph), |
345 _cost_map(_cost_vec), _pi_map(_pi), |
|
346 INF(std::numeric_limits<Value>::has_infinity ? |
336 INF(std::numeric_limits<Value>::has_infinity ? |
347 std::numeric_limits<Value>::infinity() : |
337 std::numeric_limits<Value>::infinity() : |
348 std::numeric_limits<Value>::max()) |
338 std::numeric_limits<Value>::max()) |
349 { |
339 { |
350 // Check the number types |
340 // Check the number types |
616 _res_cap.resize(_res_arc_num); |
606 _res_cap.resize(_res_arc_num); |
617 _cost.resize(_res_arc_num); |
607 _cost.resize(_res_arc_num); |
618 _pi.resize(_res_node_num); |
608 _pi.resize(_res_node_num); |
619 _excess.resize(_res_node_num); |
609 _excess.resize(_res_node_num); |
620 _next_out.resize(_res_node_num); |
610 _next_out.resize(_res_node_num); |
621 |
|
622 _arc_vec.reserve(_res_arc_num); |
|
623 _cost_vec.reserve(_res_arc_num); |
|
624 |
611 |
625 // Copy the graph |
612 // Copy the graph |
626 int i = 0, j = 0, k = 2 * _arc_num + _node_num; |
613 int i = 0, j = 0, k = 2 * _arc_num + _node_num; |
627 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { |
614 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { |
628 _node_id[n] = i; |
615 _node_id[n] = i; |
921 case PARTIAL_AUGMENT: |
908 case PARTIAL_AUGMENT: |
922 startAugment(MAX_PARTIAL_PATH_LENGTH); |
909 startAugment(MAX_PARTIAL_PATH_LENGTH); |
923 break; |
910 break; |
924 } |
911 } |
925 |
912 |
926 // Compute node potentials for the original costs |
913 // Compute node potentials (dual solution) |
927 _arc_vec.clear(); |
914 for (int i = 0; i != _res_node_num; ++i) { |
928 _cost_vec.clear(); |
915 _pi[i] = static_cast<Cost>(_pi[i] / (_res_node_num * _alpha)); |
929 for (int j = 0; j != _res_arc_num; ++j) { |
916 } |
930 if (_res_cap[j] > 0) { |
917 bool optimal = true; |
931 _arc_vec.push_back(IntPair(_source[j], _target[j])); |
918 for (int i = 0; optimal && i != _res_node_num; ++i) { |
932 _cost_vec.push_back(_scost[j]); |
919 LargeCost pi_i = _pi[i]; |
933 } |
920 int last_out = _first_out[i+1]; |
934 } |
921 for (int j = _first_out[i]; j != last_out; ++j) { |
935 _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end()); |
922 if (_res_cap[j] > 0 && _scost[j] + pi_i - _pi[_target[j]] < 0) { |
936 |
923 optimal = false; |
937 typename BellmanFord<StaticDigraph, LargeCostArcMap> |
924 break; |
938 ::template SetDistMap<LargeCostNodeMap>::Create bf(_sgr, _cost_map); |
925 } |
939 bf.distMap(_pi_map); |
926 } |
940 bf.init(0); |
927 } |
941 bf.start(); |
928 |
|
929 if (!optimal) { |
|
930 // Compute node potentials for the original costs with BellmanFord |
|
931 // (if it is necessary) |
|
932 typedef std::pair<int, int> IntPair; |
|
933 StaticDigraph sgr; |
|
934 std::vector<IntPair> arc_vec; |
|
935 std::vector<LargeCost> cost_vec; |
|
936 LargeCostArcMap cost_map(cost_vec); |
|
937 |
|
938 arc_vec.clear(); |
|
939 cost_vec.clear(); |
|
940 for (int j = 0; j != _res_arc_num; ++j) { |
|
941 if (_res_cap[j] > 0) { |
|
942 int u = _source[j], v = _target[j]; |
|
943 arc_vec.push_back(IntPair(u, v)); |
|
944 cost_vec.push_back(_scost[j] + _pi[u] - _pi[v]); |
|
945 } |
|
946 } |
|
947 sgr.build(_res_node_num, arc_vec.begin(), arc_vec.end()); |
|
948 |
|
949 typename BellmanFord<StaticDigraph, LargeCostArcMap>::Create |
|
950 bf(sgr, cost_map); |
|
951 bf.init(0); |
|
952 bf.start(); |
|
953 |
|
954 for (int i = 0; i != _res_node_num; ++i) { |
|
955 _pi[i] += bf.dist(sgr.node(i)); |
|
956 } |
|
957 } |
|
958 |
|
959 // Shift potentials to meet the requirements of the GEQ type |
|
960 // optimality conditions |
|
961 LargeCost max_pot = _pi[_root]; |
|
962 for (int i = 0; i != _res_node_num; ++i) { |
|
963 if (_pi[i] > max_pot) max_pot = _pi[i]; |
|
964 } |
|
965 if (max_pot != 0) { |
|
966 for (int i = 0; i != _res_node_num; ++i) { |
|
967 _pi[i] -= max_pot; |
|
968 } |
|
969 } |
942 |
970 |
943 // Handle non-zero lower bounds |
971 // Handle non-zero lower bounds |
944 if (_have_lower) { |
972 if (_have_lower) { |
945 int limit = _first_out[_root]; |
973 int limit = _first_out[_root]; |
946 for (int j = 0; j != limit; ++j) { |
974 for (int j = 0; j != limit; ++j) { |