Changeset 956:141f9c0db4a3 in lemon for lemon/cycle_canceling.h
- Timestamp:
- 03/06/10 15:35:12 (14 years ago)
- Branch:
- default
- Children:
- 957:f802439d2b58, 959:38213abd2911, 1041:f112c18bc304
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/cycle_canceling.h
r942 r956 1 /* -*- C++-*-1 /* -*- mode: C++; indent-tabs-mode: nil; -*- 2 2 * 3 * This file is a part of LEMON, a generic C++ optimization library 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 085 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 143 143 144 144 TEMPLATE_DIGRAPH_TYPEDEFS(GR); 145 145 146 146 typedef std::vector<int> IntVector; 147 147 typedef std::vector<double> DoubleVector; … … 152 152 153 153 private: 154 154 155 155 template <typename KT, typename VT> 156 156 class StaticVectorMap { … … 158 158 typedef KT Key; 159 159 typedef VT Value; 160 160 161 161 StaticVectorMap(std::vector<Value>& v) : _v(v) {} 162 162 163 163 const Value& operator[](const Key& key) const { 164 164 return _v[StaticDigraph::id(key)]; … … 168 168 return _v[StaticDigraph::id(key)]; 169 169 } 170 170 171 171 void set(const Key& key, const Value& val) { 172 172 _v[StaticDigraph::id(key)] = val; … … 222 222 CostArcMap _cost_map; 223 223 CostNodeMap _pi_map; 224 224 225 225 public: 226 226 227 227 /// \brief Constant for infinite upper bounds (capacities). 228 228 /// … … 367 367 return *this; 368 368 } 369 369 370 370 /// @} 371 371 … … 467 467 _cost[j] = 0; 468 468 _cost[_reverse[j]] = 0; 469 } 469 } 470 470 _have_lower = false; 471 471 return *this; … … 509 509 _cost.resize(_res_arc_num); 510 510 _supply.resize(_res_node_num); 511 511 512 512 _res_cap.resize(_res_arc_num); 513 513 _pi.resize(_res_node_num); … … 555 555 _reverse[bi] = fi; 556 556 } 557 557 558 558 // Reset parameters 559 559 resetParams(); … … 664 664 } 665 665 if (_sum_supply > 0) return INFEASIBLE; 666 666 667 667 668 668 // Initialize vectors … … 671 671 } 672 672 ValueVector excess(_supply); 673 673 674 674 // Remove infinite upper bounds and check negative arcs 675 675 const Value MAX = std::numeric_limits<Value>::max(); … … 771 771 } 772 772 } 773 773 774 774 return OPTIMAL; 775 775 } 776 776 777 777 // Build a StaticDigraph structure containing the current 778 778 // residual network … … 830 830 const int BF_FIRST_LIMIT = 2; 831 831 const double BF_LIMIT_FACTOR = 1.5; 832 832 833 833 typedef StaticVectorMap<StaticDigraph::Arc, Value> FilterMap; 834 834 typedef FilterArcs<StaticDigraph, FilterMap> ResDigraph; … … 837 837 ::template SetDistMap<CostNodeMap> 838 838 ::template SetPredMap<PredMap>::Create BF; 839 839 840 840 // Build the residual network 841 841 _arc_vec.clear(); … … 927 927 typedef typename HowardMmc<StaticDigraph, CostArcMap> 928 928 ::template SetPath<SPath>::Create MMC; 929 929 930 930 SPath cycle; 931 931 MMC mmc(_sgr, _cost_map); … … 950 950 } 951 951 952 // Rebuild the residual network 952 // Rebuild the residual network 953 953 buildResidualNetwork(); 954 954 } … … 1144 1144 Cost cycle_cost = mmc.cycleCost(); 1145 1145 int cycle_size = mmc.cycleSize(); 1146 1146 1147 1147 // Compute feasible potentials for the current epsilon 1148 1148 for (int i = 0; i != int(_cost_vec.size()); ++i) { … … 1156 1156 pi[u] = static_cast<double>(_pi[u]) / cycle_size; 1157 1157 } 1158 1158 1159 1159 iter = limit; 1160 1160 }
Note: See TracChangeset
for help on using the changeset viewer.