tools/dimacs-solver.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 24 Feb 2009 09:46:02 +0100
changeset 601 e8349c6f12ca
parent 526 28b154307c0d
child 561 6e0525ec5355
child 602 a79ef774fae1
permissions -rw-r--r--
Port NetworkSimplex from SVN -r3520 (#234)
     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               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, 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   switch(desc.type)
   119     {
   120     case DimacsDescriptor::MIN:
   121       std::cerr <<
   122         "\n\n Sorry, the min. cost flow solver is not yet available.\n";
   123       break;
   124     case DimacsDescriptor::MAX:
   125       solve_max<Value>(ap,is,os,desc);
   126       break;
   127     case DimacsDescriptor::SP:
   128       solve_sp<Value>(ap,is,os,desc);
   129       break;
   130     case DimacsDescriptor::MAT:
   131       solve_mat(ap,is,os,desc);
   132       break;
   133     default:
   134       break;
   135     }
   136 }
   137 
   138 int main(int argc, const char *argv[]) {
   139   typedef SmartDigraph Digraph;
   140 
   141   typedef Digraph::Arc Arc;
   142 
   143   std::string inputName;
   144   std::string outputName;
   145 
   146   ArgParser ap(argc, argv);
   147   ap.other("[INFILE [OUTFILE]]",
   148            "If either the INFILE or OUTFILE file is missing the standard\n"
   149            "     input/output will be used instead.")
   150     .boolOption("q", "Do not print any report")
   151     .boolOption("int","Use 'int' for capacities, costs etc. (default)")
   152     .optionGroup("datatype","int")
   153 #ifdef HAVE_LONG_LONG
   154     .boolOption("long","Use 'long long' for capacities, costs etc.")
   155     .optionGroup("datatype","long")
   156 #endif
   157     .boolOption("double","Use 'double' for capacities, costs etc.")
   158     .optionGroup("datatype","double")
   159     .boolOption("ldouble","Use 'long double' for capacities, costs etc.")
   160     .optionGroup("datatype","ldouble")
   161     .onlyOneGroup("datatype")
   162     .run();
   163 
   164   std::ifstream input;
   165   std::ofstream output;
   166 
   167   switch(ap.files().size())
   168     {
   169     case 2:
   170       output.open(ap.files()[1].c_str());
   171       if (!output) {
   172         throw IoError("Cannot open the file for writing", ap.files()[1]);
   173       }
   174     case 1:
   175       input.open(ap.files()[0].c_str());
   176       if (!input) {
   177         throw IoError("File cannot be found", ap.files()[0]);
   178       }
   179     case 0:
   180       break;
   181     default:
   182       std::cerr << ap.commandName() << ": too many arguments\n";
   183       return 1;
   184     }
   185   std::istream& is = (ap.files().size()<1 ? std::cin : input);
   186   std::ostream& os = (ap.files().size()<2 ? std::cout : output);
   187 
   188   DimacsDescriptor desc = dimacsType(is);
   189   
   190   if(!ap.given("q"))
   191     {
   192       std::cout << "Problem type: ";
   193       switch(desc.type)
   194         {
   195         case DimacsDescriptor::MIN:
   196           std::cout << "min";
   197           break;
   198         case DimacsDescriptor::MAX:
   199           std::cout << "max";
   200           break;
   201         case DimacsDescriptor::SP:
   202           std::cout << "sp";
   203         case DimacsDescriptor::MAT:
   204           std::cout << "mat";
   205           break;
   206         default:
   207           exit(1);
   208           break;
   209         }
   210       std::cout << "\nNum of nodes: " << desc.nodeNum;
   211       std::cout << "\nNum of arcs:  " << desc.edgeNum;
   212       std::cout << "\n\n";
   213     }
   214     
   215   if(ap.given("double"))
   216     solve<double>(ap,is,os,desc);
   217   else if(ap.given("ldouble"))
   218     solve<long double>(ap,is,os,desc);
   219 #ifdef HAVE_LONG_LONG
   220   else if(ap.given("long"))
   221     solve<long long>(ap,is,os,desc);
   222 #endif
   223   else solve<int>(ap,is,os,desc);
   224 
   225   return 0;
   226 }