tools/dimacs-solver.cc
author Alpar Juttner <alpar@cs.elte.hu>
Wed, 17 Oct 2018 19:22:52 +0200
changeset 1185 c8d0179a32a2
parent 1093 fb1c7da561ce
permissions -rw-r--r--
Merge bugfixes #610,#611,#612,#614
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2013
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 ///\ingroup tools
    20 ///\file
    21 ///\brief DIMACS problem solver.
    22 ///
    23 /// This program solves various problems given in DIMACS format.
    24 ///
    25 /// See
    26 /// \code
    27 ///   dimacs-solver --help
    28 /// \endcode
    29 /// for more info on usage.
    30 
    31 #include <iostream>
    32 #include <fstream>
    33 #include <cstring>
    34 
    35 #include <lemon/smart_graph.h>
    36 #include <lemon/dimacs.h>
    37 #include <lemon/lgf_writer.h>
    38 #include <lemon/time_measure.h>
    39 
    40 #include <lemon/arg_parser.h>
    41 #include <lemon/error.h>
    42 
    43 #include <lemon/dijkstra.h>
    44 #include <lemon/preflow.h>
    45 #include <lemon/matching.h>
    46 #include <lemon/network_simplex.h>
    47 
    48 using namespace lemon;
    49 typedef SmartDigraph Digraph;
    50 DIGRAPH_TYPEDEFS(Digraph);
    51 typedef SmartGraph Graph;
    52 
    53 template<class Value>
    54 void solve_sp(ArgParser &ap, std::istream &is, std::ostream &,
    55               DimacsDescriptor &desc)
    56 {
    57   bool report = !ap.given("q");
    58   Digraph g;
    59   Node s;
    60   Digraph::ArcMap<Value> len(g);
    61   Timer t;
    62   t.restart();
    63   readDimacsSp(is, g, len, s, desc);
    64   if(report) std::cerr << "Read the file: " << t << '\n';
    65   t.restart();
    66   Dijkstra<Digraph, Digraph::ArcMap<Value> > dij(g,len);
    67   if(report) std::cerr << "Setup Dijkstra class: " << t << '\n';
    68   t.restart();
    69   dij.run(s);
    70   if(report) std::cerr << "Run Dijkstra: " << t << '\n';
    71 }
    72 
    73 template<class Value>
    74 void solve_max(ArgParser &ap, std::istream &is, std::ostream &,
    75                Value infty, DimacsDescriptor &desc)
    76 {
    77   bool report = !ap.given("q");
    78   Digraph g;
    79   Node s,t;
    80   Digraph::ArcMap<Value> cap(g);
    81   Timer ti;
    82   ti.restart();
    83   readDimacsMax(is, g, cap, s, t, infty, desc);
    84   if(report) std::cerr << "Read the file: " << ti << '\n';
    85   ti.restart();
    86   Preflow<Digraph, Digraph::ArcMap<Value> > pre(g,cap,s,t);
    87   if(report) std::cerr << "Setup Preflow class: " << ti << '\n';
    88   ti.restart();
    89   pre.run();
    90   if(report) std::cerr << "Run Preflow: " << ti << '\n';
    91   if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n';
    92 }
    93 
    94 template<class Value, class LargeValue>
    95 void solve_min(ArgParser &ap, std::istream &is, std::ostream &,
    96                Value infty, DimacsDescriptor &desc)
    97 {
    98   bool report = !ap.given("q");
    99   Digraph g;
   100   Digraph::ArcMap<Value> lower(g), cap(g), cost(g);
   101   Digraph::NodeMap<Value> sup(g);
   102   Timer ti;
   103 
   104   ti.restart();
   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   }
   118   if (report) std::cerr << "Read the file: " << ti << '\n';
   119 
   120   typedef NetworkSimplex<Digraph, Value> MCF;
   121   ti.restart();
   122   MCF ns(g);
   123   ns.lowerMap(lower).upperMap(cap).costMap(cost).supplyMap(sup);
   124   if (sum_sup > 0) ns.supplyType(ns.LEQ);
   125   if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n';
   126   ti.restart();
   127   typename MCF::ProblemType res = ns.run();
   128   if (report) {
   129     std::cerr << "Run NetworkSimplex: " << ti << "\n\n";
   130     std::cerr << "Feasible flow: " << (res == MCF::OPTIMAL ? "found" :
   131                                        "not found") << '\n';
   132     if (res) std::cerr << "Min flow cost: "
   133                        << ns.template totalCost<LargeValue>() << '\n';
   134   }
   135 }
   136 
   137 void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
   138               DimacsDescriptor &desc)
   139 {
   140   bool report = !ap.given("q");
   141   Graph g;
   142   Timer ti;
   143   ti.restart();
   144   readDimacsMat(is, g, desc);
   145   if(report) std::cerr << "Read the file: " << ti << '\n';
   146   ti.restart();
   147   MaxMatching<Graph> mat(g);
   148   if(report) std::cerr << "Setup MaxMatching class: " << ti << '\n';
   149   ti.restart();
   150   mat.run();
   151   if(report) std::cerr << "Run MaxMatching: " << ti << '\n';
   152   if(report) std::cerr << "\nCardinality of max matching: "
   153                        << mat.matchingSize() << '\n';
   154 }
   155 
   156 
   157 template<class Value, class LargeValue>
   158 void solve(ArgParser &ap, std::istream &is, std::ostream &os,
   159            DimacsDescriptor &desc)
   160 {
   161   std::stringstream iss(static_cast<std::string>(ap["infcap"]));
   162   Value infty;
   163   iss >> infty;
   164   if(iss.fail())
   165     {
   166       std::cerr << "Cannot interpret '"
   167                 << static_cast<std::string>(ap["infcap"]) << "' as infinite"
   168                 << std::endl;
   169       exit(1);
   170     }
   171 
   172   switch(desc.type)
   173     {
   174     case DimacsDescriptor::MIN:
   175       solve_min<Value, LargeValue>(ap,is,os,infty,desc);
   176       break;
   177     case DimacsDescriptor::MAX:
   178       solve_max<Value>(ap,is,os,infty,desc);
   179       break;
   180     case DimacsDescriptor::SP:
   181       solve_sp<Value>(ap,is,os,desc);
   182       break;
   183     case DimacsDescriptor::MAT:
   184       solve_mat(ap,is,os,desc);
   185       break;
   186     default:
   187       break;
   188     }
   189 }
   190 
   191 int main(int argc, const char *argv[]) {
   192 
   193   std::string inputName;
   194   std::string outputName;
   195 
   196   ArgParser ap(argc, argv);
   197   ap.other("[INFILE [OUTFILE]]",
   198            "If either the INFILE or OUTFILE file is missing the standard\n"
   199            "     input/output will be used instead.")
   200     .boolOption("q", "Do not print any report")
   201     .boolOption("int","Use 'int' for capacities, costs etc. (default)")
   202     .optionGroup("datatype","int")
   203 #ifdef LEMON_HAVE_LONG_LONG
   204     .boolOption("long","Use 'long long' for capacities, costs etc.")
   205     .optionGroup("datatype","long")
   206 #endif
   207     .boolOption("double","Use 'double' for capacities, costs etc.")
   208     .optionGroup("datatype","double")
   209     .boolOption("ldouble","Use 'long double' for capacities, costs etc.")
   210     .optionGroup("datatype","ldouble")
   211     .onlyOneGroup("datatype")
   212     .stringOption("infcap","Value used for 'very high' capacities","0")
   213     .run();
   214 
   215   std::ifstream input;
   216   std::ofstream output;
   217 
   218   switch(ap.files().size())
   219     {
   220     case 2:
   221       output.open(ap.files()[1].c_str());
   222       if (!output) {
   223         throw IoError("Cannot open the file for writing", ap.files()[1]);
   224       }
   225       // fall through
   226     case 1:
   227       input.open(ap.files()[0].c_str());
   228       if (!input) {
   229         throw IoError("File cannot be found", ap.files()[0]);
   230       }
   231       // fall through
   232     case 0:
   233       break;
   234     default:
   235       std::cerr << ap.commandName() << ": too many arguments\n";
   236       return 1;
   237     }
   238   std::istream& is = (ap.files().size()<1 ? std::cin : input);
   239   std::ostream& os = (ap.files().size()<2 ? std::cout : output);
   240 
   241   DimacsDescriptor desc = dimacsType(is);
   242 
   243   if(!ap.given("q"))
   244     {
   245       std::cout << "Problem type: ";
   246       switch(desc.type)
   247         {
   248         case DimacsDescriptor::MIN:
   249           std::cout << "min";
   250           break;
   251         case DimacsDescriptor::MAX:
   252           std::cout << "max";
   253           break;
   254         case DimacsDescriptor::SP:
   255           std::cout << "sp";
   256           break;
   257         case DimacsDescriptor::MAT:
   258           std::cout << "mat";
   259           break;
   260         default:
   261           exit(1);
   262           break;
   263         }
   264       std::cout << "\nNum of nodes: " << desc.nodeNum;
   265       std::cout << "\nNum of arcs:  " << desc.edgeNum;
   266       std::cout << "\n\n";
   267     }
   268 
   269   if(ap.given("double"))
   270     solve<double, double>(ap,is,os,desc);
   271   else if(ap.given("ldouble"))
   272     solve<long double, long double>(ap,is,os,desc);
   273 #ifdef LEMON_HAVE_LONG_LONG
   274   else if(ap.given("long"))
   275     solve<long long, long long>(ap,is,os,desc);
   276   else solve<int, long long>(ap,is,os,desc);
   277 #else
   278   else solve<int, long>(ap,is,os,desc);
   279 #endif
   280 
   281   return 0;
   282 }