tools/dimacs-solver.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 03 Apr 2009 18:59:15 +0200
changeset 608 6ac5d9ae1d3d
parent 602 a79ef774fae1
child 611 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.
alpar@385
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@385
     2
 *
alpar@385
     3
 * This file is a part of LEMON, a generic C++ optimization library.
alpar@385
     4
 *
alpar@440
     5
 * Copyright (C) 2003-2009
alpar@385
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@385
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@385
     8
 *
alpar@385
     9
 * Permission to use, modify and distribute this software is granted
alpar@385
    10
 * provided that this copyright notice appears in all copies. For
alpar@385
    11
 * precise terms see the accompanying LICENSE file.
alpar@385
    12
 *
alpar@385
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@385
    14
 * express or implied, and with no claim as to its suitability for any
alpar@385
    15
 * purpose.
alpar@385
    16
 *
alpar@385
    17
 */
alpar@385
    18
alpar@385
    19
///\ingroup tools
alpar@385
    20
///\file
kpeter@532
    21
///\brief DIMACS problem solver.
alpar@385
    22
///
kpeter@532
    23
/// This program solves various problems given in DIMACS format.
alpar@385
    24
///
alpar@385
    25
/// See
alpar@385
    26
/// \verbatim
alpar@526
    27
///  dimacs-solver --help
alpar@385
    28
/// \endverbatim
alpar@385
    29
/// for more info on usage.
alpar@385
    30
///
alpar@385
    31
alpar@385
    32
#include <iostream>
alpar@385
    33
#include <fstream>
alpar@385
    34
#include <cstring>
alpar@385
    35
alpar@385
    36
#include <lemon/smart_graph.h>
alpar@385
    37
#include <lemon/dimacs.h>
alpar@385
    38
#include <lemon/lgf_writer.h>
alpar@526
    39
#include <lemon/time_measure.h>
alpar@385
    40
alpar@385
    41
#include <lemon/arg_parser.h>
alpar@387
    42
#include <lemon/error.h>
alpar@385
    43
alpar@526
    44
#include <lemon/dijkstra.h>
alpar@526
    45
#include <lemon/preflow.h>
alpar@526
    46
#include <lemon/max_matching.h>
kpeter@602
    47
#include <lemon/network_simplex.h>
alpar@526
    48
alpar@385
    49
using namespace lemon;
alpar@526
    50
typedef SmartDigraph Digraph;
alpar@526
    51
DIGRAPH_TYPEDEFS(Digraph);
alpar@526
    52
typedef SmartGraph Graph;
alpar@385
    53
alpar@526
    54
template<class Value>
alpar@526
    55
void solve_sp(ArgParser &ap, std::istream &is, std::ostream &,
alpar@526
    56
              DimacsDescriptor &desc)
alpar@526
    57
{
alpar@526
    58
  bool report = !ap.given("q");
alpar@526
    59
  Digraph g;
alpar@526
    60
  Node s;
alpar@526
    61
  Digraph::ArcMap<Value> len(g);
alpar@526
    62
  Timer t;
alpar@526
    63
  t.restart();
alpar@526
    64
  readDimacsSp(is, g, len, s, desc);
alpar@526
    65
  if(report) std::cerr << "Read the file: " << t << '\n';
alpar@526
    66
  t.restart();
alpar@526
    67
  Dijkstra<Digraph, Digraph::ArcMap<Value> > dij(g,len);
alpar@526
    68
  if(report) std::cerr << "Setup Dijkstra class: " << t << '\n';
alpar@526
    69
  t.restart();
alpar@526
    70
  dij.run(s);
alpar@526
    71
  if(report) std::cerr << "Run Dijkstra: " << t << '\n';
alpar@526
    72
}
alpar@526
    73
alpar@526
    74
template<class Value>
alpar@526
    75
void solve_max(ArgParser &ap, std::istream &is, std::ostream &,
alpar@526
    76
              DimacsDescriptor &desc)
alpar@526
    77
{
alpar@526
    78
  bool report = !ap.given("q");
alpar@526
    79
  Digraph g;
alpar@526
    80
  Node s,t;
alpar@526
    81
  Digraph::ArcMap<Value> cap(g);
alpar@526
    82
  Timer ti;
alpar@526
    83
  ti.restart();
alpar@526
    84
  readDimacsMax(is, g, cap, s, t, desc);
alpar@526
    85
  if(report) std::cerr << "Read the file: " << ti << '\n';
alpar@526
    86
  ti.restart();
alpar@526
    87
  Preflow<Digraph, Digraph::ArcMap<Value> > pre(g,cap,s,t);
alpar@526
    88
  if(report) std::cerr << "Setup Preflow class: " << ti << '\n';
alpar@526
    89
  ti.restart();
alpar@526
    90
  pre.run();
alpar@526
    91
  if(report) std::cerr << "Run Preflow: " << ti << '\n';
alpar@526
    92
  if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n';  
alpar@526
    93
}
alpar@526
    94
