r649:a79ef774fae1
Tue, 24 Feb 2009 09:52:26
[Not Reviewed]
0 comments (0 inline)
0
1
0
| ... | ... |
@@ -41,12 +41,13 @@ |
| 41 | 41 |
#include <lemon/arg_parser.h> |
| 42 | 42 |
#include <lemon/error.h> |
| 43 | 43 |
|
| 44 | 44 |
#include <lemon/dijkstra.h> |
| 45 | 45 |
#include <lemon/preflow.h> |
| 46 | 46 |
#include <lemon/max_matching.h> |
| 47 |
#include <lemon/network_simplex.h> |
|
| 47 | 48 |
|
| 48 | 49 |
using namespace lemon; |
| 49 | 50 |
typedef SmartDigraph Digraph; |
| 50 | 51 |
DIGRAPH_TYPEDEFS(Digraph); |
| 51 | 52 |
typedef SmartGraph Graph; |
| 52 | 53 |
|
| ... | ... |
@@ -88,12 +89,35 @@ |
| 88 | 89 |
ti.restart(); |
| 89 | 90 |
pre.run(); |
| 90 | 91 |
if(report) std::cerr << "Run Preflow: " << ti << '\n'; |
| 91 | 92 |
if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n'; |
| 92 | 93 |
} |
| 93 | 94 |
|
| 95 |
template<class Value> |
|
| 96 |
void solve_min(ArgParser &ap, std::istream &is, std::ostream &, |
|
| 97 |
DimacsDescriptor &desc) |
|
| 98 |
{
|
|
| 99 |
bool report = !ap.given("q");
|
|
| 100 |
Digraph g; |
|
| 101 |
Digraph::ArcMap<Value> lower(g), cap(g), cost(g); |
|
| 102 |
Digraph::NodeMap<Value> sup(g); |
|
| 103 |
Timer ti; |
|
| 104 |
ti.restart(); |
|
| 105 |
readDimacsMin(is, g, lower, cap, cost, sup, desc); |
|
| 106 |
if (report) std::cerr << "Read the file: " << ti << '\n'; |
|
| 107 |
ti.restart(); |
|
| 108 |
NetworkSimplex< Digraph, Digraph::ArcMap<Value>, Digraph::ArcMap<Value>, |
|
| 109 |
Digraph::ArcMap<Value>, Digraph::NodeMap<Value> > |
|
| 110 |
ns(g, lower, cap, cost, sup); |
|
| 111 |
if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n'; |
|
| 112 |
ti.restart(); |
|
| 113 |
ns.run(); |
|
| 114 |
if (report) std::cerr << "Run NetworkSimplex: " << ti << '\n'; |
|
| 115 |
if (report) std::cerr << "\nMin flow cost: " << ns.totalCost() << '\n'; |
|
| 116 |
} |
|
| 117 |
|
|
| 94 | 118 |
void solve_mat(ArgParser &ap, std::istream &is, std::ostream &, |
| 95 | 119 |
DimacsDescriptor &desc) |
| 96 | 120 |
{
|
| 97 | 121 |
bool report = !ap.given("q");
|
| 98 | 122 |
Graph g; |
| 99 | 123 |
Timer ti; |
| ... | ... |
@@ -115,14 +139,13 @@ |
| 115 | 139 |
void solve(ArgParser &ap, std::istream &is, std::ostream &os, |
| 116 | 140 |
DimacsDescriptor &desc) |
| 117 | 141 |
{
|
| 118 | 142 |
switch(desc.type) |
| 119 | 143 |
{
|
| 120 | 144 |
case DimacsDescriptor::MIN: |
| 121 |
std::cerr << |
|
| 122 |
"\n\n Sorry, the min. cost flow solver is not yet available.\n"; |
|
| 145 |
solve_min<Value>(ap,is,os,desc); |
|
| 123 | 146 |
break; |
| 124 | 147 |
case DimacsDescriptor::MAX: |
| 125 | 148 |
solve_max<Value>(ap,is,os,desc); |
| 126 | 149 |
break; |
| 127 | 150 |
case DimacsDescriptor::SP: |
| 128 | 151 |
solve_sp<Value>(ap,is,os,desc); |
0 comments (0 inline)