1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/tools/dimacs-solver.cc Thu Dec 10 17:05:35 2009 +0100
1.3 @@ -0,0 +1,277 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2009
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +///\ingroup tools
1.23 +///\file
1.24 +///\brief DIMACS problem solver.
1.25 +///
1.26 +/// This program solves various problems given in DIMACS format.
1.27 +///
1.28 +/// See
1.29 +/// \code
1.30 +/// dimacs-solver --help
1.31 +/// \endcode
1.32 +/// for more info on usage.
1.33 +
1.34 +#include <iostream>
1.35 +#include <fstream>
1.36 +#include <cstring>
1.37 +
1.38 +#include <lemon/smart_graph.h>
1.39 +#include <lemon/dimacs.h>
1.40 +#include <lemon/lgf_writer.h>
1.41 +#include <lemon/time_measure.h>
1.42 +
1.43 +#include <lemon/arg_parser.h>
1.44 +#include <lemon/error.h>
1.45 +
1.46 +#include <lemon/dijkstra.h>
1.47 +#include <lemon/preflow.h>
1.48 +#include <lemon/matching.h>
1.49 +#include <lemon/network_simplex.h>
1.50 +
1.51 +using namespace lemon;
1.52 +typedef SmartDigraph Digraph;
1.53 +DIGRAPH_TYPEDEFS(Digraph);
1.54 +typedef SmartGraph Graph;
1.55 +
1.56 +template<class Value>
1.57 +void solve_sp(ArgParser &ap, std::istream &is, std::ostream &,
1.58 + DimacsDescriptor &desc)
1.59 +{
1.60 + bool report = !ap.given("q");
1.61 + Digraph g;
1.62 + Node s;
1.63 + Digraph::ArcMap<Value> len(g);
1.64 + Timer t;
1.65 + t.restart();
1.66 + readDimacsSp(is, g, len, s, desc);
1.67 + if(report) std::cerr << "Read the file: " << t << '\n';
1.68 + t.restart();
1.69 + Dijkstra<Digraph, Digraph::ArcMap<Value> > dij(g,len);
1.70 + if(report) std::cerr << "Setup Dijkstra class: " << t << '\n';
1.71 + t.restart();
1.72 + dij.run(s);
1.73 + if(report) std::cerr << "Run Dijkstra: " << t << '\n';
1.74 +}
1.75 +
1.76 +template<class Value>
1.77 +void solve_max(ArgParser &ap, std::istream &is, std::ostream &,
1.78 + Value infty, DimacsDescriptor &desc)
1.79 +{
1.80 + bool report = !ap.given("q");
1.81 + Digraph g;
1.82 + Node s,t;
1.83 + Digraph::ArcMap<Value> cap(g);
1.84 + Timer ti;
1.85 + ti.restart();
1.86 + readDimacsMax(is, g, cap, s, t, infty, desc);
1.87 + if(report) std::cerr << "Read the file: " << ti << '\n';
1.88 + ti.restart();
1.89 + Preflow<Digraph, Digraph::ArcMap<Value> > pre(g,cap,s,t);
1.90 + if(report) std::cerr << "Setup Preflow class: " << ti << '\n';
1.91 + ti.restart();
1.92 + pre.run();
1.93 + if(report) std::cerr << "Run Preflow: " << ti << '\n';
1.94 + if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n';
1.95 +}
1.96 +
1.97 +template<class Value>
1.98 +void solve_min(ArgParser &ap, std::istream &is, std::ostream &,
1.99 + Value infty, DimacsDescriptor &desc)
1.100 +{
1.101 + bool report = !ap.given("q");
1.102 + Digraph g;
1.103 + Digraph::ArcMap<Value> lower(g), cap(g), cost(g);
1.104 + Digraph::NodeMap<Value> sup(g);
1.105 + Timer ti;
1.106 +
1.107 + ti.restart();
1.108 + readDimacsMin(is, g, lower, cap, cost, sup, infty, desc);
1.109 + ti.stop();
1.110 + Value sum_sup = 0;
1.111 + for (Digraph::NodeIt n(g); n != INVALID; ++n) {
1.112 + sum_sup += sup[n];
1.113 + }
1.114 + if (report) {
1.115 + std::cerr << "Sum of supply values: " << sum_sup << "\n";
1.116 + if (sum_sup <= 0)
1.117 + std::cerr << "GEQ supply contraints are used for NetworkSimplex\n\n";
1.118 + else
1.119 + std::cerr << "LEQ supply contraints are used for NetworkSimplex\n\n";
1.120 + }
1.121 + if (report) std::cerr << "Read the file: " << ti << '\n';
1.122 +
1.123 + ti.restart();
1.124 + NetworkSimplex<Digraph, Value> ns(g);
1.125 + ns.lowerMap(lower).upperMap(cap).costMap(cost).supplyMap(sup);
1.126 + if (sum_sup > 0) ns.supplyType(ns.LEQ);
1.127 + if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n';
1.128 + ti.restart();
1.129 + bool res = ns.run();
1.130 + if (report) {
1.131 + std::cerr << "Run NetworkSimplex: " << ti << "\n\n";
1.132 + std::cerr << "Feasible flow: " << (res ? "found" : "not found") << '\n';
1.133 + if (res) std::cerr << "Min flow cost: " << ns.totalCost() << '\n';
1.134 + }
1.135 +}
1.136 +
1.137 +void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
1.138 + DimacsDescriptor &desc)
1.139 +{
1.140 + bool report = !ap.given("q");
1.141 + Graph g;
1.142 + Timer ti;
1.143 + ti.restart();
1.144 + readDimacsMat(is, g, desc);
1.145 + if(report) std::cerr << "Read the file: " << ti << '\n';
1.146 + ti.restart();
1.147 + MaxMatching<Graph> mat(g);
1.148 + if(report) std::cerr << "Setup MaxMatching class: " << ti << '\n';
1.149 + ti.restart();
1.150 + mat.run();
1.151 + if(report) std::cerr << "Run MaxMatching: " << ti << '\n';
1.152 + if(report) std::cerr << "\nCardinality of max matching: "
1.153 + << mat.matchingSize() << '\n';
1.154 +}
1.155 +
1.156 +
1.157 +template<class Value>
1.158 +void solve(ArgParser &ap, std::istream &is, std::ostream &os,
1.159 + DimacsDescriptor &desc)
1.160 +{
1.161 + std::stringstream iss(static_cast<std::string>(ap["infcap"]));
1.162 + Value infty;
1.163 + iss >> infty;
1.164 + if(iss.fail())
1.165 + {
1.166 + std::cerr << "Cannot interpret '"
1.167 + << static_cast<std::string>(ap["infcap"]) << "' as infinite"
1.168 + << std::endl;
1.169 + exit(1);
1.170 + }
1.171 +
1.172 + switch(desc.type)
1.173 + {
1.174 + case DimacsDescriptor::MIN:
1.175 + solve_min<Value>(ap,is,os,infty,desc);
1.176 + break;
1.177 + case DimacsDescriptor::MAX:
1.178 + solve_max<Value>(ap,is,os,infty,desc);
1.179 + break;
1.180 + case DimacsDescriptor::SP:
1.181 + solve_sp<Value>(ap,is,os,desc);
1.182 + break;
1.183 + case DimacsDescriptor::MAT:
1.184 + solve_mat(ap,is,os,desc);
1.185 + break;
1.186 + default:
1.187 + break;
1.188 + }
1.189 +}
1.190 +
1.191 +int main(int argc, const char *argv[]) {
1.192 + typedef SmartDigraph Digraph;
1.193 +
1.194 + typedef Digraph::Arc Arc;
1.195 +
1.196 + std::string inputName;
1.197 + std::string outputName;
1.198 +
1.199 + ArgParser ap(argc, argv);
1.200 + ap.other("[INFILE [OUTFILE]]",
1.201 + "If either the INFILE or OUTFILE file is missing the standard\n"
1.202 + " input/output will be used instead.")
1.203 + .boolOption("q", "Do not print any report")
1.204 + .boolOption("int","Use 'int' for capacities, costs etc. (default)")
1.205 + .optionGroup("datatype","int")
1.206 +#ifdef LEMON_HAVE_LONG_LONG
1.207 + .boolOption("long","Use 'long long' for capacities, costs etc.")
1.208 + .optionGroup("datatype","long")
1.209 +#endif
1.210 + .boolOption("double","Use 'double' for capacities, costs etc.")
1.211 + .optionGroup("datatype","double")
1.212 + .boolOption("ldouble","Use 'long double' for capacities, costs etc.")
1.213 + .optionGroup("datatype","ldouble")
1.214 + .onlyOneGroup("datatype")
1.215 + .stringOption("infcap","Value used for 'very high' capacities","0")
1.216 + .run();
1.217 +
1.218 + std::ifstream input;
1.219 + std::ofstream output;
1.220 +
1.221 + switch(ap.files().size())
1.222 + {
1.223 + case 2:
1.224 + output.open(ap.files()[1].c_str());
1.225 + if (!output) {
1.226 + throw IoError("Cannot open the file for writing", ap.files()[1]);
1.227 + }
1.228 + case 1:
1.229 + input.open(ap.files()[0].c_str());
1.230 + if (!input) {
1.231 + throw IoError("File cannot be found", ap.files()[0]);
1.232 + }
1.233 + case 0:
1.234 + break;
1.235 + default:
1.236 + std::cerr << ap.commandName() << ": too many arguments\n";
1.237 + return 1;
1.238 + }
1.239 + std::istream& is = (ap.files().size()<1 ? std::cin : input);
1.240 + std::ostream& os = (ap.files().size()<2 ? std::cout : output);
1.241 +
1.242 + DimacsDescriptor desc = dimacsType(is);
1.243 +
1.244 + if(!ap.given("q"))
1.245 + {
1.246 + std::cout << "Problem type: ";
1.247 + switch(desc.type)
1.248 + {
1.249 + case DimacsDescriptor::MIN:
1.250 + std::cout << "min";
1.251 + break;
1.252 + case DimacsDescriptor::MAX:
1.253 + std::cout << "max";
1.254 + break;
1.255 + case DimacsDescriptor::SP:
1.256 + std::cout << "sp";
1.257 + case DimacsDescriptor::MAT:
1.258 + std::cout << "mat";
1.259 + break;
1.260 + default:
1.261 + exit(1);
1.262 + break;
1.263 + }
1.264 + std::cout << "\nNum of nodes: " << desc.nodeNum;
1.265 + std::cout << "\nNum of arcs: " << desc.edgeNum;
1.266 + std::cout << "\n\n";
1.267 + }
1.268 +
1.269 + if(ap.given("double"))
1.270 + solve<double>(ap,is,os,desc);
1.271 + else if(ap.given("ldouble"))
1.272 + solve<long double>(ap,is,os,desc);
1.273 +#ifdef LEMON_HAVE_LONG_LONG
1.274 + else if(ap.given("long"))
1.275 + solve<long long>(ap,is,os,desc);
1.276 +#endif
1.277 + else solve<int>(ap,is,os,desc);
1.278 +
1.279 + return 0;
1.280 +}