COIN-OR::LEMON - Graph Library

source: lemon-1.2/tools/dimacs-solver.cc @ 570:ab6da8cf5ab2

Last change on this file since 570:ab6da8cf5ab2 was 561:6e0525ec5355, checked in by Alpar Juttner <alpar@…>, 10 years ago

Accept negative values as unbounded capacity in dimacs readers (#243)
and some doc improvements.

File size: 6.3 KB
Line 
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
48using namespace lemon;
49typedef SmartDigraph Digraph;
50DIGRAPH_TYPEDEFS(Digraph);
51typedef SmartGraph Graph;
52
53template<class Value>
54void 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
73template<class Value>
74void solve_max(ArgParser &ap, std::istream &is, std::ostream &,
75               Value infty, 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, infty, 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
94void 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
114template<class Value>
115void solve(ArgParser &ap, std::istream &is, std::ostream &os,
116           DimacsDescriptor &desc)
117{
118  std::stringstream iss(ap["infcap"]);
119  Value infty;
120  iss >> infty;
121  if(iss.fail())
122    {
123      std::cerr << "Cannot interpret '"
124                << static_cast<std::string>(ap["infcap"]) << "' as infinite"
125                << std::endl;
126      exit(1);
127    }
128 
129  switch(desc.type)
130    {
131    case DimacsDescriptor::MIN:
132      std::cerr <<
133        "\n\n Sorry, the min. cost flow solver is not yet available.\n";
134      break;
135    case DimacsDescriptor::MAX:
136      solve_max<Value>(ap,is,os,infty,desc);
137      break;
138    case DimacsDescriptor::SP:
139      solve_sp<Value>(ap,is,os,desc);
140      break;
141    case DimacsDescriptor::MAT:
142      solve_mat(ap,is,os,desc);
143      break;
144    default:
145      break;
146    }
147}
148
149int main(int argc, const char *argv[]) {
150  typedef SmartDigraph Digraph;
151
152  typedef Digraph::Arc Arc;
153
154  std::string inputName;
155  std::string outputName;
156
157  ArgParser ap(argc, argv);
158  ap.other("[INFILE [OUTFILE]]",
159           "If either the INFILE or OUTFILE file is missing the standard\n"
160           "     input/output will be used instead.")
161    .boolOption("q", "Do not print any report")
162    .boolOption("int","Use 'int' for capacities, costs etc. (default)")
163    .optionGroup("datatype","int")
164#ifdef HAVE_LONG_LONG
165    .boolOption("long","Use 'long long' for capacities, costs etc.")
166    .optionGroup("datatype","long")
167#endif
168    .boolOption("double","Use 'double' for capacities, costs etc.")
169    .optionGroup("datatype","double")
170    .boolOption("ldouble","Use 'long double' for capacities, costs etc.")
171    .optionGroup("datatype","ldouble")
172    .onlyOneGroup("datatype")
173    .stringOption("infcap","Value used for 'very high' capacities","0")
174    .run();
175
176  std::ifstream input;
177  std::ofstream output;
178
179  switch(ap.files().size())
180    {
181    case 2:
182      output.open(ap.files()[1].c_str());
183      if (!output) {
184        throw IoError("Cannot open the file for writing", ap.files()[1]);
185      }
186    case 1:
187      input.open(ap.files()[0].c_str());
188      if (!input) {
189        throw IoError("File cannot be found", ap.files()[0]);
190      }
191    case 0:
192      break;
193    default:
194      std::cerr << ap.commandName() << ": too many arguments\n";
195      return 1;
196    }
197  std::istream& is = (ap.files().size()<1 ? std::cin : input);
198  std::ostream& os = (ap.files().size()<2 ? std::cout : output);
199
200  DimacsDescriptor desc = dimacsType(is);
201 
202  if(!ap.given("q"))
203    {
204      std::cout << "Problem type: ";
205      switch(desc.type)
206        {
207        case DimacsDescriptor::MIN:
208          std::cout << "min";
209          break;
210        case DimacsDescriptor::MAX:
211          std::cout << "max";
212          break;
213        case DimacsDescriptor::SP:
214          std::cout << "sp";
215        case DimacsDescriptor::MAT:
216          std::cout << "mat";
217          break;
218        default:
219          exit(1);
220          break;
221        }
222      std::cout << "\nNum of nodes: " << desc.nodeNum;
223      std::cout << "\nNum of arcs:  " << desc.edgeNum;
224      std::cout << "\n\n";
225    }
226   
227  if(ap.given("double"))
228    solve<double>(ap,is,os,desc);
229  else if(ap.given("ldouble"))
230    solve<long double>(ap,is,os,desc);
231#ifdef HAVE_LONG_LONG
232  else if(ap.given("long"))
233    solve<long long>(ap,is,os,desc);
234#endif
235  else solve<int>(ap,is,os,desc);
236
237  return 0;
238}
Note: See TracBrowser for help on using the repository browser.