r618:b95898314e09
Fri, 24 Apr 2009 13:12:14
[Not Reviewed]
0 comments (0 inline)
0
3
0
| ... | ... |
@@ -1147,6 +1147,7 @@ |
| 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) {
|
| ... | ... |
@@ -1167,17 +1168,17 @@ |
| 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 |
} |
| ... | ... |
@@ -1194,17 +1195,17 @@ |
| 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 |
} |
| ... | ... |
@@ -233,12 +233,7 @@ |
| 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 |
} |
| ... | ... |
@@ -93,24 +93,42 @@ |
| 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 &, |
| ... | ... |
@@ -151,7 +169,7 @@ |
| 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); |
0 comments (0 inline)