tools/dimacs-solver.cc
author Alpar Juttner <alpar@cs.elte.hu>
Mon, 23 Feb 2009 12:33:40 +0000
changeset 530 1c5d6e47921f
parent 440 88ed40ad0d4f
child 532 997a75bac45a
permissions -rw-r--r--
Merge
     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 to LGF converter.
    22 ///
    23 /// This program converts various DIMACS formats to the LEMON Digraph Format
    24 /// (LGF).
    25 ///
    26 /// See
    27 /// \verbatim
    28 ///  dimacs-solver --help
    29 /// \endverbatim
    30 /// for more info on usage.
    31 ///
    32 
    33 #include <iostream>
    34 #include <fstream>
    35 #include <cstring>
    36 
    37 #include <lemon/smart_graph.h>
    38 #include <lemon/dimacs.h>
    39 #include <lemon/lgf_writer.h>
    40 #include <lemon/time_measure.h>
    41 
    42 #include <lemon/arg_parser.h>
    43 #include <lemon/error.h>
    44 
    45 #include <lemon/dijkstra.h>
    46 #include <lemon/preflow.h>
    47 #include <lemon/max_matching.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 void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
    96               DimacsDescriptor &desc)
    97 {
    98   bool report = !ap.given("q");
    99   Graph g;
   100   Timer ti;
   101   ti.restart();
   102   readDimacsMat(is, g, desc);
   103   if(report) std::cerr << "Read the file: " << ti << '\n';
   104   ti.restart();
   105   MaxMatching<Graph> mat(g);
   106   if(report) std::cerr << "Setup MaxMatching class: " << ti << '\n';
   107   ti.restart();
   108   mat.run();
   109   if(report) std::cerr << "Run MaxMatching: " << ti << '\n';
   110   if(report) std::cerr << "\nCardinality of max matching: "
   111                        << mat.matchingSize() << '\n';  
   112 }
   113 
   114 
   115 template<class Value>
   116 void solve(ArgParser &ap, std::istream &is, std::ostream &os,
   117            DimacsDescriptor &desc)
   118 {
   119   switch(desc.type)
   120     {
   121     case DimacsDescriptor::MIN:
   122       std::cerr <<
   123         "\n\n Sorry, the min. cost flow solver is not yet available.\n"
   124                 << std::endl;
   125       break;
   126     case DimacsDescriptor::MAX:
   127       solve_max<Value>(ap,is,os,desc);
   128       break;
   129     case DimacsDescriptor::SP:
   130       solve_sp<Value>(ap,is,os,desc);
   131       break;
   132     case DimacsDescriptor::MAT:
   133       solve_mat(ap,is,os,desc);
   134       break;
   135     default:
   136       break;
   137     }
   138 }
   139 
   140 int main(int argc, const char *argv[]) {
   141   typedef SmartDigraph Digraph;
   142 
   143   typedef Digraph::Arc Arc;
   144   typedef Digraph::Node Node;
   145   typedef Digraph::ArcIt ArcIt;
   146   typedef Digraph::NodeIt NodeIt;
   147   typedef Digraph::ArcMap<double> DoubleArcMap;
   148   typedef Digraph::NodeMap<double> DoubleNodeMap;
   149 
   150   std::string inputName;
   151   std::string outputName;
   152 
   153   ArgParser ap(argc, argv);
   154   ap.other("[INFILE [OUTFILE]]",
   155            "If either the INFILE or OUTFILE file is missing the standard\n"
   156            "     input/output will be used instead.")
   157     .boolOption("q", "Do not print any report")
   158     .boolOption("int","Use 'int' for capacities, costs etc. (default)")
   159     .optionGroup("datatype","int")
   160 #ifdef HAVE_LONG_LONG
   161     .boolOption("long","Use 'long long' for capacities, costs etc.")
   162     .optionGroup("datatype","long")
   163 #endif
   164     .boolOption("double","Use 'double' for capacities, costs etc.")
   165     .optionGroup("datatype","double")
   166     .boolOption("ldouble","Use 'long double' for capacities, costs etc.")
   167     .optionGroup("datatype","ldouble")
   168     .onlyOneGroup("datatype")
   169     .run();
   170 
   171   std::ifstream input;
   172   std::ofstream output;
   173 
   174   switch(ap.files().size())
   175     {
   176     case 2:
   177       output.open(ap.files()[1].c_str());
   178       if (!output) {
   179         throw IoError("Cannot open the file for writing", ap.files()[1]);
   180       }
   181     case 1:
   182       input.open(ap.files()[0].c_str());
   183       if (!input) {
   184         throw IoError("File cannot be found", ap.files()[0]);
   185       }
   186     case 0:
   187       break;
   188     default:
   189       std::cerr << ap.commandName() << ": too many arguments\n";
   190       return 1;
   191   }
   192   std::istream& is = (ap.files().size()<1 ? std::cin : input);
   193   std::ostream& os = (ap.files().size()<2 ? std::cout : output);
   194 
   195   DimacsDescriptor desc = dimacsType(is);
   196   
   197   if(!ap.given("q"))
   198     {
   199       std::cout << "Problem type: ";
   200       switch(desc.type)
   201         {
   202         case DimacsDescriptor::MIN:
   203           std::cout << "min";
   204           break;
   205         case DimacsDescriptor::MAX:
   206           std::cout << "max";
   207           break;
   208         case DimacsDescriptor::SP:
   209           std::cout << "sp";
   210         case DimacsDescriptor::MAT:
   211           std::cout << "mat";
   212           break;
   213         default:
   214           exit(1);
   215           break;
   216         }
   217       std::cout << "\nNum of nodes: " << desc.nodeNum;
   218       std::cout << "\nNum of arcs:  " << desc.edgeNum;
   219       std::cout << '\n' << std::endl;
   220     }
   221     
   222   if(ap.given("double"))
   223     solve<double>(ap,is,os,desc);
   224   else if(ap.given("ldouble"))
   225     solve<long double>(ap,is,os,desc);
   226 #ifdef HAVE_LONG_LONG
   227   else if(ap.given("long"))
   228     solve<long long>(ap,is,os,desc);
   229 #endif
   230   else solve<int>(ap,is,os,desc);
   231 
   232   return 0;
   233 }