1.1 --- a/lemon/cycle_canceling.h Wed Mar 17 12:35:52 2010 +0100
1.2 +++ b/lemon/cycle_canceling.h Sat Mar 06 14:35:12 2010 +0000
1.3 @@ -1,8 +1,8 @@
1.4 -/* -*- C++ -*-
1.5 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.6 *
1.7 - * This file is a part of LEMON, a generic C++ optimization library
1.8 + * This file is a part of LEMON, a generic C++ optimization library.
1.9 *
1.10 - * Copyright (C) 2003-2008
1.11 + * Copyright (C) 2003-2010
1.12 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.13 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.14 *
1.15 @@ -142,7 +142,7 @@
1.16 private:
1.17
1.18 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
1.19 -
1.20 +
1.21 typedef std::vector<int> IntVector;
1.22 typedef std::vector<double> DoubleVector;
1.23 typedef std::vector<Value> ValueVector;
1.24 @@ -151,15 +151,15 @@
1.25 // Note: vector<char> is used instead of vector<bool> for efficiency reasons
1.26
1.27 private:
1.28 -
1.29 +
1.30 template <typename KT, typename VT>
1.31 class StaticVectorMap {
1.32 public:
1.33 typedef KT Key;
1.34 typedef VT Value;
1.35 -
1.36 +
1.37 StaticVectorMap(std::vector<Value>& v) : _v(v) {}
1.38 -
1.39 +
1.40 const Value& operator[](const Key& key) const {
1.41 return _v[StaticDigraph::id(key)];
1.42 }
1.43 @@ -167,7 +167,7 @@
1.44 Value& operator[](const Key& key) {
1.45 return _v[StaticDigraph::id(key)];
1.46 }
1.47 -
1.48 +
1.49 void set(const Key& key, const Value& val) {
1.50 _v[StaticDigraph::id(key)] = val;
1.51 }
1.52 @@ -221,9 +221,9 @@
1.53 IntVector _id_vec;
1.54 CostArcMap _cost_map;
1.55 CostNodeMap _pi_map;
1.56 -
1.57 +
1.58 public:
1.59 -
1.60 +
1.61 /// \brief Constant for infinite upper bounds (capacities).
1.62 ///
1.63 /// Constant for infinite upper bounds (capacities).
1.64 @@ -366,7 +366,7 @@
1.65 _supply[_node_id[t]] = -k;
1.66 return *this;
1.67 }
1.68 -
1.69 +
1.70 /// @}
1.71
1.72 /// \name Execution control
1.73 @@ -466,7 +466,7 @@
1.74 _upper[j] = INF;
1.75 _cost[j] = 0;
1.76 _cost[_reverse[j]] = 0;
1.77 - }
1.78 + }
1.79 _have_lower = false;
1.80 return *this;
1.81 }
1.82 @@ -508,7 +508,7 @@
1.83 _upper.resize(_res_arc_num);
1.84 _cost.resize(_res_arc_num);
1.85 _supply.resize(_res_node_num);
1.86 -
1.87 +
1.88 _res_cap.resize(_res_arc_num);
1.89 _pi.resize(_res_node_num);
1.90
1.91 @@ -554,7 +554,7 @@
1.92 _reverse[fi] = bi;
1.93 _reverse[bi] = fi;
1.94 }
1.95 -
1.96 +
1.97 // Reset parameters
1.98 resetParams();
1.99 return *this;
1.100 @@ -663,14 +663,14 @@
1.101 _sum_supply += _supply[i];
1.102 }
1.103 if (_sum_supply > 0) return INFEASIBLE;
1.104 -
1.105 +
1.106
1.107 // Initialize vectors
1.108 for (int i = 0; i != _res_node_num; ++i) {
1.109 _pi[i] = 0;
1.110 }
1.111 ValueVector excess(_supply);
1.112 -
1.113 +
1.114 // Remove infinite upper bounds and check negative arcs
1.115 const Value MAX = std::numeric_limits<Value>::max();
1.116 int last_out;
1.117 @@ -770,10 +770,10 @@
1.118 _cost[ra] = 0;
1.119 }
1.120 }
1.121 -
1.122 +
1.123 return OPTIMAL;
1.124 }
1.125 -
1.126 +
1.127 // Build a StaticDigraph structure containing the current
1.128 // residual network
1.129 void buildResidualNetwork() {
1.130 @@ -829,14 +829,14 @@
1.131 // Constants for computing the iteration limits
1.132 const int BF_FIRST_LIMIT = 2;
1.133 const double BF_LIMIT_FACTOR = 1.5;
1.134 -
1.135 +
1.136 typedef StaticVectorMap<StaticDigraph::Arc, Value> FilterMap;
1.137 typedef FilterArcs<StaticDigraph, FilterMap> ResDigraph;
1.138 typedef StaticVectorMap<StaticDigraph::Node, StaticDigraph::Arc> PredMap;
1.139 typedef typename BellmanFord<ResDigraph, CostArcMap>
1.140 ::template SetDistMap<CostNodeMap>
1.141 ::template SetPredMap<PredMap>::Create BF;
1.142 -
1.143 +
1.144 // Build the residual network
1.145 _arc_vec.clear();
1.146 _cost_vec.clear();
1.147 @@ -926,7 +926,7 @@
1.148 typedef typename SPath::ArcIt SPathArcIt;
1.149 typedef typename HowardMmc<StaticDigraph, CostArcMap>
1.150 ::template SetPath<SPath>::Create MMC;
1.151 -
1.152 +
1.153 SPath cycle;
1.154 MMC mmc(_sgr, _cost_map);
1.155 mmc.cycle(cycle);
1.156 @@ -949,7 +949,7 @@
1.157 _res_cap[_reverse[j]] += delta;
1.158 }
1.159
1.160 - // Rebuild the residual network
1.161 + // Rebuild the residual network
1.162 buildResidualNetwork();
1.163 }
1.164 }
1.165 @@ -1143,7 +1143,7 @@
1.166 epsilon = -mmc.cycleMean();
1.167 Cost cycle_cost = mmc.cycleCost();
1.168 int cycle_size = mmc.cycleSize();
1.169 -
1.170 +
1.171 // Compute feasible potentials for the current epsilon
1.172 for (int i = 0; i != int(_cost_vec.size()); ++i) {
1.173 _cost_vec[i] = cycle_size * _cost_vec[i] - cycle_cost;
1.174 @@ -1155,7 +1155,7 @@
1.175 for (int u = 0; u != _res_node_num; ++u) {
1.176 pi[u] = static_cast<double>(_pi[u]) / cycle_size;
1.177 }
1.178 -
1.179 +
1.180 iter = limit;
1.181 }
1.182 }