kpeter@602
    95
template<class Value>
kpeter@602
    96
void solve_min(ArgParser &ap, std::istream &is, std::ostream &,
kpeter@602
    97
               DimacsDescriptor &desc)
kpeter@602
    98
{
kpeter@602
    99
  bool report = !ap.given("q");
kpeter@602
   100
  Digraph g;
kpeter@602
   101
  Digraph::ArcMap<Value> lower(g), cap(g), cost(g);
kpeter@602
   102
  Digraph::NodeMap<Value> sup(g);
kpeter@602
   103
  Timer ti;
kpeter@602
   104
  ti.restart();
kpeter@602
   105
  readDimacsMin(is, g, lower, cap, cost, sup, desc);
kpeter@602
   106
  if (report) std::cerr << "Read the file: " << ti << '\n';
kpeter@602
   107
  ti.restart();
kpeter@605
   108
  NetworkSimplex<Digraph, Value> ns(g);
kpeter@605
   109
  ns.lowerMap(lower).capacityMap(cap).costMap(cost).supplyMap(sup);
kpeter@602
   110
  if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n';
kpeter@602
   111
  ti.restart();
kpeter@602
   112
  ns.run();
kpeter@602
   113
  if (report) std::cerr << "Run NetworkSimplex: " << ti << '\n';
kpeter@602
   114
  if (report) std::cerr << "\nMin flow cost: " << ns.totalCost() << '\n';
kpeter@602
   115
}
kpeter@602
   116
alpar@526
   117
void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
alpar@526
   118
              DimacsDescriptor &desc)
alpar@526
   119
{
alpar@526
   120
  bool report = !ap.given("q");
alpar@526
   121
  Graph g;
alpar@526
   122
  Timer ti;
alpar@526
   123
  ti.restart();
alpar@526
   124
  readDimacsMat(is, g, desc);
alpar@526
   125
  if(report) std::cerr << "Read the file: " << ti << '\n';
alpar@526
   126
  ti.restart();
alpar@526
   127
  MaxMatching<Graph> mat(g);
alpar@526
   128
  if(report) std::cerr << "Setup MaxMatching class: " << ti << '\n';
alpar@526
   129
  ti.restart();
alpar@526
   130
  mat.run();
alpar@526
   131
  if(report) std::cerr << "Run MaxMatching: " << ti << '\n';
alpar@526
   132
  if(report) std::cerr << "\nCardinality of max matching: "
alpar@526
   133
                       << mat.matchingSize() << '\n';  
alpar@526
   134
}
alpar@526
   135
alpar@526
   136
alpar@526
   137
template<class Value>
alpar@526
   138
void solve(ArgParser &ap, std::istream &is, std::ostream &os,
alpar@526
   139
           DimacsDescriptor &desc)
alpar@526
   140
{
alpar@526
   141
  switch(desc.type)
alpar@526
   142
    {
alpar@526
   143
    case DimacsDescriptor::MIN:
kpeter@602
   144
      solve_min<Value>(ap,is,os,desc);
alpar@526
   145
      break;
alpar@526
   146
    case DimacsDescriptor::MAX:
alpar@526
   147
      solve_max<Value>(ap,is,os,desc);
alpar@526
   148
      break;
alpar@526
   149
    case DimacsDescriptor::SP:
alpar@526
   150
      solve_sp<Value>(ap,is,os,desc);
alpar@526
   151
      break;
alpar@526
   152
    case DimacsDescriptor::MAT:
alpar@526
   153
      solve_mat(ap,is,os,desc);
alpar@526
   154
      break;
alpar@526
   155
    default:
alpar@526
   156
      break;
alpar@526
   157
    }
alpar@526
   158
}
alpar@385
   159
alpar@385
   160
