tools/dimacs-solver.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Thu, 23 Jul 2009 18:09:41 +0200
changeset 731 7b1a6e963018
parent 687 6c408d864fa1
parent 674 20dac2104519
child 919 9d380bf27194
child 1081 f1398882a928
child 1167 c5990f454032
permissions -rw-r--r--
Fix the implementation and doc of CrossRefMap (#302)

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