r665:b95898314e09
Fri, 24 Apr 2009 13:12:14
[Not Reviewed]
0 comments (0 inline)
0
3
0
| ... | ... |
@@ -1138,82 +1138,83 @@ |
| 1138 | 1138 |
if (std::numeric_limits<Cost>::is_exact) {
|
| 1139 | 1139 |
art_cost = std::numeric_limits<Cost>::max() / 4 + 1; |
| 1140 | 1140 |
} else {
|
| 1141 | 1141 |
art_cost = std::numeric_limits<Cost>::min(); |
| 1142 | 1142 |
for (int i = 0; i != _arc_num; ++i) {
|
| 1143 | 1143 |
if (_cost[i] > art_cost) art_cost = _cost[i]; |
| 1144 | 1144 |
} |
| 1145 | 1145 |
art_cost = (art_cost + 1) * _node_num; |
| 1146 | 1146 |
} |
| 1147 | 1147 |
|
| 1148 | 1148 |
// Run Circulation to check if a feasible solution exists |
| 1149 | 1149 |
typedef ConstMap<Arc, Flow> ConstArcMap; |
| 1150 |
ConstArcMap zero_arc_map(0), inf_arc_map(inf_cap); |
|
| 1150 | 1151 |
FlowNodeMap *csup = NULL; |
| 1151 | 1152 |
bool local_csup = false; |
| 1152 | 1153 |
if (_psupply) {
|
| 1153 | 1154 |
csup = _psupply; |
| 1154 | 1155 |
} else {
|
| 1155 | 1156 |
csup = new FlowNodeMap(_graph, 0); |
| 1156 | 1157 |
(*csup)[_psource] = _pstflow; |
| 1157 | 1158 |
(*csup)[_ptarget] = -_pstflow; |
| 1158 | 1159 |
local_csup = true; |
| 1159 | 1160 |
} |
| 1160 | 1161 |
bool circ_result = false; |
| 1161 | 1162 |
if (_ptype == GEQ || (_ptype == LEQ && sum_supply == 0)) {
|
| 1162 | 1163 |
// GEQ problem type |
| 1163 | 1164 |
if (_plower) {
|
| 1164 | 1165 |
if (_pupper) {
|
| 1165 | 1166 |
Circulation<GR, FlowArcMap, FlowArcMap, FlowNodeMap> |
| 1166 | 1167 |
circ(_graph, *_plower, *_pupper, *csup); |
| 1167 | 1168 |
circ_result = circ.run(); |
| 1168 | 1169 |
} else {
|
| 1169 | 1170 |
Circulation<GR, FlowArcMap, ConstArcMap, FlowNodeMap> |
| 1170 |
circ(_graph, *_plower, |
|
| 1171 |
circ(_graph, *_plower, inf_arc_map, *csup); |
|
| 1171 | 1172 |
circ_result = circ.run(); |
| 1172 | 1173 |
} |
| 1173 | 1174 |
} else {
|
| 1174 | 1175 |
if (_pupper) {
|
| 1175 | 1176 |
Circulation<GR, ConstArcMap, FlowArcMap, FlowNodeMap> |
| 1176 |
circ(_graph, |
|
| 1177 |
circ(_graph, zero_arc_map, *_pupper, *csup); |
|
| 1177 | 1178 |
circ_result = circ.run(); |
| 1178 | 1179 |
} else {
|
| 1179 | 1180 |
Circulation<GR, ConstArcMap, ConstArcMap, FlowNodeMap> |
| 1180 |
circ(_graph, |
|
| 1181 |
circ(_graph, zero_arc_map, inf_arc_map, *csup); |
|
| 1181 | 1182 |
circ_result = circ.run(); |
| 1182 | 1183 |
} |
| 1183 | 1184 |
} |
| 1184 | 1185 |
} else {
|
| 1185 | 1186 |
// LEQ problem type |
| 1186 | 1187 |
typedef ReverseDigraph<const GR> RevGraph; |
| 1187 | 1188 |
typedef NegMap<FlowNodeMap> NegNodeMap; |
| 1188 | 1189 |
RevGraph rgraph(_graph); |
| 1189 | 1190 |
NegNodeMap neg_csup(*csup); |
| 1190 | 1191 |
if (_plower) {
|
| 1191 | 1192 |
if (_pupper) {
|
| 1192 | 1193 |
Circulation<RevGraph, FlowArcMap, FlowArcMap, NegNodeMap> |
| 1193 | 1194 |
circ(rgraph, *_plower, *_pupper, neg_csup); |
| 1194 | 1195 |
circ_result = circ.run(); |
| 1195 | 1196 |
} else {
|
| 1196 | 1197 |
Circulation<RevGraph, FlowArcMap, ConstArcMap, NegNodeMap> |
| 1197 |
circ(rgraph, *_plower, |
|
| 1198 |
circ(rgraph, *_plower, inf_arc_map, neg_csup); |
|
| 1198 | 1199 |
circ_result = circ.run(); |
| 1199 | 1200 |
} |
| 1200 | 1201 |
} else {
|
| 1201 | 1202 |
if (_pupper) {
|
| 1202 | 1203 |
Circulation<RevGraph, ConstArcMap, FlowArcMap, NegNodeMap> |
| 1203 |
circ(rgraph, |
|
| 1204 |
circ(rgraph, zero_arc_map, *_pupper, neg_csup); |
|
| 1204 | 1205 |
circ_result = circ.run(); |
| 1205 | 1206 |
} else {
|
| 1206 | 1207 |
Circulation<RevGraph, ConstArcMap, ConstArcMap, NegNodeMap> |
| 1207 |
circ(rgraph, |
|
| 1208 |
circ(rgraph, zero_arc_map, inf_arc_map, neg_csup); |
|
| 1208 | 1209 |
circ_result = circ.run(); |
| 1209 | 1210 |
} |
| 1210 | 1211 |
} |
| 1211 | 1212 |
} |
| 1212 | 1213 |
if (local_csup) delete csup; |
| 1213 | 1214 |
if (!circ_result) return false; |
| 1214 | 1215 |
|
| 1215 | 1216 |
// Set data for the artificial root node |
| 1216 | 1217 |
_root = _node_num; |
| 1217 | 1218 |
_parent[_root] = -1; |
| 1218 | 1219 |
_pred[_root] = -1; |
| 1219 | 1220 |
_thread[_root] = 0; |
| ... | ... |
@@ -224,30 +224,25 @@ |
| 224 | 224 |
check(checkPotential(gr, lower, upper, cost, supply, mcf.flowMap(), |
| 225 | 225 |
mcf.potentialMap()), |
| 226 | 226 |
"Wrong potentials " + test_id); |
| 227 | 227 |
} |
| 228 | 228 |
} |
| 229 | 229 |
|
| 230 | 230 |
int main() |
| 231 | 231 |
{
|
| 232 | 232 |
// Check the interfaces |
| 233 | 233 |
{
|
| 234 | 234 |
typedef int Flow; |
| 235 | 235 |
typedef int Cost; |
| 236 |
// TODO: This typedef should be enabled if the standard maps are |
|
| 237 |
// reference maps in the graph concepts (See #190). |
|
| 238 |
/**/ |
|
| 239 |
//typedef concepts::Digraph GR; |
|
| 240 |
typedef ListDigraph GR; |
|
| 241 |
/**/ |
|
| 236 |
typedef concepts::Digraph GR; |
|
| 242 | 237 |
checkConcept< McfClassConcept<GR, Flow, Cost>, |
| 243 | 238 |
NetworkSimplex<GR, Flow, Cost> >(); |
| 244 | 239 |
} |
| 245 | 240 |
|
| 246 | 241 |
// Run various MCF tests |
| 247 | 242 |
typedef ListDigraph Digraph; |
| 248 | 243 |
DIGRAPH_TYPEDEFS(ListDigraph); |
| 249 | 244 |
|
| 250 | 245 |
// Read the test digraph |
| 251 | 246 |
Digraph gr; |
| 252 | 247 |
Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), u(gr); |
| 253 | 248 |
Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr); |
| ... | ... |
@@ -84,42 +84,60 @@ |
| 84 | 84 |
if(report) std::cerr << "Read the file: " << ti << '\n'; |
| 85 | 85 |
ti.restart(); |
| 86 | 86 |
Preflow<Digraph, Digraph::ArcMap<Value> > pre(g,cap,s,t); |
| 87 | 87 |
if(report) std::cerr << "Setup Preflow class: " << ti << '\n'; |
| 88 | 88 |
ti.restart(); |
| 89 | 89 |
pre.run(); |
| 90 | 90 |
if(report) std::cerr << "Run Preflow: " << ti << '\n'; |
| 91 | 91 |
if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n'; |
| 92 | 92 |
} |
| 93 | 93 |
|
| 94 | 94 |
template<class Value> |
| 95 | 95 |
void solve_min(ArgParser &ap, std::istream &is, std::ostream &, |
| 96 |
DimacsDescriptor &desc) |
|
| 96 |
Value infty, DimacsDescriptor &desc) |
|
| 97 | 97 |
{
|
| 98 | 98 |
bool report = !ap.given("q");
|
| 99 | 99 |
Digraph g; |
| 100 | 100 |
Digraph::ArcMap<Value> lower(g), cap(g), cost(g); |
| 101 | 101 |
Digraph::NodeMap<Value> sup(g); |
| 102 | 102 |
Timer ti; |
| 103 |
|
|
| 103 | 104 |
ti.restart(); |
| 104 |
readDimacsMin(is, g, lower, cap, cost, sup, |
|
| 105 |
readDimacsMin(is, g, lower, cap, cost, sup, infty, desc); |
|
| 106 |
ti.stop(); |
|
| 107 |
Value sum_sup = 0; |
|
| 108 |
for (Digraph::NodeIt n(g); n != INVALID; ++n) {
|
|
| 109 |
sum_sup += sup[n]; |
|
| 110 |
} |
|
| 111 |
if (report) {
|
|
| 112 |
std::cerr << "Sum of supply values: " << sum_sup << "\n"; |
|
| 113 |
if (sum_sup <= 0) |
|
| 114 |
std::cerr << "GEQ supply contraints are used for NetworkSimplex\n\n"; |
|
| 115 |
else |
|
| 116 |
std::cerr << "LEQ supply contraints are used for NetworkSimplex\n\n"; |
|
| 117 |
} |
|
| 105 | 118 |
if (report) std::cerr << "Read the file: " << ti << '\n'; |
| 119 |
|
|
| 106 | 120 |
ti.restart(); |
| 107 | 121 |
NetworkSimplex<Digraph, Value> ns(g); |
| 108 | 122 |
ns.lowerMap(lower).capacityMap(cap).costMap(cost).supplyMap(sup); |
| 123 |
if (sum_sup > 0) ns.problemType(ns.LEQ); |
|
| 109 | 124 |
if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n'; |
| 110 | 125 |
ti.restart(); |
| 111 |
ns.run(); |
|
| 112 |
if (report) std::cerr << "Run NetworkSimplex: " << ti << '\n'; |
|
| 113 |
|
|
| 126 |
bool res = ns.run(); |
|
| 127 |
if (report) {
|
|
| 128 |
std::cerr << "Run NetworkSimplex: " << ti << "\n\n"; |
|
| 129 |
std::cerr << "Feasible flow: " << (res ? "found" : "not found") << '\n'; |
|
| 130 |
if (res) std::cerr << "Min flow cost: " << ns.totalCost() << '\n'; |
|
| 131 |
} |
|
| 114 | 132 |
} |
| 115 | 133 |
|
| 116 | 134 |
void solve_mat(ArgParser &ap, std::istream &is, std::ostream &, |
| 117 | 135 |
DimacsDescriptor &desc) |
| 118 | 136 |
{
|
| 119 | 137 |
bool report = !ap.given("q");
|
| 120 | 138 |
Graph g; |
| 121 | 139 |
Timer ti; |
| 122 | 140 |
ti.restart(); |
| 123 | 141 |
readDimacsMat(is, g, desc); |
| 124 | 142 |
if(report) std::cerr << "Read the file: " << ti << '\n'; |
| 125 | 143 |
ti.restart(); |
| ... | ... |
@@ -142,25 +160,25 @@ |
| 142 | 160 |
iss >> infty; |
| 143 | 161 |
if(iss.fail()) |
| 144 | 162 |
{
|
| 145 | 163 |
std::cerr << "Cannot interpret '" |
| 146 | 164 |
<< static_cast<std::string>(ap["infcap"]) << "' as infinite" |
| 147 | 165 |
<< std::endl; |
| 148 | 166 |
exit(1); |
| 149 | 167 |
} |
| 150 | 168 |
|
| 151 | 169 |
switch(desc.type) |
| 152 | 170 |
{
|
| 153 | 171 |
case DimacsDescriptor::MIN: |
| 154 |
solve_min<Value>(ap,is,os,desc); |
|
| 172 |
solve_min<Value>(ap,is,os,infty,desc); |
|
| 155 | 173 |
break; |
| 156 | 174 |
case DimacsDescriptor::MAX: |
| 157 | 175 |
solve_max<Value>(ap,is,os,infty,desc); |
| 158 | 176 |
break; |
| 159 | 177 |
case DimacsDescriptor::SP: |
| 160 | 178 |
solve_sp<Value>(ap,is,os,desc); |
| 161 | 179 |
break; |
| 162 | 180 |
case DimacsDescriptor::MAT: |
| 163 | 181 |
solve_mat(ap,is,os,desc); |
| 164 | 182 |
break; |
| 165 | 183 |
default: |
| 166 | 184 |
break; |
0 comments (0 inline)