tools/dimacs-solver.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Wed, 08 Apr 2009 10:42:00 +0200
changeset 621 003367ffe66e
parent 608 6e0525ec5355
child 631 33c6b6e755cd
permissions -rw-r--r--
Add RangeIdMap, CrossRefMap to the rename script (#160)
     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 /// \verbatim
    27 ///  dimacs-solver --help
    28 /// \endverbatim
    29 /// for more info on usage.
    30 ///
    31 
    32 #include <iostream>
    33 #include <fstream>
    34 #include <cstring>
    35 
    36 #include <lemon/smart_graph.h>
    37 #include <lemon/dimacs.h>
    38 #include <lemon/lgf_writer.h>
    39 #include <lemon/time_measure.h>
    40 
    41 #include <lemon/arg_parser.h>
    42 #include <lemon/error.h>
    43 
    44 #include <lemon/dijkstra.h>
    45 #include <lemon/preflow.h>
    46 #include <lemon/max_matching.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 void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
    95               DimacsDescriptor &desc)
    96 {
    97   bool report = !ap.given("q");
    98   Graph g;
    99   Timer ti;
   100   ti.restart();
   101   readDimacsMat(is, g, desc);
   102   if(report) std::cerr << "Read the file: " << ti << '\n';
   103   ti.restart();
   104   MaxMatching<Graph> mat(g);
   105   if(report) std::cerr << "Setup MaxMatching class: " << ti << '\n';
   106   ti.restart();
   107   mat.run();
   108   if(report) std::cerr << "Run MaxMatching: " << ti << '\n';
   109   if(report) std::cerr << "\nCardinality of max matching: "
   110                        << mat.matchingSize() << '\n';  
   111 }
   112 
   113 
   114 template<class Value>
   115 void solve(ArgParser &ap, std::istream &is, std::ostream &os,
   116            DimacsDescriptor &desc)
   117 {
   118   std::stringstream iss(static_cast<std::string>(ap["infcap"]));
   119   Value infty;
   120   iss >> infty;
   121   if(iss.fail())
   122     {
   123       std::cerr << "Cannot interpret '"
   124                 << static_cast<std::string>(ap["infcap"]) << "' as infinite"
   125                 << std::endl;
   126       exit(1);
   127     }
   128   
   129   switch(desc.type)
   130     {
   131     case DimacsDescriptor::MIN:
   132       std::cerr <<
   133         "\n\n Sorry, the min. cost flow solver is not yet available.\n";
   134       break;
   135     case DimacsDescriptor::MAX:
   136       solve_max<Value>(ap,is,os,infty,desc);
   137       break;
   138     case DimacsDescriptor::SP:
   139       solve_sp<Value>(ap,is,os,desc);
   140       break;
   141     case DimacsDescriptor::MAT:
   142       solve_mat(ap,is,os,desc);
   143       break;
   144     default:
   145       break;
   146     }
   147 }
   148 
   149 int main(int argc, const char *argv[]) {
   150   typedef SmartDigraph Digraph;
   151 
   152   typedef Digraph::Arc Arc;
   153 
   154   std::string inputName;
   155   std::string outputName;
   156 
   157   ArgParser ap(argc, argv);
   158   ap.other("[INFILE [OUTFILE]]",
   159            "If either the INFILE or OUTFILE file is missing the standard\n"
   160            "     input/output will be used instead.")
   161     .boolOption("q", "Do not print any report")
   162     .boolOption("int","Use 'int' for capacities, costs etc. (default)")
   163     .optionGroup("datatype","int")
   164 #ifdef HAVE_LONG_LONG
   165     .boolOption("long","Use 'long long' for capacities, costs etc.")
   166     .optionGroup("datatype","long")
   167 #endif
   168     .boolOption("double","Use 'double' for capacities, costs etc.")
   169     .optionGroup("datatype","double")
   170     .boolOption("ldouble","Use 'long double' for capacities, costs etc.")
   171     .optionGroup("datatype","ldouble")
   172     .onlyOneGroup("datatype")
   173     .stringOption("infcap","Value used for 'very high' capacities","0")
   174     .run();
   175 
   176   std::ifstream input;
   177   std::ofstream output;
   178 
   179   switch(ap.files().size())
   180     {
   181     case 2:
   182       output.open(ap.files()[1].c_str());
   183       if (!output) {
   184         throw IoError("Cannot open the file for writing", ap.files()[1]);
   185       }
   186     case 1:
   187       input.open(ap.files()[0].c_str());
   188       if (!input) {
   189         throw IoError("File cannot be found", ap.files()[0]);
   190       }
   191     case 0:
   192       break;
   193     default:
   194       std::cerr << ap.commandName() << ": too many arguments\n";
   195       return 1;
   196     }
   197   std::istream& is = (ap.files().size()<1 ? std::cin : input);
   198   std::ostream& os = (ap.files().size()<2 ? std::cout : output);
   199 
   200   DimacsDescriptor desc = dimacsType(is);
   201   
   202   if(!ap.given("q"))
   203     {
   204       std::cout << "Problem type: ";
   205       switch(desc.type)
   206         {
   207         case DimacsDescriptor::MIN:
   208           std::cout << "min";
   209           break;
   210         case DimacsDescriptor::MAX:
   211           std::cout << "max";
   212           break;
   213         case DimacsDescriptor::SP:
   214           std::cout << "sp";
   215         case DimacsDescriptor::MAT:
   216           std::cout << "mat";
   217           break;
   218         default:
   219           exit(1);
   220           break;
   221         }
   222       std::cout << "\nNum of nodes: " << desc.nodeNum;
   223       std::cout << "\nNum of arcs:  " << desc.edgeNum;
   224       std::cout << "\n\n";
   225     }
   226     
   227   if(ap.given("double"))
   228     solve<double>(ap,is,os,desc);
   229   else if(ap.given("ldouble"))
   230     solve<long double>(ap,is,os,desc);
   231 #ifdef HAVE_LONG_LONG
   232   else if(ap.given("long"))
   233     solve<long long>(ap,is,os,desc);
   234 #endif
   235   else solve<int>(ap,is,os,desc);
   236 
   237   return 0;
   238 }