tools/dimacs-solver.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 03 Apr 2009 18:59:15 +0200
changeset 655 6ac5d9ae1d3d
parent 649 a79ef774fae1
child 658 85cb3aa71cce
permissions -rw-r--r--
Support real types + numerical stability fix in NS (#254)

- Real types are supported by appropriate inicialization.
- A feature of the XTI spanning tree structure is removed to ensure
numerical stability (could cause problems using integer types).
The node potentials are updated always on the lower subtree,
in order to prevent overflow problems.
The former method isn't notably faster during to our tests.
     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 #include <lemon/network_simplex.h>
    48 
    49 using namespace lemon;
    50 typedef SmartDigraph Digraph;
    51 DIGRAPH_TYPEDEFS(Digraph);
    52 typedef SmartGraph Graph;
    53 
    54 template<class Value>
    55 void solve_sp(ArgParser &ap, std::istream &is, std::ostream &,
    56               DimacsDescriptor &desc)
    57 {
    58   bool report = !ap.given("q");
    59   Digraph g;
    60   Node s;
    61   Digraph::ArcMap<Value> len(g);
    62   Timer t;
    63   t.restart();
    64   readDimacsSp(is, g, len, s, desc);
    65   if(report) std::cerr << "Read the file: " << t << '\n';
    66   t.restart();
    67   Dijkstra<Digraph, Digraph::ArcMap<Value> > dij(g,len);
    68   if(report) std::cerr << "Setup Dijkstra class: " << t << '\n';
    69   t.restart();
    70   dij.run(s);
    71   if(report) std::cerr << "Run Dijkstra: " << t << '\n';
    72 }
    73 
    74 template<class Value>
    75 void solve_max(ArgParser &ap, std::istream &is, std::ostream &,
    76               DimacsDescriptor &desc)
    77 {
    78   bool report = !ap.given("q");
    79   Digraph g;
    80   Node s,t;
    81   Digraph::ArcMap<Value> cap(g);
    82   Timer ti;
    83   ti.restart();
    84   readDimacsMax(is, g, cap, s, t, desc);
    85   if(report) std::cerr << "Read the file: " << ti << '\n';
    86   ti.restart();
    87   Preflow<Digraph, Digraph::ArcMap<Value> > pre(g,cap,s,t);
    88   if(report) std::cerr << "Setup Preflow class: " << ti << '\n';
    89   ti.restart();
    90   pre.run();
    91   if(report) std::cerr << "Run Preflow: " << ti << '\n';
    92   if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n';  
    93 }
    94 
    95 template<class Value>
    96 void solve_min(ArgParser &ap, std::istream &is, std::ostream &,
    97                DimacsDescriptor &desc)
    98 {
    99   bool report = !ap.given("q");
   100   Digraph g;
   101   Digraph::ArcMap<Value> lower(g), cap(g), cost(g);
   102   Digraph::NodeMap<Value> sup(g);
   103   Timer ti;
   104   ti.restart();
   105   readDimacsMin(is, g, lower, cap, cost, sup, desc);
   106   if (report) std::cerr << "Read the file: " << ti << '\n';
   107   ti.restart();
   108   NetworkSimplex<Digraph, Value> ns(g);
   109   ns.lowerMap(lower).capacityMap(cap).costMap(cost).supplyMap(sup);
   110   if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n';
   111   ti.restart();
   112   ns.run();
   113   if (report) std::cerr << "Run NetworkSimplex: " << ti << '\n';
   114   if (report) std::cerr << "\nMin flow cost: " << ns.totalCost() << '\n';
   115 }
   116 
   117 void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
   118               DimacsDescriptor &desc)
   119 {
   120   bool report = !ap.given("q");
   121   Graph g;
   122   Timer ti;
   123   ti.restart();
   124   readDimacsMat(is, g, desc);
   125   if(report) std::cerr << "Read the file: " << ti << '\n';
   126   ti.restart();
   127   MaxMatching<Graph> mat(g);
   128   if(report) std::cerr << "Setup MaxMatching class: " << ti << '\n';
   129   ti.restart();
   130   mat.run();
   131   if(report) std::cerr << "Run MaxMatching: " << ti << '\n';
   132   if(report) std::cerr << "\nCardinality of max matching: "
   133                        << mat.matchingSize() << '\n';  
   134 }
   135 
   136 
   137 template<class Value>
   138 void solve(ArgParser &ap, std::istream &is, std::ostream &os,
   139            DimacsDescriptor &desc)
   140 {
   141   switch(desc.type)
   142     {
   143     case DimacsDescriptor::MIN:
   144       solve_min<Value>(ap,is,os,desc);
   145       break;
   146     case DimacsDescriptor::MAX:
   147       solve_max<Value>(ap,is,os,desc);
   148       break;
   149     case DimacsDescriptor::SP:
   150       solve_sp<Value>(ap,is,os,desc);
   151       break;
   152     case DimacsDescriptor::MAT:
   153       solve_mat(ap,is,os,desc);
   154       break;
   155     default:
   156       break;
   157     }
   158 }
   159 
   160 int main(int argc, const char *argv[]) {
   161   typedef SmartDigraph Digraph;
   162 
   163   typedef Digraph::Arc Arc;
   164 
   165   std::string inputName;
   166   std::string outputName;
   167 
   168   ArgParser ap(argc, argv);
   169   ap.other("[INFILE [OUTFILE]]",
   170            "If either the INFILE or OUTFILE file is missing the standard\n"
   171            "     input/output will be used instead.")
   172     .boolOption("q", "Do not print any report")
   173     .boolOption("int","Use 'int' for capacities, costs etc. (default)")
   174     .optionGroup("datatype","int")
   175 #ifdef HAVE_LONG_LONG
   176     .boolOption("long","Use 'long long' for capacities, costs etc.")
   177     .optionGroup("datatype","long")
   178 #endif
   179     .boolOption("double","Use 'double' for capacities, costs etc.")
   180     .optionGroup("datatype","double")
   181     .boolOption("ldouble","Use 'long double' for capacities, costs etc.")
   182     .optionGroup("datatype","ldouble")
   183     .onlyOneGroup("datatype")
   184     .run();
   185 
   186   std::ifstream input;
   187   std::ofstream output;
   188 
   189   switch(ap.files().size())
   190     {
   191     case 2:
   192       output.open(ap.files()[1].c_str());
   193       if (!output) {
   194         throw IoError("Cannot open the file for writing", ap.files()[1]);
   195       }
   196     case 1:
   197       input.open(ap.files()[0].c_str());
   198       if (!input) {
   199         throw IoError("File cannot be found", ap.files()[0]);
   200       }
   201     case 0:
   202       break;
   203     default:
   204       std::cerr << ap.commandName() << ": too many arguments\n";
   205       return 1;
   206     }
   207   std::istream& is = (ap.files().size()<1 ? std::cin : input);
   208   std::ostream& os = (ap.files().size()<2 ? std::cout : output);
   209 
   210   DimacsDescriptor desc = dimacsType(is);
   211   
   212   if(!ap.given("q"))
   213     {
   214       std::cout << "Problem type: ";
   215       switch(desc.type)
   216         {
   217         case DimacsDescriptor::MIN:
   218           std::cout << "min";
   219           break;
   220         case DimacsDescriptor::MAX:
   221           std::cout << "max";
   222           break;
   223         case DimacsDescriptor::SP:
   224           std::cout << "sp";
   225         case DimacsDescriptor::MAT:
   226           std::cout << "mat";
   227           break;
   228         default:
   229           exit(1);
   230           break;
   231         }
   232       std::cout << "\nNum of nodes: " << desc.nodeNum;
   233       std::cout << "\nNum of arcs:  " << desc.edgeNum;
   234       std::cout << "\n\n";
   235     }
   236     
   237   if(ap.given("double"))
   238     solve<double>(ap,is,os,desc);
   239   else if(ap.given("ldouble"))
   240     solve<long double>(ap,is,os,desc);
   241 #ifdef HAVE_LONG_LONG
   242   else if(ap.given("long"))
   243     solve<long long>(ap,is,os,desc);
   244 #endif
   245   else solve<int>(ap,is,os,desc);
   246 
   247   return 0;
   248 }