DIMACS solver utility (#226)
authorAlpar Juttner <alpar@cs.elte.hu>
Mon, 23 Feb 2009 11:49:57 +0000
changeset 51028b154307c0d
parent 509 635a8375227d
child 511 c458e02723b1
DIMACS solver utility (#226)
tools/Makefile.am
tools/dimacs-solver.cc
     1.1 --- a/tools/Makefile.am	Mon Feb 23 11:48:47 2009 +0000
     1.2 +++ b/tools/Makefile.am	Mon Feb 23 11:49:57 2009 +0000
     1.3 @@ -1,6 +1,7 @@
     1.4  if WANT_TOOLS
     1.5  
     1.6  bin_PROGRAMS += \
     1.7 +	tools/dimacs-solver \
     1.8  	tools/dimacs-to-lgf \
     1.9  	tools/lgf-gen
    1.10  
    1.11 @@ -8,5 +9,6 @@
    1.12  
    1.13  endif WANT_TOOLS
    1.14  
    1.15 +tools_dimacs_solver_SOURCES = tools/dimacs-solver.cc
    1.16  tools_dimacs_to_lgf_SOURCES = tools/dimacs-to-lgf.cc
    1.17  tools_lgf_gen_SOURCES = tools/lgf-gen.cc
     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/tools/dimacs-solver.cc	Mon Feb 23 11:49:57 2009 +0000
     2.3 @@ -0,0 +1,233 @@
     2.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     2.5 + *
     2.6 + * This file is a part of LEMON, a generic C++ optimization library.
     2.7 + *
     2.8 + * Copyright (C) 2003-2009
     2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    2.11 + *
    2.12 + * Permission to use, modify and distribute this software is granted
    2.13 + * provided that this copyright notice appears in all copies. For
    2.14 + * precise terms see the accompanying LICENSE file.
    2.15 + *
    2.16 + * This software is provided "AS IS" with no warranty of any kind,
    2.17 + * express or implied, and with no claim as to its suitability for any
    2.18 + * purpose.
    2.19 + *
    2.20 + */
    2.21 +
    2.22 +///\ingroup tools
    2.23 +///\file
    2.24 +///\brief DIMACS to LGF converter.
    2.25 +///
    2.26 +/// This program converts various DIMACS formats to the LEMON Digraph Format
    2.27 +/// (LGF).
    2.28 +///
    2.29 +/// See
    2.30 +/// \verbatim
    2.31 +///  dimacs-solver --help
    2.32 +/// \endverbatim
    2.33 +/// for more info on usage.
    2.34 +///
    2.35 +
    2.36 +#include <iostream>
    2.37 +#include <fstream>
    2.38 +#include <cstring>
    2.39 +
    2.40 +#include <lemon/smart_graph.h>
    2.41 +#include <lemon/dimacs.h>
    2.42 +#include <lemon/lgf_writer.h>
    2.43 +#include <lemon/time_measure.h>
    2.44 +
    2.45 +#include <lemon/arg_parser.h>
    2.46 +#include <lemon/error.h>
    2.47 +
    2.48 +#include <lemon/dijkstra.h>
    2.49 +#include <lemon/preflow.h>
    2.50 +#include <lemon/max_matching.h>
    2.51 +
    2.52 +using namespace lemon;
    2.53 +typedef SmartDigraph Digraph;
    2.54 +DIGRAPH_TYPEDEFS(Digraph);
    2.55 +typedef SmartGraph Graph;
    2.56 +
    2.57 +template<class Value>
    2.58 +void solve_sp(ArgParser &ap, std::istream &is, std::ostream &,
    2.59 +              DimacsDescriptor &desc)
    2.60 +{
    2.61 +  bool report = !ap.given("q");
    2.62 +  Digraph g;
    2.63 +  Node s;
    2.64 +  Digraph::ArcMap<Value> len(g);
    2.65 +  Timer t;
    2.66 +  t.restart();
    2.67 +  readDimacsSp(is, g, len, s, desc);
    2.68 +  if(report) std::cerr << "Read the file: " << t << '\n';
    2.69 +  t.restart();
    2.70 +  Dijkstra<Digraph, Digraph::ArcMap<Value> > dij(g,len);
    2.71 +  if(report) std::cerr << "Setup Dijkstra class: " << t << '\n';
    2.72 +  t.restart();
    2.73 +  dij.run(s);
    2.74 +  if(report) std::cerr << "Run Dijkstra: " << t << '\n';
    2.75 +}
    2.76 +
    2.77 +template<class Value>
    2.78 +void solve_max(ArgParser &ap, std::istream &is, std::ostream &,
    2.79 +              DimacsDescriptor &desc)
    2.80 +{
    2.81 +  bool report = !ap.given("q");
    2.82 +  Digraph g;
    2.83 +  Node s,t;
    2.84 +  Digraph::ArcMap<Value> cap(g);
    2.85 +  Timer ti;
    2.86 +  ti.restart();
    2.87 +  readDimacsMax(is, g, cap, s, t, desc);
    2.88 +  if(report) std::cerr << "Read the file: " << ti << '\n';
    2.89 +  ti.restart();
    2.90 +  Preflow<Digraph, Digraph::ArcMap<Value> > pre(g,cap,s,t);
    2.91 +  if(report) std::cerr << "Setup Preflow class: " << ti << '\n';
    2.92 +  ti.restart();
    2.93 +  pre.run();
    2.94 +  if(report) std::cerr << "Run Preflow: " << ti << '\n';
    2.95 +  if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n';  
    2.96 +}
    2.97 +
    2.98 +void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
    2.99 +              DimacsDescriptor &desc)
   2.100 +{
   2.101 +  bool report = !ap.given("q");
   2.102 +  Graph g;
   2.103 +  Timer ti;
   2.104 +  ti.restart();
   2.105 +  readDimacsMat(is, g, desc);
   2.106 +  if(report) std::cerr << "Read the file: " << ti << '\n';
   2.107 +  ti.restart();
   2.108 +  MaxMatching<Graph> mat(g);
   2.109 +  if(report) std::cerr << "Setup MaxMatching class: " << ti << '\n';
   2.110 +  ti.restart();
   2.111 +  mat.run();
   2.112 +  if(report) std::cerr << "Run MaxMatching: " << ti << '\n';
   2.113 +  if(report) std::cerr << "\nCardinality of max matching: "
   2.114 +                       << mat.matchingSize() << '\n';  
   2.115 +}
   2.116 +
   2.117 +
   2.118 +template<class Value>
   2.119 +void solve(ArgParser &ap, std::istream &is, std::ostream &os,
   2.120 +           DimacsDescriptor &desc)
   2.121 +{
   2.122 +  switch(desc.type)
   2.123 +    {
   2.124 +    case DimacsDescriptor::MIN:
   2.125 +      std::cerr <<
   2.126 +        "\n\n Sorry, the min. cost flow solver is not yet available.\n"
   2.127 +                << std::endl;
   2.128 +      break;
   2.129 +    case DimacsDescriptor::MAX:
   2.130 +      solve_max<Value>(ap,is,os,desc);
   2.131 +      break;
   2.132 +    case DimacsDescriptor::SP:
   2.133 +      solve_sp<Value>(ap,is,os,desc);
   2.134 +      break;
   2.135 +    case DimacsDescriptor::MAT:
   2.136 +      solve_mat(ap,is,os,desc);
   2.137 +      break;
   2.138 +    default:
   2.139 +      break;
   2.140 +    }
   2.141 +}
   2.142 +
   2.143 +int main(int argc, const char *argv[]) {
   2.144 +  typedef SmartDigraph Digraph;
   2.145 +
   2.146 +  typedef Digraph::Arc Arc;
   2.147 +  typedef Digraph::Node Node;
   2.148 +  typedef Digraph::ArcIt ArcIt;
   2.149 +  typedef Digraph::NodeIt NodeIt;
   2.150 +  typedef Digraph::ArcMap<double> DoubleArcMap;
   2.151 +  typedef Digraph::NodeMap<double> DoubleNodeMap;
   2.152 +
   2.153 +  std::string inputName;
   2.154 +  std::string outputName;
   2.155 +
   2.156 +  ArgParser ap(argc, argv);
   2.157 +  ap.other("[INFILE [OUTFILE]]",
   2.158 +           "If either the INFILE or OUTFILE file is missing the standard\n"
   2.159 +           "     input/output will be used instead.")
   2.160 +    .boolOption("q", "Do not print any report")
   2.161 +    .boolOption("int","Use 'int' for capacities, costs etc. (default)")
   2.162 +    .optionGroup("datatype","int")
   2.163 +#ifdef HAVE_LONG_LONG
   2.164 +    .boolOption("long","Use 'long long' for capacities, costs etc.")
   2.165 +    .optionGroup("datatype","long")
   2.166 +#endif
   2.167 +    .boolOption("double","Use 'double' for capacities, costs etc.")
   2.168 +    .optionGroup("datatype","double")
   2.169 +    .boolOption("ldouble","Use 'long double' for capacities, costs etc.")
   2.170 +    .optionGroup("datatype","ldouble")
   2.171 +    .onlyOneGroup("datatype")
   2.172 +    .run();
   2.173 +
   2.174 +  std::ifstream input;
   2.175 +  std::ofstream output;
   2.176 +
   2.177 +  switch(ap.files().size())
   2.178 +    {
   2.179 +    case 2:
   2.180 +      output.open(ap.files()[1].c_str());
   2.181 +      if (!output) {
   2.182 +        throw IoError("Cannot open the file for writing", ap.files()[1]);
   2.183 +      }
   2.184 +    case 1:
   2.185 +      input.open(ap.files()[0].c_str());
   2.186 +      if (!input) {
   2.187 +        throw IoError("File cannot be found", ap.files()[0]);
   2.188 +      }
   2.189 +    case 0:
   2.190 +      break;
   2.191 +    default:
   2.192 +      std::cerr << ap.commandName() << ": too many arguments\n";
   2.193 +      return 1;
   2.194 +  }
   2.195 +  std::istream& is = (ap.files().size()<1 ? std::cin : input);
   2.196 +  std::ostream& os = (ap.files().size()<2 ? std::cout : output);
   2.197 +
   2.198 +  DimacsDescriptor desc = dimacsType(is);
   2.199 +  
   2.200 +  if(!ap.given("q"))
   2.201 +    {
   2.202 +      std::cout << "Problem type: ";
   2.203 +      switch(desc.type)
   2.204 +        {
   2.205 +        case DimacsDescriptor::MIN:
   2.206 +          std::cout << "min";
   2.207 +          break;
   2.208 +        case DimacsDescriptor::MAX:
   2.209 +          std::cout << "max";
   2.210 +          break;
   2.211 +        case DimacsDescriptor::SP:
   2.212 +          std::cout << "sp";
   2.213 +        case DimacsDescriptor::MAT:
   2.214 +          std::cout << "mat";
   2.215 +          break;
   2.216 +        default:
   2.217 +          exit(1);
   2.218 +          break;
   2.219 +        }
   2.220 +      std::cout << "\nNum of nodes: " << desc.nodeNum;
   2.221 +      std::cout << "\nNum of arcs:  " << desc.edgeNum;
   2.222 +      std::cout << '\n' << std::endl;
   2.223 +    }
   2.224 +    
   2.225 +  if(ap.given("double"))
   2.226 +    solve<double>(ap,is,os,desc);
   2.227 +  else if(ap.given("ldouble"))
   2.228 +    solve<long double>(ap,is,os,desc);
   2.229 +#ifdef HAVE_LONG_LONG
   2.230 +  else if(ap.given("long"))
   2.231 +    solve<long long>(ap,is,os,desc);
   2.232 +#endif
   2.233 +  else solve<int>(ap,is,os,desc);
   2.234 +
   2.235 +  return 0;
   2.236 +}