r820:7ef7a5fbb85d
Fri, 13 Nov 2009 00:37:55
[Not Reviewed]
0 comments (0 inline)
0
2
0
| ... | ... |
@@ -196,49 +196,49 @@ |
| 196 | 196 |
|
| 197 | 197 |
TEMPLATE_DIGRAPH_TYPEDEFS(GR); |
| 198 | 198 |
|
| 199 | 199 |
typedef std::vector<int> IntVector; |
| 200 | 200 |
typedef std::vector<char> BoolVector; |
| 201 | 201 |
typedef std::vector<Value> ValueVector; |
| 202 | 202 |
typedef std::vector<Cost> CostVector; |
| 203 | 203 |
typedef std::vector<LargeCost> LargeCostVector; |
| 204 | 204 |
|
| 205 | 205 |
private: |
| 206 | 206 |
|
| 207 | 207 |
template <typename KT, typename VT> |
| 208 |
class |
|
| 208 |
class StaticVectorMap {
|
|
| 209 | 209 |
public: |
| 210 | 210 |
typedef KT Key; |
| 211 | 211 |
typedef VT Value; |
| 212 | 212 |
|
| 213 |
|
|
| 213 |
StaticVectorMap(std::vector<Value>& v) : _v(v) {}
|
|
| 214 | 214 |
|
| 215 | 215 |
const Value& operator[](const Key& key) const {
|
| 216 | 216 |
return _v[StaticDigraph::id(key)]; |
| 217 | 217 |
} |
| 218 | 218 |
|
| 219 | 219 |
Value& operator[](const Key& key) {
|
| 220 | 220 |
return _v[StaticDigraph::id(key)]; |
| 221 | 221 |
} |
| 222 | 222 |
|
| 223 | 223 |
void set(const Key& key, const Value& val) {
|
| 224 | 224 |
_v[StaticDigraph::id(key)] = val; |
| 225 | 225 |
} |
| 226 | 226 |
|
| 227 | 227 |
private: |
| 228 | 228 |
std::vector<Value>& _v; |
| 229 | 229 |
}; |
| 230 | 230 |
|
| 231 |
typedef VectorMap<StaticDigraph::Node, LargeCost> LargeCostNodeMap; |
|
| 232 |
typedef VectorMap<StaticDigraph::Arc, LargeCost> LargeCostArcMap; |
|
| 231 |
typedef StaticVectorMap<StaticDigraph::Node, LargeCost> LargeCostNodeMap; |
|
| 232 |
typedef StaticVectorMap<StaticDigraph::Arc, LargeCost> LargeCostArcMap; |
|
| 233 | 233 |
|
| 234 | 234 |
private: |
| 235 | 235 |
|
| 236 | 236 |
// Data related to the underlying digraph |
| 237 | 237 |
const GR &_graph; |
| 238 | 238 |
int _node_num; |
| 239 | 239 |
int _arc_num; |
| 240 | 240 |
int _res_node_num; |
| 241 | 241 |
int _res_arc_num; |
| 242 | 242 |
int _root; |
| 243 | 243 |
|
| 244 | 244 |
// Parameters of the problem |
| ... | ... |
@@ -143,49 +143,49 @@ |
| 143 | 143 |
|
| 144 | 144 |
TEMPLATE_DIGRAPH_TYPEDEFS(GR); |
| 145 | 145 |
|
| 146 | 146 |
typedef std::vector<int> IntVector; |
| 147 | 147 |
typedef std::vector<char> CharVector; |
| 148 | 148 |
typedef std::vector<double> DoubleVector; |
| 149 | 149 |
typedef std::vector<Value> ValueVector; |
| 150 | 150 |
typedef std::vector<Cost> CostVector; |
| 151 | 151 |
|
| 152 | 152 |
private: |
| 153 | 153 |
|
| 154 | 154 |
template <typename KT, typename VT> |
| 155 |
class |
|
| 155 |
class StaticVectorMap {
|
|
| 156 | 156 |
public: |
| 157 | 157 |
typedef KT Key; |
| 158 | 158 |
typedef VT Value; |
| 159 | 159 |
|
| 160 |
|
|
| 160 |
StaticVectorMap(std::vector<Value>& v) : _v(v) {}
|
|
| 161 | 161 |
|
| 162 | 162 |
const Value& operator[](const Key& key) const {
|
| 163 | 163 |
return _v[StaticDigraph::id(key)]; |
| 164 | 164 |
} |
| 165 | 165 |
|
| 166 | 166 |
Value& operator[](const Key& key) {
|
| 167 | 167 |
return _v[StaticDigraph::id(key)]; |
| 168 | 168 |
} |
| 169 | 169 |
|
| 170 | 170 |
void set(const Key& key, const Value& val) {
|
| 171 | 171 |
_v[StaticDigraph::id(key)] = val; |
| 172 | 172 |
} |
| 173 | 173 |
|
| 174 | 174 |
private: |
| 175 | 175 |
std::vector<Value>& _v; |
| 176 | 176 |
}; |
| 177 | 177 |
|
| 178 |
typedef VectorMap<StaticDigraph::Node, Cost> CostNodeMap; |
|
| 179 |
typedef VectorMap<StaticDigraph::Arc, Cost> CostArcMap; |
|
| 178 |
typedef StaticVectorMap<StaticDigraph::Node, Cost> CostNodeMap; |
|
| 179 |
typedef StaticVectorMap<StaticDigraph::Arc, Cost> CostArcMap; |
|
| 180 | 180 |
|
| 181 | 181 |
private: |
| 182 | 182 |
|
| 183 | 183 |
|
| 184 | 184 |
// Data related to the underlying digraph |
| 185 | 185 |
const GR &_graph; |
| 186 | 186 |
int _node_num; |
| 187 | 187 |
int _arc_num; |
| 188 | 188 |
int _res_node_num; |
| 189 | 189 |
int _res_arc_num; |
| 190 | 190 |
int _root; |
| 191 | 191 |
|
| ... | ... |
@@ -791,27 +791,27 @@ |
| 791 | 791 |
for (int j = 0; j != limit; ++j) {
|
| 792 | 792 |
if (!_forward[j]) _res_cap[j] += _lower[j]; |
| 793 | 793 |
} |
| 794 | 794 |
} |
| 795 | 795 |
} |
| 796 | 796 |
|
| 797 | 797 |
// Execute the "Simple Cycle Canceling" method |
| 798 | 798 |
void startSimpleCycleCanceling() {
|
| 799 | 799 |
// Constants for computing the iteration limits |
| 800 | 800 |
const int BF_FIRST_LIMIT = 2; |
| 801 | 801 |
const double BF_LIMIT_FACTOR = 1.5; |
| 802 | 802 |
|
| 803 |
typedef |
|
| 803 |
typedef StaticVectorMap<StaticDigraph::Arc, Value> FilterMap; |
|
| 804 | 804 |
typedef FilterArcs<StaticDigraph, FilterMap> ResDigraph; |
| 805 |
typedef |
|
| 805 |
typedef StaticVectorMap<StaticDigraph::Node, StaticDigraph::Arc> PredMap; |
|
| 806 | 806 |
typedef typename BellmanFord<ResDigraph, CostArcMap> |
| 807 | 807 |
::template SetDistMap<CostNodeMap> |
| 808 | 808 |
::template SetPredMap<PredMap>::Create BF; |
| 809 | 809 |
|
| 810 | 810 |
// Build the residual network |
| 811 | 811 |
_arc_vec.clear(); |
| 812 | 812 |
_cost_vec.clear(); |
| 813 | 813 |
for (int j = 0; j != _res_arc_num; ++j) {
|
| 814 | 814 |
_arc_vec.push_back(IntPair(_source[j], _target[j])); |
| 815 | 815 |
_cost_vec.push_back(_cost[j]); |
| 816 | 816 |
} |
| 817 | 817 |
_sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end()); |
0 comments (0 inline)