r661:19b6f20e0ea2
Fri, 24 Apr 2009 12:23:17
[Not Reviewed]
0 comments (0 inline)
0
1
0
| ... | ... |
@@ -72,107 +72,125 @@ |
| 72 | 72 |
|
| 73 | 73 |
template<class Value> |
| 74 | 74 |
void solve_max(ArgParser &ap, std::istream &is, std::ostream &, |
| 75 | 75 |
Value infty, DimacsDescriptor &desc) |
| 76 | 76 |
{
|
| 77 | 77 |
bool report = !ap.given("q");
|
| 78 | 78 |
Digraph g; |
| 79 | 79 |
Node s,t; |
| 80 | 80 |
Digraph::ArcMap<Value> cap(g); |
| 81 | 81 |
Timer ti; |
| 82 | 82 |
ti.restart(); |
| 83 | 83 |
readDimacsMax(is, g, cap, s, t, infty, desc); |
| 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(); |
| 126 | 144 |
MaxMatching<Graph> mat(g); |
| 127 | 145 |
if(report) std::cerr << "Setup MaxMatching class: " << ti << '\n'; |
| 128 | 146 |
ti.restart(); |
| 129 | 147 |
mat.run(); |
| 130 | 148 |
if(report) std::cerr << "Run MaxMatching: " << ti << '\n'; |
| 131 | 149 |
if(report) std::cerr << "\nCardinality of max matching: " |
| 132 | 150 |
<< mat.matchingSize() << '\n'; |
| 133 | 151 |
} |
| 134 | 152 |
|
| 135 | 153 |
|
| 136 | 154 |
template<class Value> |
| 137 | 155 |
void solve(ArgParser &ap, std::istream &is, std::ostream &os, |
| 138 | 156 |
DimacsDescriptor &desc) |
| 139 | 157 |
{
|
| 140 | 158 |
std::stringstream iss(static_cast<std::string>(ap["infcap"])); |
| 141 | 159 |
Value infty; |
| 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; |
| 167 | 185 |
} |
| 168 | 186 |
} |
| 169 | 187 |
|
| 170 | 188 |
int main(int argc, const char *argv[]) {
|
| 171 | 189 |
typedef SmartDigraph Digraph; |
| 172 | 190 |
|
| 173 | 191 |
typedef Digraph::Arc Arc; |
| 174 | 192 |
|
| 175 | 193 |
std::string inputName; |
| 176 | 194 |
std::string outputName; |
| 177 | 195 |
|
| 178 | 196 |
ArgParser ap(argc, argv); |
0 comments (0 inline)