Changeset 1048:1226290a9b7d in lemon for lemon
 Timestamp:
 03/15/11 19:52:31 (9 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/cost_scaling.h
r1047 r1048 238 238 }; 239 239 240 typedef StaticVectorMap<StaticDigraph::Node, LargeCost> LargeCostNodeMap;241 240 typedef StaticVectorMap<StaticDigraph::Arc, LargeCost> LargeCostArcMap; 242 241 … … 289 288 int _max_rank; 290 289 291 // Data for a StaticDigraph structure292 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 290 public: 300 291 … … 343 334 CostScaling(const GR& graph) : 344 335 _graph(graph), _node_id(graph), _arc_idf(graph), _arc_idb(graph), 345 _cost_map(_cost_vec), _pi_map(_pi),346 336 INF(std::numeric_limits<Value>::has_infinity ? 347 337 std::numeric_limits<Value>::infinity() : … … 619 609 _excess.resize(_res_node_num); 620 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 612 // Copy the graph … … 924 911 } 925 912 926 // Compute node potentials for the original costs 927 _arc_vec.clear(); 928 _cost_vec.clear(); 929 for (int j = 0; j != _res_arc_num; ++j) { 930 if (_res_cap[j] > 0) { 931 _arc_vec.push_back(IntPair(_source[j], _target[j])); 932 _cost_vec.push_back(_scost[j]); 933 } 934 } 935 _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end()); 936 937 typename BellmanFord<StaticDigraph, LargeCostArcMap> 938 ::template SetDistMap<LargeCostNodeMap>::Create bf(_sgr, _cost_map); 939 bf.distMap(_pi_map); 940 bf.init(0); 941 bf.start(); 913 // Compute node potentials (dual solution) 914 for (int i = 0; i != _res_node_num; ++i) { 915 _pi[i] = static_cast<Cost>(_pi[i] / (_res_node_num * _alpha)); 916 } 917 bool optimal = true; 918 for (int i = 0; optimal && i != _res_node_num; ++i) { 919 LargeCost pi_i = _pi[i]; 920 int last_out = _first_out[i+1]; 921 for (int j = _first_out[i]; j != last_out; ++j) { 922 if (_res_cap[j] > 0 && _scost[j] + pi_i  _pi[_target[j]] < 0) { 923 optimal = false; 924 break; 925 } 926 } 927 } 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 971 // Handle nonzero lower bounds
Note: See TracChangeset
for help on using the changeset viewer.