tools/dimacs-solver.cc
author Akos Ladanyi <ladanyi@tmit.bme.hu>
Thu, 23 Apr 2009 07:28:56 +0100
changeset 619 ec817dfc2cb7
parent 594 d657c71db7db
parent 605 5232721b3f14
child 614 19b6f20e0ea2
permissions -rw-r--r--
FindGLPK improvements (#256)
     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/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>
    95 void solve_min(ArgParser &ap, std::istream &is, std::ostream &,
    96                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   ti.restart();
   104   readDimacsMin(is, g, lower, cap, cost, sup, 0, desc);
   105   if (report) std::cerr << "Read the file: " << ti << '\n';
   106   ti.restart();
   107   NetworkSimplex<Digraph, Value> ns(g);
   108   ns.lowerMap(lower).capacityMap(cap).costMap(cost).supplyMap(sup);
   109   if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n';
   110   ti.restart();
   111   ns.run();
   112   if (report) std::cerr << "Run NetworkSimplex: " << ti << '\n';
   113   if (report) std::cerr << "\nMin flow cost: " << ns.totalCost() << '\n';
   114 }
   115 
   116 void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
   117               DimacsDescriptor &desc)
   118 {
   119   bool report = !ap.given("q");
   120   Graph g;
   121   Timer ti;
   122   ti.restart();
   123   readDimacsMat(is, g, desc);
   124   if(report) std::cerr << "Read the file: " << ti << '\n';
   125   ti.restart();
   126   MaxMatching<Graph> mat(g);
   127   if(report) std::cerr << "Setup MaxMatching class: " << ti << '\n';
   128   ti.restart();
   129   mat.run();
   130   if(report) std::cerr << "Run MaxMatching: " << ti << '\n';
   131   if(report) std::cerr << "\nCardinality of max matching: "
   132                        << mat.matchingSize() << '\n';  
   133 }
   134 
   135 
   136 template<class Value>
   137 void solve(ArgParser &ap, std::istream &is, std::ostream &os,
   138            DimacsDescriptor &desc)
   139 {
   140   std::stringstream iss(static_cast<std::string>(ap["infcap"]));
   141   Value infty;
   142   iss >> infty;
   143   if(iss.fail())
   144     {
   145       std::cerr << "Cannot interpret '"
   146                 << static_cast<std::string>(ap["infcap"]) << "' as infinite"
   147                 << std::endl;
   148       exit(1);
   149     }
   150   
   151   switch(desc.type)
   152     {
   153     case DimacsDescriptor::MIN:
   154       solve_min<Value>(ap,is,os,desc);
   155       break;
   156     case DimacsDescriptor::MAX:
   157       solve_max<Value>(ap,is,os,infty,desc);
   158       break;
   159     case DimacsDescriptor::SP:
   160       solve_sp<Value>(ap,is,os,desc);
   161       break;
   162     case DimacsDescriptor::MAT:
   163       solve_mat(ap,is,os,desc);
   164       break;
   165     default:
   166       break;
   167     }
   168 }
   169 
   170 int main(int argc, const char *argv[]) {
   171   typedef SmartDigraph Digraph;
   172 
   173   typedef Digraph::Arc Arc;
   174 
   175   std::string inputName;
   176   std::string outputName;
   177 
   178   ArgParser ap(argc, argv);
   179   ap.other("[INFILE [OUTFILE]]",
   180            "If either the INFILE or OUTFILE file is missing the standard\n"
   181            "     input/output will be used instead.")
   182     .boolOption("q", "Do not print any report")
   183     .boolOption("int","Use 'int' for capacities, costs etc. (default)")
   184     .optionGroup("datatype","int")
   185 #ifdef HAVE_LONG_LONG
   186     .boolOption("long","Use 'long long' for capacities, costs etc.")
   187     .optionGroup("datatype","long")
   188 #endif
   189     .boolOption("double","Use 'double' for capacities, costs etc.")
   190     .optionGroup("datatype","double")
   191     .boolOption("ldouble","Use 'long double' for capacities, costs etc.")
   192     .optionGroup("datatype","ldouble")
   193     .onlyOneGroup("datatype")
   194     .stringOption("infcap","Value used for 'very high' capacities","0")
   195     .run();
   196 
   197   std::ifstream input;
   198   std::ofstream output;
   199 
   200   switch(ap.files().size())
   201     {
   202     case 2:
   203       output.open(ap.files()[1].c_str());
   204       if (!output) {
   205         throw IoError("Cannot open the file for writing", ap.files()[1]);
   206       }
   207     case 1:
   208       input.open(ap.files()[0].c_str());
   209       if (!input) {
   210         throw IoError("File cannot be found", ap.files()[0]);
   211       }
   212     case 0:
   213       break;
   214     default:
   215       std::cerr << ap.commandName() << ": too many arguments\n";
   216       return 1;
   217     }
   218   std::istream& is = (ap.files().size()<1 ? std::cin : input);
   219   std::ostream& os = (ap.files().size()<2 ? std::cout : output);
   220 
   221   DimacsDescriptor desc = dimacsType(is);
   222   
   223   if(!ap.given("q"))
   224     {
   225       std::cout << "Problem type: ";
   226       switch(desc.type)
   227         {
   228         case DimacsDescriptor::MIN:
   229           std::cout << "min";
   230           break;
   231         case DimacsDescriptor::MAX:
   232           std::cout << "max";
   233           break;
   234         case DimacsDescriptor::SP:
   235           std::cout << "sp";
   236         case DimacsDescriptor::MAT:
   237           std::cout << "mat";
   238           break;
   239         default:
   240           exit(1);
   241           break;
   242         }
   243       std::cout << "\nNum of nodes: " << desc.nodeNum;
   244       std::cout << "\nNum of arcs:  " << desc.edgeNum;
   245       std::cout << "\n\n";
   246     }
   247     
   248   if(ap.given("double"))
   249     solve<double>(ap,is,os,desc);
   250   else if(ap.given("ldouble"))
   251     solve<long double>(ap,is,os,desc);
   252 #ifdef HAVE_LONG_LONG
   253   else if(ap.given("long"))
   254     solve<long long>(ap,is,os,desc);
   255 #endif
   256   else solve<int>(ap,is,os,desc);
   257 
   258   return 0;
   259 }