tools/dimacs-solver.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Sun, 22 Aug 2010 23:54:10 +0200
changeset 895 dca9eed2c375
parent 846 9d380bf27194
child 1006 764826c6e2b4
permissions -rw-r--r--
Improve the tree update process and a pivot rule (#391)
and make some parts of the code clearer using better names
     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   ti.restart();
   121   NetworkSimplex<Digraph, Value> ns(g);
   122   ns.lowerMap(lower).upperMap(cap).costMap(cost).supplyMap(sup);
   123   if (sum_sup > 0) ns.supplyType(ns.LEQ);
   124   if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n';
   125   ti.restart();
   126   bool res = ns.run();
   127   if (report) {
   128     std::cerr << "Run NetworkSimplex: " << ti << "\n\n";
   129     std::cerr << "Feasible flow: " << (res ? "found" : "not found") << '\n';
   130     if (res) std::cerr << "Min flow cost: "
   131                        << ns.template totalCost<LargeValue>() << '\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, class LargeValue>
   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, LargeValue>(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   typedef SmartDigraph Digraph;
   191 
   192   typedef Digraph::Arc Arc;
   193 
   194   std::string inputName;
   195   std::string outputName;
   196 
   197   ArgParser ap(argc, argv);
   198   ap.other("[INFILE [OUTFILE]]",
   199            "If either the INFILE or OUTFILE file is missing the standard\n"
   200            "     input/output will be used instead.")
   201     .boolOption("q", "Do not print any report")
   202     .boolOption("int","Use 'int' for capacities, costs etc. (default)")
   203     .optionGroup("datatype","int")
   204 #ifdef LEMON_HAVE_LONG_LONG
   205     .boolOption("long","Use 'long long' for capacities, costs etc.")
   206     .optionGroup("datatype","long")
   207 #endif
   208     .boolOption("double","Use 'double' for capacities, costs etc.")
   209     .optionGroup("datatype","double")
   210     .boolOption("ldouble","Use 'long double' for capacities, costs etc.")
   211     .optionGroup("datatype","ldouble")
   212     .onlyOneGroup("datatype")
   213     .stringOption("infcap","Value used for 'very high' capacities","0")
   214     .run();
   215 
   216   std::ifstream input;
   217   std::ofstream output;
   218 
   219   switch(ap.files().size())
   220     {
   221     case 2:
   222       output.open(ap.files()[1].c_str());
   223       if (!output) {
   224         throw IoError("Cannot open the file for writing", ap.files()[1]);
   225       }
   226     case 1:
   227       input.open(ap.files()[0].c_str());
   228       if (!input) {
   229         throw IoError("File cannot be found", ap.files()[0]);
   230       }
   231     case 0:
   232       break;
   233     default:
   234       std::cerr << ap.commandName() << ": too many arguments\n";
   235       return 1;
   236     }
   237   std::istream& is = (ap.files().size()<1 ? std::cin : input);
   238   std::ostream& os = (ap.files().size()<2 ? std::cout : output);
   239 
   240   DimacsDescriptor desc = dimacsType(is);
   241 
   242   if(!ap.given("q"))
   243     {
   244       std::cout << "Problem type: ";
   245       switch(desc.type)
   246         {
   247         case DimacsDescriptor::MIN:
   248           std::cout << "min";
   249           break;
   250         case DimacsDescriptor::MAX:
   251           std::cout << "max";
   252           break;
   253         case DimacsDescriptor::SP:
   254           std::cout << "sp";
   255         case DimacsDescriptor::MAT:
   256           std::cout << "mat";
   257           break;
   258         default:
   259           exit(1);
   260           break;
   261         }
   262       std::cout << "\nNum of nodes: " << desc.nodeNum;
   263       std::cout << "\nNum of arcs:  " << desc.edgeNum;
   264       std::cout << "\n\n";
   265     }
   266 
   267   if(ap.given("double"))
   268     solve<double, double>(ap,is,os,desc);
   269   else if(ap.given("ldouble"))
   270     solve<long double, long double>(ap,is,os,desc);
   271 #ifdef LEMON_HAVE_LONG_LONG
   272   else if(ap.given("long"))
   273     solve<long long, long long>(ap,is,os,desc);
   274   else solve<int, long long>(ap,is,os,desc);
   275 #else
   276   else solve<int, long>(ap,is,os,desc);
   277 #endif
   278 
   279   return 0;
   280 }