tools/dimacs-solver.cc
author Alpar Juttner <alpar@cs.elte.hu>
Fri, 09 Aug 2013 11:29:40 +0200
changeset 1271 fb1c7da561ce
parent 1270 dceba191c00d
child 1386 ad22262328b3
permissions -rw-r--r--
Remove long lines (from all but one file)
     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     case 1:
   226       input.open(ap.files()[0].c_str());
   227       if (!input) {
   228         throw IoError("File cannot be found", ap.files()[0]);
   229       }
   230     case 0:
   231       break;
   232     default:
   233       std::cerr << ap.commandName() << ": too many arguments\n";
   234       return 1;
   235     }
   236   std::istream& is = (ap.files().size()<1 ? std::cin : input);
   237   std::ostream& os = (ap.files().size()<2 ? std::cout : output);
   238 
   239   DimacsDescriptor desc = dimacsType(is);
   240 
   241   if(!ap.given("q"))
   242     {
   243       std::cout << "Problem type: ";
   244       switch(desc.type)
   245         {
   246         case DimacsDescriptor::MIN:
   247           std::cout << "min";
   248           break;
   249         case DimacsDescriptor::MAX:
   250           std::cout << "max";
   251           break;
   252         case DimacsDescriptor::SP:
   253           std::cout << "sp";
   254         case DimacsDescriptor::MAT:
   255           std::cout << "mat";
   256           break;
   257         default:
   258           exit(1);
   259           break;
   260         }
   261       std::cout << "\nNum of nodes: " << desc.nodeNum;
   262       std::cout << "\nNum of arcs:  " << desc.edgeNum;
   263       std::cout << "\n\n";
   264     }
   265 
   266   if(ap.given("double"))
   267     solve<double, double>(ap,is,os,desc);
   268   else if(ap.given("ldouble"))
   269     solve<long double, long double>(ap,is,os,desc);
   270 #ifdef LEMON_HAVE_LONG_LONG
   271   else if(ap.given("long"))
   272     solve<long long, long long>(ap,is,os,desc);
   273   else solve<int, long long>(ap,is,os,desc);
   274 #else
   275   else solve<int, long>(ap,is,os,desc);
   276 #endif
   277 
   278   return 0;
   279 }