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