diff options
Diffstat (limited to 'lemon/tools/dimacs-solver.cc')
-rw-r--r-- | lemon/tools/dimacs-solver.cc | 280 |
1 files changed, 280 insertions, 0 deletions
diff --git a/lemon/tools/dimacs-solver.cc b/lemon/tools/dimacs-solver.cc new file mode 100644 index 0000000..dc99cae --- /dev/null +++ b/lemon/tools/dimacs-solver.cc @@ -0,0 +1,280 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2010 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +///\ingroup tools +///\file +///\brief DIMACS problem solver. +/// +/// This program solves various problems given in DIMACS format. +/// +/// See +/// \code +/// dimacs-solver --help +/// \endcode +/// for more info on usage. + +#include <iostream> +#include <fstream> +#include <cstring> + +#include <lemon/smart_graph.h> +#include <lemon/dimacs.h> +#include <lemon/lgf_writer.h> +#include <lemon/time_measure.h> + +#include <lemon/arg_parser.h> +#include <lemon/error.h> + +#include <lemon/dijkstra.h> +#include <lemon/preflow.h> +#include <lemon/matching.h> +#include <lemon/network_simplex.h> + +using namespace lemon; +typedef SmartDigraph Digraph; +DIGRAPH_TYPEDEFS(Digraph); +typedef SmartGraph Graph; + +template<class Value> +void solve_sp(ArgParser &ap, std::istream &is, std::ostream &, + DimacsDescriptor &desc) +{ + bool report = !ap.given("q"); + Digraph g; + Node s; + Digraph::ArcMap<Value> len(g); + Timer t; + t.restart(); + readDimacsSp(is, g, len, s, desc); + if(report) std::cerr << "Read the file: " << t << '\n'; + t.restart(); + Dijkstra<Digraph, Digraph::ArcMap<Value> > dij(g,len); + if(report) std::cerr << "Setup Dijkstra class: " << t << '\n'; + t.restart(); + dij.run(s); + if(report) std::cerr << "Run Dijkstra: " << t << '\n'; +} + +template<class Value> +void solve_max(ArgParser &ap, std::istream &is, std::ostream &, + Value infty, DimacsDescriptor &desc) +{ + bool report = !ap.given("q"); + Digraph g; + Node s,t; + Digraph::ArcMap<Value> cap(g); + Timer ti; + ti.restart(); + readDimacsMax(is, g, cap, s, t, infty, desc); + if(report) std::cerr << "Read the file: " << ti << '\n'; + ti.restart(); + Preflow<Digraph, Digraph::ArcMap<Value> > pre(g,cap,s,t); + if(report) std::cerr << "Setup Preflow class: " << ti << '\n'; + ti.restart(); + pre.run(); + if(report) std::cerr << "Run Preflow: " << ti << '\n'; + if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n'; +} + +template<class Value, class LargeValue> +void solve_min(ArgParser &ap, std::istream &is, std::ostream &, + Value infty, DimacsDescriptor &desc) +{ + bool report = !ap.given("q"); + Digraph g; + Digraph::ArcMap<Value> lower(g), cap(g), cost(g); + Digraph::NodeMap<Value> sup(g); + Timer ti; + + ti.restart(); + readDimacsMin(is, g, lower, cap, cost, sup, infty, desc); + ti.stop(); + Value sum_sup = 0; + for (Digraph::NodeIt n(g); n != INVALID; ++n) { + sum_sup += sup[n]; + } + if (report) { + std::cerr << "Sum of supply values: " << sum_sup << "\n"; + if (sum_sup <= 0) + std::cerr << "GEQ supply contraints are used for NetworkSimplex\n\n"; + else + std::cerr << "LEQ supply contraints are used for NetworkSimplex\n\n"; + } + if (report) std::cerr << "Read the file: " << ti << '\n'; + + ti.restart(); + NetworkSimplex<Digraph, Value> ns(g); + ns.lowerMap(lower).upperMap(cap).costMap(cost).supplyMap(sup); + if (sum_sup > 0) ns.supplyType(ns.LEQ); + if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n'; + ti.restart(); + bool res = ns.run(); + if (report) { + std::cerr << "Run NetworkSimplex: " << ti << "\n\n"; + std::cerr << "Feasible flow: " << (res ? "found" : "not found") << '\n'; + if (res) std::cerr << "Min flow cost: " + << ns.template totalCost<LargeValue>() << '\n'; + } +} + +void solve_mat(ArgParser &ap, std::istream &is, std::ostream &, + DimacsDescriptor &desc) +{ + bool report = !ap.given("q"); + Graph g; + Timer ti; + ti.restart(); + readDimacsMat(is, g, desc); + if(report) std::cerr << "Read the file: " << ti << '\n'; + ti.restart(); + MaxMatching<Graph> mat(g); + if(report) std::cerr << "Setup MaxMatching class: " << ti << '\n'; + ti.restart(); + mat.run(); + if(report) std::cerr << "Run MaxMatching: " << ti << '\n'; + if(report) std::cerr << "\nCardinality of max matching: " + << mat.matchingSize() << '\n'; +} + + +template<class Value, class LargeValue> +void solve(ArgParser &ap, std::istream &is, std::ostream &os, + DimacsDescriptor &desc) +{ + std::stringstream iss(static_cast<std::string>(ap["infcap"])); + Value infty; + iss >> infty; + if(iss.fail()) + { + std::cerr << "Cannot interpret '" + << static_cast<std::string>(ap["infcap"]) << "' as infinite" + << std::endl; + exit(1); + } + + switch(desc.type) + { + case DimacsDescriptor::MIN: + solve_min<Value, LargeValue>(ap,is,os,infty,desc); + break; + case DimacsDescriptor::MAX: + solve_max<Value>(ap,is,os,infty,desc); + break; + case DimacsDescriptor::SP: + solve_sp<Value>(ap,is,os,desc); + break; + case DimacsDescriptor::MAT: + solve_mat(ap,is,os,desc); + break; + default: + break; + } +} + +int main(int argc, const char *argv[]) { + typedef SmartDigraph Digraph; + + typedef Digraph::Arc Arc; + + std::string inputName; + std::string outputName; + + ArgParser ap(argc, argv); + ap.other("[INFILE [OUTFILE]]", + "If either the INFILE or OUTFILE file is missing the standard\n" + " input/output will be used instead.") + .boolOption("q", "Do not print any report") + .boolOption("int","Use 'int' for capacities, costs etc. (default)") + .optionGroup("datatype","int") +#ifdef LEMON_HAVE_LONG_LONG + .boolOption("long","Use 'long long' for capacities, costs etc.") + .optionGroup("datatype","long") +#endif + .boolOption("double","Use 'double' for capacities, costs etc.") + .optionGroup("datatype","double") + .boolOption("ldouble","Use 'long double' for capacities, costs etc.") + .optionGroup("datatype","ldouble") + .onlyOneGroup("datatype") + .stringOption("infcap","Value used for 'very high' capacities","0") + .run(); + + std::ifstream input; + std::ofstream output; + + switch(ap.files().size()) + { + case 2: + output.open(ap.files()[1].c_str()); + if (!output) { + throw IoError("Cannot open the file for writing", ap.files()[1]); + } + case 1: + input.open(ap.files()[0].c_str()); + if (!input) { + throw IoError("File cannot be found", ap.files()[0]); + } + case 0: + break; + default: + std::cerr << ap.commandName() << ": too many arguments\n"; + return 1; + } + std::istream& is = (ap.files().size()<1 ? std::cin : input); + std::ostream& os = (ap.files().size()<2 ? std::cout : output); + + DimacsDescriptor desc = dimacsType(is); + + if(!ap.given("q")) + { + std::cout << "Problem type: "; + switch(desc.type) + { + case DimacsDescriptor::MIN: + std::cout << "min"; + break; + case DimacsDescriptor::MAX: + std::cout << "max"; + break; + case DimacsDescriptor::SP: + std::cout << "sp"; + case DimacsDescriptor::MAT: + std::cout << "mat"; + break; + default: + exit(1); + break; + } + std::cout << "\nNum of nodes: " << desc.nodeNum; + std::cout << "\nNum of arcs: " << desc.edgeNum; + std::cout << "\n\n"; + } + + if(ap.given("double")) + solve<double, double>(ap,is,os,desc); + else if(ap.given("ldouble")) + solve<long double, long double>(ap,is,os,desc); +#ifdef LEMON_HAVE_LONG_LONG + else if(ap.given("long")) + solve<long long, long long>(ap,is,os,desc); + else solve<int, long long>(ap,is,os,desc); +#else + else solve<int, long>(ap,is,os,desc); +#endif + + return 0; +} |