tools/dimacs-solver.cc
author Balazs Dezso <deba@inf.elte.hu>
Fri, 19 Mar 2010 18:23:47 +0100
changeset 1042 d450a02728d0
parent 877 141f9c0db4a3
parent 1005 c5990f454032
child 1092 dceba191c00d
permissions -rw-r--r--
Bidirectional iterator support for radixSort() (#362)
     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-2010
     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" : "not found") << '\n';
   131     if (res) std::cerr << "Min flow cost: "
   132                        << ns.template totalCost<LargeValue>() << '\n';
   133   }
   134 }
   135 
   136 void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
   137               DimacsDescriptor &desc)
   138 {
   139   bool report = !ap.given("q");
   140   Graph g;
   141   Timer ti;
   142   ti.restart();
   143   readDimacsMat(is, g, desc);
   144   if(report) std::cerr << "Read the file: " << ti << '\n';
   145   ti.restart();
   146   MaxMatching<Graph> mat(g);
   147   if(report) std::cerr << "Setup MaxMatching class: " << ti << '\n';
   148   ti.restart();
   149   mat.run();
   150   if(report) std::cerr << "Run MaxMatching: " << ti << '\n';
   151   if(report) std::cerr << "\nCardinality of max matching: "
   152                        << mat.matchingSize() << '\n';
   153 }
   154 
   155 
   156 template<class Value, class LargeValue>
   157 void solve(ArgParser &ap, std::istream &is, std::ostream &os,
   158            DimacsDescriptor &desc)
   159 {
   160   std::stringstream iss(static_cast<std::string>(ap["infcap"]));
   161   Value infty;
   162   iss >> infty;
   163   if(iss.fail())
   164     {
   165       std::cerr << "Cannot interpret '"
   166                 << static_cast<std::string>(ap["infcap"]) << "' as infinite"
   167                 << std::endl;
   168       exit(1);
   169     }
   170 
   171   switch(desc.type)
   172     {
   173     case DimacsDescriptor::MIN:
   174       solve_min<Value, LargeValue>(ap,is,os,infty,desc);
   175       break;
   176     case DimacsDescriptor::MAX:
   177       solve_max<Value>(ap,is,os,infty,desc);
   178       break;
   179     case DimacsDescriptor::SP:
   180       solve_sp<Value>(ap,is,os,desc);
   181       break;
   182     case DimacsDescriptor::MAT:
   183       solve_mat(ap,is,os,desc);
   184       break;
   185     default:
   186       break;
   187     }
   188 }
   189 
   190 int main(int argc, const char *argv[]) {
   191 
   192   std::string inputName;
   193   std::string outputName;
   194 
   195   ArgParser ap(argc, argv);
   196   ap.other("[INFILE [OUTFILE]]",
   197            "If either the INFILE or OUTFILE file is missing the standard\n"
   198            "     input/output will be used instead.")
   199     .boolOption("q", "Do not print any report")
   200     .boolOption("int","Use 'int' for capacities, costs etc. (default)")
   201     .optionGroup("datatype","int")
   202 #ifdef LEMON_HAVE_LONG_LONG
   203     .boolOption("long","Use 'long long' for capacities, costs etc.")
   204     .optionGroup("datatype","long")
   205 #endif
   206     .boolOption("double","Use 'double' for capacities, costs etc.")
   207     .optionGroup("datatype","double")
   208     .boolOption("ldouble","Use 'long double' for capacities, costs etc.")
   209     .optionGroup("datatype","ldouble")
   210     .onlyOneGroup("datatype")
   211     .stringOption("infcap","Value used for 'very high' capacities","0")
   212     .run();
   213 
   214   std::ifstream input;
   215   std::ofstream output;
   216 
   217   switch(ap.files().size())
   218     {
   219     case 2:
   220       output.open(ap.files()[1].c_str());
   221       if (!output) {
   222         throw IoError("Cannot open the file for writing", ap.files()[1]);
   223       }
   224     case 1:
   225       input.open(ap.files()[0].c_str());
   226       if (!input) {
   227         throw IoError("File cannot be found", ap.files()[0]);
   228       }
   229     case 0:
   230       break;
   231     default:
   232       std::cerr << ap.commandName() << ": too many arguments\n";
   233       return 1;
   234     }
   235   std::istream& is = (ap.files().size()<1 ? std::cin : input);
   236   std::ostream& os = (ap.files().size()<2 ? std::cout : output);
   237 
   238   DimacsDescriptor desc = dimacsType(is);
   239 
   240   if(!ap.given("q"))
   241     {
   242       std::cout << "Problem type: ";
   243       switch(desc.type)
   244         {
   245         case DimacsDescriptor::MIN:
   246           std::cout << "min";
   247           break;
   248         case DimacsDescriptor::MAX:
   249           std::cout << "max";
   250           break;
   251         case DimacsDescriptor::SP:
   252           std::cout << "sp";
   253         case DimacsDescriptor::MAT:
   254           std::cout << "mat";
   255           break;
   256         default:
   257           exit(1);
   258           break;
   259         }
   260       std::cout << "\nNum of nodes: " << desc.nodeNum;
   261       std::cout << "\nNum of arcs:  " << desc.edgeNum;
   262       std::cout << "\n\n";
   263     }
   264 
   265   if(ap.given("double"))
   266     solve<double, double>(ap,is,os,desc);
   267   else if(ap.given("ldouble"))
   268     solve<long double, long double>(ap,is,os,desc);
   269 #ifdef LEMON_HAVE_LONG_LONG
   270   else if(ap.given("long"))
   271     solve<long long, long long>(ap,is,os,desc);
   272   else solve<int, long long>(ap,is,os,desc);
   273 #else
   274   else solve<int, long>(ap,is,os,desc);
   275 #endif
   276 
   277   return 0;
   278 }