int main(int argc, const char *argv[]) {
alpar@385
   161
  typedef SmartDigraph Digraph;
alpar@385
   162
alpar@385
   163
  typedef Digraph::Arc Arc;
alpar@385
   164
alpar@385
   165
  std::string inputName;
alpar@385
   166
  std::string outputName;
alpar@385
   167
alpar@385
   168
  ArgParser ap(argc, argv);
alpar@387
   169
  ap.other("[INFILE [OUTFILE]]",
alpar@387
   170
           "If either the INFILE or OUTFILE file is missing the standard\n"
alpar@387
   171
           "     input/output will be used instead.")
alpar@526
   172
    .boolOption("q", "Do not print any report")
alpar@526
   173
    .boolOption("int","Use 'int' for capacities, costs etc. (default)")
alpar@526
   174
    .optionGroup("datatype","int")
alpar@526
   175
#ifdef HAVE_LONG_LONG
alpar@526
   176
    .boolOption("long","Use 'long long' for capacities, costs etc.")
alpar@526
   177
    .optionGroup("datatype","long")
alpar@526
   178
#endif
alpar@526
   179
    .boolOption("double","Use 'double' for capacities, costs etc.")
alpar@526
   180
    .optionGroup("datatype","double")
alpar@526
   181
    .boolOption("ldouble","Use 'long double' for capacities, costs etc.")
alpar@526
   182
    .optionGroup("datatype","ldouble")
alpar@526
   183
    .onlyOneGroup("datatype")
alpar@385
   184
    .run();
alpar@385
   185
alpar@526
   186
  std::ifstream input;
alpar@526
   187
  std::ofstream output;
alpar@387
   188
alpar@387
   189
  switch(ap.files().size())
alpar@387
   190
    {
alpar@387
   191
    case 2:
alpar@387
   192
      output.open(ap.files()[1].c_str());
alpar@387
   193
      if (!output) {
alpar@387
   194
        throw IoError("Cannot open the file for writing", ap.files()[1]);
alpar@387
   195
      }
alpar@387
   196
    case 1:
alpar@387
   197
      input.open(ap.files()[0].c_str());
alpar@387
   198
      if (!input) {
alpar@387
   199
        throw IoError("File cannot be found", ap.files()[0]);
alpar@387
   200
      }
alpar@387
   201
    case 0:
alpar@387
   202
      break;
alpar@387
   203
    default:
alpar@526
   204
      std::cerr << ap.commandName() << ": too many arguments\n";
alpar@387
   205
      return 1;
kpeter@532
   206
    }
alpar@526
   207
  std::istream& is = (ap.files().size()<1 ? std::cin : input);
alpar@526
   208
  std::ostream& os = (ap.files().size()<2 ? std::cout : output);
alpar@387
   209
alpar@387
   210
  DimacsDescriptor desc = dimacsType(is);
alpar@526
   211
  
alpar@526
   212
  if(!ap.given("q"))
alpar@387
   213
    {
alpar@526
   214
      std::cout << "Problem type: ";
alpar@526
   215
      switch(desc.type)
alpar@526
   216
        {
alpar@526
   217
        case DimacsDescriptor::MIN:
alpar@526
   218
          std::cout << "min";
alpar@526
   219
          break;
alpar@526
   220
        case DimacsDescriptor::MAX:
alpar@526
   221
          std::cout << "max";
alpar@526
   222
          break;
alpar@526
   223
        case DimacsDescriptor::SP:
alpar@526
   224
          std::cout << "sp";
alpar@526
   225
        case DimacsDescriptor::MAT:
alpar@526
   226
          std::cout << "mat";
alpar@526
   227
          break;
alpar@526
   228
        default:
alpar@526
   229
          exit(1);
alpar@526
   230
          break;
alpar@526
   231
        }
alpar@526
   232
      std::cout << "\nNum of nodes: " << desc.nodeNum;
alpar@526
   233
      std::cout << "\nNum of arcs:  " << desc.edgeNum;
kpeter@532
   234
      std::cout << "\n\n";
alpar@385
   235
    }
alpar@526
   236
    
alpar@526
   237
  if(ap.given("double"))
alpar@526
   238
    solve<double>(ap,is,os,desc);
alpar@526
   239
  else if(ap.given("ldouble"))
alpar@526
   240
    solve<long double>(ap,is,os,desc);
alpar@526
   241
#ifdef HAVE_LONG_LONG
alpar@526
   242
  else if(ap.given("long"))
alpar@526
   243
    solve<long long>(ap,is,os,desc);
alpar@526
   244
#endif
alpar@526
   245
  else solve<int>(ap,is,os,desc);
alpar@526
   246
alpar@385
   247
  return 0;
alpar@385
   248
}