r387:24a2c6ee6cb0
Fri, 28 Nov 2008 07:38:20
[Not Reviewed]
0 comments (0 inline)
0
2
0
175
59
83
102
| ... | ... |
@@ -23,6 +23,7 @@ |
| 23 | 23 |
#include <string> |
| 24 | 24 |
#include <vector> |
| 25 | 25 |
#include <lemon/maps.h> |
| 26 |
#include <lemon/error.h> |
|
| 26 | 27 |
|
| 27 | 28 |
/// \ingroup dimacs_group |
| 28 | 29 |
/// \file |
| ... | ... |
@@ -40,6 +41,70 @@ |
| 40 | 41 |
/// \addtogroup dimacs_group |
| 41 | 42 |
/// @{
|
| 42 | 43 |
|
| 44 |
|
|
| 45 |
/// DIMACS file type descriptor. |
|
| 46 |
struct DimacsDescriptor |
|
| 47 |
{
|
|
| 48 |
///File type enum |
|
| 49 |
enum Type |
|
| 50 |
{
|
|
| 51 |
NONE, MIN, MAX, SP, MAT |
|
| 52 |
}; |
|
| 53 |
///The file type |
|
| 54 |
Type type; |
|
| 55 |
///The number of nodes on the graph |
|
| 56 |
int nodeNum; |
|
| 57 |
///The number of edges on the graph |
|
| 58 |
int edgeNum; |
|
| 59 |
int lineShift; |
|
| 60 |
/// Constructor. Sets the type to NONE. |
|
| 61 |
DimacsDescriptor() : type(NONE) {}
|
|
| 62 |
}; |
|
| 63 |
|
|
| 64 |
///Discover the type of a DIMACS file |
|
| 65 |
|
|
| 66 |
///It starts seeking the begining of the file for the problem type |
|
| 67 |
///and size info. The found date is returned in a special struct |
|
| 68 |
///that can be evaluated and passed to the appropriate reader |
|
| 69 |
///function. |
|
| 70 |
DimacsDescriptor dimacsType(std::istream& is) |
|
| 71 |
{
|
|
| 72 |
DimacsDescriptor r; |
|
| 73 |
std::string problem,str; |
|
| 74 |
char c; |
|
| 75 |
r.lineShift=0; |
|
| 76 |
while (is >> c) |
|
| 77 |
switch(c) |
|
| 78 |
{
|
|
| 79 |
case 'p': |
|
| 80 |
if(is >> problem >> r.nodeNum >> r.edgeNum) |
|
| 81 |
{
|
|
| 82 |
getline(is, str); |
|
| 83 |
r.lineShift++; |
|
| 84 |
if(problem=="min") r.type=DimacsDescriptor::MIN; |
|
| 85 |
else if(problem=="max") r.type=DimacsDescriptor::MAX; |
|
| 86 |
else if(problem=="sp") r.type=DimacsDescriptor::SP; |
|
| 87 |
else if(problem=="mat") r.type=DimacsDescriptor::MAT; |
|
| 88 |
else throw FormatError("Unknown problem type");
|
|
| 89 |
return r; |
|
| 90 |
} |
|
| 91 |
else |
|
| 92 |
{
|
|
| 93 |
throw FormatError("Missing or wrong problem type declaration.");
|
|
| 94 |
} |
|
| 95 |
break; |
|
| 96 |
case 'c': |
|
| 97 |
getline(is, str); |
|
| 98 |
r.lineShift++; |
|
| 99 |
break; |
|
| 100 |
default: |
|
| 101 |
throw FormatError("Unknown DIMACS declaration.");
|
|
| 102 |
} |
|
| 103 |
throw FormatError("Missing problem type declaration.");
|
|
| 104 |
} |
|
| 105 |
|
|
| 106 |
|
|
| 107 |
|
|
| 43 | 108 |
/// DIMACS min cost flow reader function. |
| 44 | 109 |
/// |
| 45 | 110 |
/// This function reads a min cost flow instance from DIMACS format, |
| ... | ... |
@@ -47,27 +112,40 @@ |
| 47 | 112 |
/// \code |
| 48 | 113 |
/// p min |
| 49 | 114 |
/// \endcode |
| 50 |
/// At the beginning \c g is cleared by \c g.clear(). The supply |
|
| 115 |
/// At the beginning, \c g is cleared by \c g.clear(). The supply |
|
| 51 | 116 |
/// amount of the nodes are written to \c supply (signed). The |
| 52 | 117 |
/// lower bounds, capacities and costs of the arcs are written to |
| 53 | 118 |
/// \c lower, \c capacity and \c cost. |
| 119 |
/// |
|
| 120 |
/// If the file type was previously evaluated by dimacsType(), then |
|
| 121 |
/// the descriptor struct should be given by the \c dest parameter. |
|
| 54 | 122 |
template <typename Digraph, typename LowerMap, |
| 55 |
typename CapacityMap, typename CostMap, |
|
| 56 |
typename SupplyMap> |
|
| 57 |
void readDimacsMin( std::istream& is, |
|
| 58 |
Digraph &g, |
|
| 59 |
LowerMap& lower, |
|
| 60 |
CapacityMap& capacity, |
|
| 61 |
CostMap& cost, |
|
| 62 |
SupplyMap& supply ) |
|
| 123 |
typename CapacityMap, typename CostMap, |
|
| 124 |
typename SupplyMap> |
|
| 125 |
void readDimacsMin(std::istream& is, |
|
| 126 |
Digraph &g, |
|
| 127 |
LowerMap& lower, |
|
| 128 |
CapacityMap& capacity, |
|
| 129 |
CostMap& cost, |
|
| 130 |
SupplyMap& supply, |
|
| 131 |
DimacsDescriptor desc=DimacsDescriptor()) |
|
| 63 | 132 |
{
|
| 64 | 133 |
g.clear(); |
| 65 | 134 |
std::vector<typename Digraph::Node> nodes; |
| 66 | 135 |
typename Digraph::Arc e; |
| 67 | 136 |
std::string problem, str; |
| 68 | 137 |
char c; |
| 69 |
int n, m; |
|
| 70 | 138 |
int i, j; |
| 139 |
if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); |
|
| 140 |
if(desc.type!=DimacsDescriptor::MIN) |
|
| 141 |
throw FormatError("Problem type mismatch");
|
|
| 142 |
|
|
| 143 |
nodes.resize(desc.nodeNum + 1); |
|
| 144 |
for (int k = 1; k <= desc.nodeNum; ++k) {
|
|
| 145 |
nodes[k] = g.addNode(); |
|
| 146 |
supply.set(nodes[k], 0); |
|
| 147 |
} |
|
| 148 |
|
|
| 71 | 149 |
typename SupplyMap::Value sup; |
| 72 | 150 |
typename CapacityMap::Value low; |
| 73 | 151 |
typename CapacityMap::Value cap; |
| ... | ... |
@@ -77,16 +155,6 @@ |
| 77 | 155 |
case 'c': // comment line |
| 78 | 156 |
getline(is, str); |
| 79 | 157 |
break; |
| 80 |
case 'p': // problem definition line |
|
| 81 |
is >> problem >> n >> m; |
|
| 82 |
getline(is, str); |
|
| 83 |
if (problem != "min") return; |
|
| 84 |
nodes.resize(n + 1); |
|
| 85 |
for (int k = 1; k <= n; ++k) {
|
|
| 86 |
nodes[k] = g.addNode(); |
|
| 87 |
supply.set(nodes[k], 0); |
|
| 88 |
} |
|
| 89 |
break; |
|
| 90 | 158 |
case 'n': // node definition line |
| 91 | 159 |
is >> i >> sup; |
| 92 | 160 |
getline(is, str); |
| ... | ... |
@@ -107,47 +175,38 @@ |
| 107 | 175 |
} |
| 108 | 176 |
} |
| 109 | 177 |
|
| 110 |
/// DIMACS max flow reader function. |
|
| 111 |
/// |
|
| 112 |
/// This function reads a max flow instance from DIMACS format, |
|
| 113 |
/// i.e. from DIMACS files having a line starting with |
|
| 114 |
/// \code |
|
| 115 |
/// p max |
|
| 116 |
/// \endcode |
|
| 117 |
/// At the beginning \c g is cleared by \c g.clear(). The arc |
|
| 118 |
/// capacities are written to \c capacity and \c s and \c t are |
|
| 119 |
/// set to the source and the target nodes. |
|
| 120 | 178 |
template<typename Digraph, typename CapacityMap> |
| 121 |
void readDimacsMax(std::istream& is, Digraph &g, CapacityMap& capacity, |
|
| 122 |
typename Digraph::Node &s, typename Digraph::Node &t) {
|
|
| 179 |
void _readDimacs(std::istream& is, |
|
| 180 |
Digraph &g, |
|
| 181 |
CapacityMap& capacity, |
|
| 182 |
typename Digraph::Node &s, |
|
| 183 |
typename Digraph::Node &t, |
|
| 184 |
DimacsDescriptor desc=DimacsDescriptor()) {
|
|
| 123 | 185 |
g.clear(); |
| 186 |
s=t=INVALID; |
|
| 124 | 187 |
std::vector<typename Digraph::Node> nodes; |
| 125 | 188 |
typename Digraph::Arc e; |
| 126 |
std::string problem; |
|
| 127 | 189 |
char c, d; |
| 128 |
int n, m; |
|
| 129 | 190 |
int i, j; |
| 130 | 191 |
typename CapacityMap::Value _cap; |
| 131 | 192 |
std::string str; |
| 193 |
nodes.resize(desc.nodeNum + 1); |
|
| 194 |
for (int k = 1; k <= desc.nodeNum; ++k) {
|
|
| 195 |
nodes[k] = g.addNode(); |
|
| 196 |
} |
|
| 197 |
|
|
| 132 | 198 |
while (is >> c) {
|
| 133 | 199 |
switch (c) {
|
| 134 | 200 |
case 'c': // comment line |
| 135 | 201 |
getline(is, str); |
| 136 | 202 |
break; |
| 137 |
case 'p': // problem definition line |
|
| 138 |
is >> problem >> n >> m; |
|
| 139 |
getline(is, str); |
|
| 140 |
nodes.resize(n + 1); |
|
| 141 |
for (int k = 1; k <= n; ++k) |
|
| 142 |
nodes[k] = g.addNode(); |
|
| 143 |
break; |
|
| 144 | 203 |
case 'n': // node definition line |
| 145 |
if ( |
|
| 204 |
if (desc.type==DimacsDescriptor::SP) { // shortest path problem
|
|
| 146 | 205 |
is >> i; |
| 147 | 206 |
getline(is, str); |
| 148 | 207 |
s = nodes[i]; |
| 149 | 208 |
} |
| 150 |
if ( |
|
| 209 |
if (desc.type==DimacsDescriptor::MAX) { // max flow problem
|
|
| 151 | 210 |
is >> i >> d; |
| 152 | 211 |
getline(is, str); |
| 153 | 212 |
if (d == 's') s = nodes[i]; |
| ... | ... |
@@ -155,7 +214,8 @@ |
| 155 | 214 |
} |
| 156 | 215 |
break; |
| 157 | 216 |
case 'a': // arc (arc) definition line |
| 158 |
if ( |
|
| 217 |
if (desc.type==DimacsDescriptor::SP || |
|
| 218 |
desc.type==DimacsDescriptor::MAX) {
|
|
| 159 | 219 |
is >> i >> j >> _cap; |
| 160 | 220 |
getline(is, str); |
| 161 | 221 |
e = g.addArc(nodes[i], nodes[j]); |
| ... | ... |
@@ -170,6 +230,32 @@ |
| 170 | 230 |
} |
| 171 | 231 |
} |
| 172 | 232 |
|
| 233 |
/// DIMACS max flow reader function. |
|
| 234 |
/// |
|
| 235 |
/// This function reads a max flow instance from DIMACS format, |
|
| 236 |
/// i.e. from DIMACS files having a line starting with |
|
| 237 |
/// \code |
|
| 238 |
/// p max |
|
| 239 |
/// \endcode |
|
| 240 |
/// At the beginning, \c g is cleared by \c g.clear(). The arc |
|
| 241 |
/// capacities are written to \c capacity and \c s and \c t are |
|
| 242 |
/// set to the source and the target nodes. |
|
| 243 |
/// |
|
| 244 |
/// If the file type was previously evaluated by dimacsType(), then |
|
| 245 |
/// the descriptor struct should be given by the \c dest parameter. |
|
| 246 |
template<typename Digraph, typename CapacityMap> |
|
| 247 |
void readDimacsMax(std::istream& is, |
|
| 248 |
Digraph &g, |
|
| 249 |
CapacityMap& capacity, |
|
| 250 |
typename Digraph::Node &s, |
|
| 251 |
typename Digraph::Node &t, |
|
| 252 |
DimacsDescriptor desc=DimacsDescriptor()) {
|
|
| 253 |
if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); |
|
| 254 |
if(desc.type!=DimacsDescriptor::MAX) |
|
| 255 |
throw FormatError("Problem type mismatch");
|
|
| 256 |
_readDimacs(is,g,capacity,s,t,desc); |
|
| 257 |
} |
|
| 258 |
|
|
| 173 | 259 |
/// DIMACS shortest path reader function. |
| 174 | 260 |
/// |
| 175 | 261 |
/// This function reads a shortest path instance from DIMACS format, |
| ... | ... |
@@ -177,25 +263,44 @@ |
| 177 | 263 |
/// \code |
| 178 | 264 |
/// p sp |
| 179 | 265 |
/// \endcode |
| 180 |
/// At the beginning \c g is cleared by \c g.clear(). The arc |
|
| 181 |
/// capacities are written to \c capacity and \c s is set to the |
|
| 266 |
/// At the beginning, \c g is cleared by \c g.clear(). The arc |
|
| 267 |
/// lengths are written to \c lenght and \c s is set to the |
|
| 182 | 268 |
/// source node. |
| 183 |
template<typename Digraph, typename CapacityMap> |
|
| 184 |
void readDimacsSp(std::istream& is, Digraph &g, CapacityMap& capacity, |
|
| 185 |
|
|
| 269 |
/// |
|
| 270 |
/// If the file type was previously evaluated by dimacsType(), then |
|
| 271 |
/// the descriptor struct should be given by the \c dest parameter. |
|
| 272 |
template<typename Digraph, typename LengthMap> |
|
| 273 |
void readDimacsSp(std::istream& is, |
|
| 274 |
Digraph &g, |
|
| 275 |
LengthMap& length, |
|
| 276 |
typename Digraph::Node &s, |
|
| 277 |
DimacsDescriptor desc=DimacsDescriptor()) {
|
|
| 186 | 278 |
typename Digraph::Node t; |
| 187 |
|
|
| 279 |
if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); |
|
| 280 |
if(desc.type!=DimacsDescriptor::SP) |
|
| 281 |
throw FormatError("Problem type mismatch");
|
|
| 282 |
_readDimacs(is, g, length, s, t,desc); |
|
| 188 | 283 |
} |
| 189 | 284 |
|
| 190 | 285 |
/// DIMACS capacitated digraph reader function. |
| 191 | 286 |
/// |
| 192 | 287 |
/// This function reads an arc capacitated digraph instance from |
| 193 |
/// DIMACS format. At the beginning \c g is cleared by \c g.clear() |
|
| 194 |
/// and the arc capacities are written to \c capacity. |
|
| 288 |
/// DIMACS 'mat' or 'sp' format. |
|
| 289 |
/// At the beginning, \c g is cleared by \c g.clear() |
|
| 290 |
/// and the arc capacities/lengths are written to \c capacity. |
|
| 291 |
/// |
|
| 292 |
/// If the file type was previously evaluated by dimacsType(), then |
|
| 293 |
/// the descriptor struct should be given by the \c dest parameter. |
|
| 195 | 294 |
template<typename Digraph, typename CapacityMap> |
| 196 |
void |
|
| 295 |
void readDimacsCap(std::istream& is, |
|
| 296 |
Digraph &g, |
|
| 297 |
CapacityMap& capacity, |
|
| 298 |
DimacsDescriptor desc=DimacsDescriptor()) {
|
|
| 197 | 299 |
typename Digraph::Node u,v; |
| 198 |
|
|
| 300 |
if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); |
|
| 301 |
if(desc.type!=DimacsDescriptor::MAX || desc.type!=DimacsDescriptor::SP) |
|
| 302 |
throw FormatError("Problem type mismatch");
|
|
| 303 |
_readDimacs(is, g, capacity, u, v, desc); |
|
| 199 | 304 |
} |
| 200 | 305 |
|
| 201 | 306 |
/// DIMACS plain digraph reader function. |
| ... | ... |
@@ -206,12 +311,19 @@ |
| 206 | 311 |
/// \code |
| 207 | 312 |
/// p mat |
| 208 | 313 |
/// \endcode |
| 209 |
/// At the beginning \c g is cleared by \c g.clear(). |
|
| 314 |
/// At the beginning, \c g is cleared by \c g.clear(). |
|
| 315 |
/// |
|
| 316 |
/// If the file type was previously evaluated by dimacsType(), then |
|
| 317 |
/// the descriptor struct should be given by the \c dest parameter. |
|
| 210 | 318 |
template<typename Digraph> |
| 211 |
void readDimacsMat(std::istream& is, Digraph &g |
|
| 319 |
void readDimacsMat(std::istream& is, Digraph &g, |
|
| 320 |
DimacsDescriptor desc=DimacsDescriptor()) {
|
|
| 212 | 321 |
typename Digraph::Node u,v; |
| 213 | 322 |
NullMap<typename Digraph::Arc, int> n; |
| 214 |
|
|
| 323 |
if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); |
|
| 324 |
if(desc.type!=DimacsDescriptor::MAT) |
|
| 325 |
throw FormatError("Problem type mismatch");
|
|
| 326 |
_readDimacs(is, g, n, u, v, desc); |
|
| 215 | 327 |
} |
| 216 | 328 |
|
| 217 | 329 |
/// DIMACS plain digraph writer function. |
| ... | ... |
@@ -222,12 +334,16 @@ |
| 222 | 334 |
/// \code |
| 223 | 335 |
/// p mat |
| 224 | 336 |
/// \endcode |
| 337 |
/// If \c comment is not empty, then it will be printed in the first line |
|
| 338 |
/// prefixed by 'c'. |
|
| 225 | 339 |
template<typename Digraph> |
| 226 |
void writeDimacsMat(std::ostream& os, const Digraph &g |
|
| 340 |
void writeDimacsMat(std::ostream& os, const Digraph &g, |
|
| 341 |
std::string comment="") {
|
|
| 227 | 342 |
typedef typename Digraph::NodeIt NodeIt; |
| 228 | 343 |
typedef typename Digraph::ArcIt ArcIt; |
| 229 | 344 |
|
| 230 |
|
|
| 345 |
if(!comment.empty()) |
|
| 346 |
os << "c " << comment << std::endl; |
|
| 231 | 347 |
os << "p mat " << g.nodeNum() << " " << g.arcNum() << std::endl; |
| 232 | 348 |
|
| 233 | 349 |
typename Digraph::template NodeMap<int> nodes(g); |
| ... | ... |
@@ -39,6 +39,7 @@ |
| 39 | 39 |
#include <lemon/lgf_writer.h> |
| 40 | 40 |
|
| 41 | 41 |
#include <lemon/arg_parser.h> |
| 42 |
#include <lemon/error.h> |
|
| 42 | 43 |
|
| 43 | 44 |
using namespace std; |
| 44 | 45 |
using namespace lemon; |
| ... | ... |
@@ -56,113 +57,93 @@ |
| 56 | 57 |
|
| 57 | 58 |
std::string inputName; |
| 58 | 59 |
std::string outputName; |
| 59 |
std::string typeName; |
|
| 60 |
|
|
| 61 |
bool mincostflow; |
|
| 62 |
bool maxflow; |
|
| 63 |
bool shortestpath; |
|
| 64 |
bool capacitated; |
|
| 65 |
bool plain; |
|
| 66 |
|
|
| 67 |
bool version; |
|
| 68 | 60 |
|
| 69 | 61 |
ArgParser ap(argc, argv); |
| 70 |
ap.refOption("-input",
|
|
| 71 |
"use FILE as input instead of standard input", |
|
| 72 |
inputName).synonym("i", "-input")
|
|
| 73 |
.refOption("-output",
|
|
| 74 |
"use FILE as output instead of standard output", |
|
| 75 |
outputName).synonym("o", "-output")
|
|
| 76 |
.refOption("-mincostflow",
|
|
| 77 |
"set the type of the digraph to \"mincostflow\" digraph", |
|
| 78 |
mincostflow) |
|
| 79 |
.optionGroup("type", "-mincostflow").synonym("mcf", "-mincostflow")
|
|
| 80 |
.refOption("-maxflow",
|
|
| 81 |
"set the type of the digraph to \"maxflow\" digraph", |
|
| 82 |
maxflow) |
|
| 83 |
.optionGroup("type", "-maxflow").synonym("mf", "-maxflow")
|
|
| 84 |
.refOption("-shortestpath",
|
|
| 85 |
"set the type of the digraph to \"shortestpath\" digraph", |
|
| 86 |
shortestpath) |
|
| 87 |
.optionGroup("type", "-shortestpath").synonym("sp", "-shortestpath")
|
|
| 88 |
.refOption("-capacitated",
|
|
| 89 |
"set the type of the digraph to \"capacitated\" digraph", |
|
| 90 |
capacitated) |
|
| 91 |
.optionGroup("type", "-capacitated").synonym("cap", "-capacitated")
|
|
| 92 |
.refOption("-plain",
|
|
| 93 |
"set the type of the digraph to \"plain\" digraph", |
|
| 94 |
plain) |
|
| 95 |
.optionGroup("type", "-plain").synonym("pl", "-plain")
|
|
| 96 |
.onlyOneGroup("type")
|
|
| 97 |
.mandatoryGroup("type")
|
|
| 98 |
.refOption("-version", "show version information", version)
|
|
| 99 |
.synonym("v", "-version")
|
|
| 62 |
ap.other("[INFILE [OUTFILE]]",
|
|
| 63 |
"If either the INFILE or OUTFILE file is missing the standard\n" |
|
| 64 |
" input/output will be used instead.") |
|
| 100 | 65 |
.run(); |
| 101 | 66 |
|
| 102 | 67 |
ifstream input; |
| 103 |
if (!inputName.empty()) {
|
|
| 104 |
input.open(inputName.c_str()); |
|
| 105 |
if (!input) {
|
|
| 106 |
cerr << "File open error" << endl; |
|
| 107 |
|
|
| 68 |
ofstream output; |
|
| 69 |
|
|
| 70 |
switch(ap.files().size()) |
|
| 71 |
{
|
|
| 72 |
case 2: |
|
| 73 |
output.open(ap.files()[1].c_str()); |
|
| 74 |
if (!output) {
|
|
| 75 |
throw IoError("Cannot open the file for writing", ap.files()[1]);
|
|
| 76 |
} |
|
| 77 |
case 1: |
|
| 78 |
input.open(ap.files()[0].c_str()); |
|
| 79 |
if (!input) {
|
|
| 80 |
throw IoError("File cannot be found", ap.files()[0]);
|
|
| 81 |
} |
|
| 82 |
case 0: |
|
| 83 |
break; |
|
| 84 |
default: |
|
| 85 |
cerr << ap.commandName() << ": too many arguments\n"; |
|
| 86 |
return 1; |
|
| 87 |
} |
|
| 88 |
istream& is = (ap.files().size()<1 ? cin : input); |
|
| 89 |
ostream& os = (ap.files().size()<2 ? cout : output); |
|
| 90 |
|
|
| 91 |
DimacsDescriptor desc = dimacsType(is); |
|
| 92 |
switch(desc.type) |
|
| 93 |
{
|
|
| 94 |
case DimacsDescriptor::MIN: |
|
| 95 |
{
|
|
| 96 |
Digraph digraph; |
|
| 97 |
DoubleArcMap lower(digraph), capacity(digraph), cost(digraph); |
|
| 98 |
DoubleNodeMap supply(digraph); |
|
| 99 |
readDimacsMin(is, digraph, lower, capacity, cost, supply, desc); |
|
| 100 |
DigraphWriter<Digraph>(digraph, os). |
|
| 101 |
nodeMap("supply", supply).
|
|
| 102 |
arcMap("lower", lower).
|
|
| 103 |
arcMap("capacity", capacity).
|
|
| 104 |
arcMap("cost", cost).
|
|
| 105 |
attribute("problem","min").
|
|
| 106 |
run(); |
|
| 107 |
} |
|
| 108 |
break; |
|
| 109 |
case DimacsDescriptor::MAX: |
|
| 110 |
{
|
|
| 111 |
Digraph digraph; |
|
| 112 |
Node s, t; |
|
| 113 |
DoubleArcMap capacity(digraph); |
|
| 114 |
readDimacsMax(is, digraph, capacity, s, t, desc); |
|
| 115 |
DigraphWriter<Digraph>(digraph, os). |
|
| 116 |
arcMap("capacity", capacity).
|
|
| 117 |
node("source", s).
|
|
| 118 |
node("target", t).
|
|
| 119 |
attribute("problem","max").
|
|
| 120 |
run(); |
|
| 121 |
} |
|
| 122 |
break; |
|
| 123 |
case DimacsDescriptor::SP: |
|
| 124 |
{
|
|
| 125 |
Digraph digraph; |
|
| 126 |
Node s; |
|
| 127 |
DoubleArcMap capacity(digraph); |
|
| 128 |
readDimacsSp(is, digraph, capacity, s, desc); |
|
| 129 |
DigraphWriter<Digraph>(digraph, os). |
|
| 130 |
arcMap("capacity", capacity).
|
|
| 131 |
node("source", s).
|
|
| 132 |
attribute("problem","sp").
|
|
| 133 |
run(); |
|
| 134 |
} |
|
| 135 |
break; |
|
| 136 |
case DimacsDescriptor::MAT: |
|
| 137 |
{
|
|
| 138 |
Digraph digraph; |
|
| 139 |
readDimacsMat(is, digraph,desc); |
|
| 140 |
DigraphWriter<Digraph>(digraph, os). |
|
| 141 |
attribute("problem","mat").
|
|
| 142 |
run(); |
|
| 143 |
} |
|
| 144 |
break; |
|
| 145 |
default: |
|
| 146 |
break; |
|
| 108 | 147 |
} |
| 109 |
} |
|
| 110 |
istream& is = (inputName.empty() ? cin : input); |
|
| 111 |
|
|
| 112 |
ofstream output; |
|
| 113 |
if (!outputName.empty()) {
|
|
| 114 |
output.open(outputName.c_str()); |
|
| 115 |
if (!output) {
|
|
| 116 |
cerr << "File open error" << endl; |
|
| 117 |
return -1; |
|
| 118 |
} |
|
| 119 |
} |
|
| 120 |
ostream& os = (outputName.empty() ? cout : output); |
|
| 121 |
|
|
| 122 |
if (mincostflow) {
|
|
| 123 |
Digraph digraph; |
|
| 124 |
DoubleArcMap lower(digraph), capacity(digraph), cost(digraph); |
|
| 125 |
DoubleNodeMap supply(digraph); |
|
| 126 |
readDimacsMin(is, digraph, lower, capacity, cost, supply); |
|
| 127 |
DigraphWriter<Digraph>(digraph, os). |
|
| 128 |
nodeMap("supply", supply).
|
|
| 129 |
arcMap("lower", lower).
|
|
| 130 |
arcMap("capacity", capacity).
|
|
| 131 |
arcMap("cost", cost).
|
|
| 132 |
run(); |
|
| 133 |
} else if (maxflow) {
|
|
| 134 |
Digraph digraph; |
|
| 135 |
Node s, t; |
|
| 136 |
DoubleArcMap capacity(digraph); |
|
| 137 |
readDimacsMax(is, digraph, capacity, s, t); |
|
| 138 |
DigraphWriter<Digraph>(digraph, os). |
|
| 139 |
arcMap("capacity", capacity).
|
|
| 140 |
node("source", s).
|
|
| 141 |
node("target", t).
|
|
| 142 |
run(); |
|
| 143 |
} else if (shortestpath) {
|
|
| 144 |
Digraph digraph; |
|
| 145 |
Node s; |
|
| 146 |
DoubleArcMap capacity(digraph); |
|
| 147 |
readDimacsSp(is, digraph, capacity, s); |
|
| 148 |
DigraphWriter<Digraph>(digraph, os). |
|
| 149 |
arcMap("capacity", capacity).
|
|
| 150 |
node("source", s).
|
|
| 151 |
run(); |
|
| 152 |
} else if (capacitated) {
|
|
| 153 |
Digraph digraph; |
|
| 154 |
DoubleArcMap capacity(digraph); |
|
| 155 |
readDimacsMax(is, digraph, capacity); |
|
| 156 |
DigraphWriter<Digraph>(digraph, os). |
|
| 157 |
arcMap("capacity", capacity).
|
|
| 158 |
run(); |
|
| 159 |
} else if (plain) {
|
|
| 160 |
Digraph digraph; |
|
| 161 |
readDimacsMat(is, digraph); |
|
| 162 |
DigraphWriter<Digraph>(digraph, os).run(); |
|
| 163 |
} else {
|
|
| 164 |
cerr << "Invalid type error" << endl; |
|
| 165 |
return -1; |
|
| 166 |
} |
|
| 167 | 148 |
return 0; |
| 168 | 149 |
} |
0 comments (0 inline)