tools/dimacs-solver.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Wed, 15 Apr 2009 11:41:25 +0200
changeset 591 493533ead9df
parent 569 24682336c38e
child 594 d657c71db7db
permissions -rw-r--r--
Bug fix in the Euler iterators (#264)
Handle the case when the first node is isolated.
     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-2009
     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/max_matching.h>
    46 
    47 using namespace lemon;
    48 typedef SmartDigraph Digraph;
    49 DIGRAPH_TYPEDEFS(Digraph);
    50 typedef SmartGraph Graph;
    51 
    52 template<class Value>
    53 void solve_sp(ArgParser &ap, std::istream &is, std::ostream &,
    54               DimacsDescriptor &desc)
    55 {
    56   bool report = !ap.given("q");
    57   Digraph g;
    58   Node s;
    59   Digraph::ArcMap<Value> len(g);
    60   Timer t;
    61   t.restart();
    62   readDimacsSp(is, g, len, s, desc);
    63   if(report) std::cerr << "Read the file: " << t << '\n';
    64   t.restart();
    65   Dijkstra<Digraph, Digraph::ArcMap<Value> > dij(g,len);
    66   if(report) std::cerr << "Setup Dijkstra class: " << t << '\n';
    67   t.restart();
    68   dij.run(s);
    69   if(report) std::cerr << "Run Dijkstra: " << t << '\n';
    70 }
    71 
    72 template<class Value>
    73 void solve_max(ArgParser &ap, std::istream &is, std::ostream &,
    74                Value infty, DimacsDescriptor &desc)
    75 {
    76   bool report = !ap.given("q");
    77   Digraph g;
    78   Node s,t;
    79   Digraph::ArcMap<Value> cap(g);
    80   Timer ti;
    81   ti.restart();
    82   readDimacsMax(is, g, cap, s, t, infty, desc);
    83   if(report) std::cerr << "Read the file: " << ti << '\n';
    84   ti.restart();
    85   Preflow<Digraph, Digraph::ArcMap<Value> > pre(g,cap,s,t);
    86   if(report) std::cerr << "Setup Preflow class: " << ti << '\n';
    87   ti.restart();
    88   pre.run();
    89   if(report) std::cerr << "Run Preflow: " << ti << '\n';
    90   if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n';  
    91 }
    92 
    93 void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
    94               DimacsDescriptor &desc)
    95 {
    96   bool report = !ap.given("q");
    97   Graph g;
    98   Timer ti;
    99   ti.restart();
   100   readDimacsMat(is, g, desc);
   101   if(report) std::cerr << "Read the file: " << ti << '\n';
   102   ti.restart();
   103   MaxMatching<Graph> mat(g);
   104   if(report) std::cerr << "Setup MaxMatching class: " << ti << '\n';
   105   ti.restart();
   106   mat.run();
   107   if(report) std::cerr << "Run MaxMatching: " << ti << '\n';
   108   if(report) std::cerr << "\nCardinality of max matching: "
   109                        << mat.matchingSize() << '\n';  
   110 }
   111 
   112 
   113 template<class Value>
   114 void solve(ArgParser &ap, std::istream &is, std::ostream &os,
   115            DimacsDescriptor &desc)
   116 {
   117   std::stringstream iss(static_cast<std::string>(ap["infcap"]));
   118   Value infty;
   119   iss >> infty;
   120   if(iss.fail())
   121     {
   122       std::cerr << "Cannot interpret '"
   123                 << static_cast<std::string>(ap["infcap"]) << "' as infinite"
   124                 << std::endl;
   125       exit(1);
   126     }
   127   
   128   switch(desc.type)
   129     {
   130     case DimacsDescriptor::MIN:
   131       std::cerr <<
   132         "\n\n Sorry, the min. cost flow solver is not yet available.\n";
   133       break;
   134     case DimacsDescriptor::MAX:
   135       solve_max<Value>(ap,is,os,infty,desc);
   136       break;
   137     case DimacsDescriptor::SP:
   138       solve_sp<Value>(ap,is,os,desc);
   139       break;
   140     case DimacsDescriptor::MAT:
   141       solve_mat(ap,is,os,desc);
   142       break;
   143     default:
   144       break;
   145     }
   146 }
   147 
   148 int main(int argc, const char *argv[]) {
   149   typedef SmartDigraph Digraph;
   150 
   151   typedef Digraph::Arc Arc;
   152 
   153   std::string inputName;
   154   std::string outputName;
   155 
   156   ArgParser ap(argc, argv);
   157   ap.other("[INFILE [OUTFILE]]",
   158            "If either the INFILE or OUTFILE file is missing the standard\n"
   159            "     input/output will be used instead.")
   160     .boolOption("q", "Do not print any report")
   161     .boolOption("int","Use 'int' for capacities, costs etc. (default)")
   162     .optionGroup("datatype","int")
   163 #ifdef HAVE_LONG_LONG
   164     .boolOption("long","Use 'long long' for capacities, costs etc.")
   165     .optionGroup("datatype","long")
   166 #endif
   167     .boolOption("double","Use 'double' for capacities, costs etc.")
   168     .optionGroup("datatype","double")
   169     .boolOption("ldouble","Use 'long double' for capacities, costs etc.")
   170     .optionGroup("datatype","ldouble")
   171     .onlyOneGroup("datatype")
   172     .stringOption("infcap","Value used for 'very high' capacities","0")
   173     .run();
   174 
   175   std::ifstream input;
   176   std::ofstream output;
   177 
   178   switch(ap.files().size())
   179     {
   180     case 2:
   181       output.open(ap.files()[1].c_str());
   182       if (!output) {
   183         throw IoError("Cannot open the file for writing", ap.files()[1]);
   184       }
   185     case 1:
   186       input.open(ap.files()[0].c_str());
   187       if (!input) {
   188         throw IoError("File cannot be found", ap.files()[0]);
   189       }
   190     case 0:
   191       break;
   192     default:
   193       std::cerr << ap.commandName() << ": too many arguments\n";
   194       return 1;
   195     }
   196   std::istream& is = (ap.files().size()<1 ? std::cin : input);
   197   std::ostream& os = (ap.files().size()<2 ? std::cout : output);
   198 
   199   DimacsDescriptor desc = dimacsType(is);
   200   
   201   if(!ap.given("q"))
   202     {
   203       std::cout << "Problem type: ";
   204       switch(desc.type)
   205         {
   206         case DimacsDescriptor::MIN:
   207           std::cout << "min";
   208           break;
   209         case DimacsDescriptor::MAX:
   210           std::cout << "max";
   211           break;
   212         case DimacsDescriptor::SP:
   213           std::cout << "sp";
   214         case DimacsDescriptor::MAT:
   215           std::cout << "mat";
   216           break;
   217         default:
   218           exit(1);
   219           break;
   220         }
   221       std::cout << "\nNum of nodes: " << desc.nodeNum;
   222       std::cout << "\nNum of arcs:  " << desc.edgeNum;
   223       std::cout << "\n\n";
   224     }
   225     
   226   if(ap.given("double"))
   227     solve<double>(ap,is,os,desc);
   228   else if(ap.given("ldouble"))
   229     solve<long double>(ap,is,os,desc);
   230 #ifdef HAVE_LONG_LONG
   231   else if(ap.given("long"))
   232     solve<long long>(ap,is,os,desc);
   233 #endif
   234   else solve<int>(ap,is,os,desc);
   235 
   236   return 0;
   237 }