COIN-OR::LEMON - Graph Library

source: lemon/tools/dimacs-solver.cc @ 1386:ad22262328b3

Last change on this file since 1386:ad22262328b3 was 1386:ad22262328b3, checked in by Peter Kovacs <kpeter@…>, 18 months ago

Add missing break statement to dimacs-solver (#609)

File size: 7.9 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-2013
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/// \code
27///   dimacs-solver --help
28/// \endcode
29/// for more info on usage.
30
31#include <iostream>
32#include <fstream>
33#include <cstring>
34
35#include <lemon/smart_graph.h>
36#include <lemon/dimacs.h>
37#include <lemon/lgf_writer.h>
38#include <lemon/time_measure.h>
39
40#include <lemon/arg_parser.h>
41#include <lemon/error.h>
42
43#include <lemon/dijkstra.h>
44#include <lemon/preflow.h>
45#include <lemon/matching.h>
46#include <lemon/network_simplex.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
94template<class Value, class LargeValue>
95void solve_min(ArgParser &ap, std::istream &is, std::ostream &,
96               Value infty, DimacsDescriptor &desc)
97{
98  bool report = !ap.given("q");
99  Digraph g;
100  Digraph::ArcMap<Value> lower(g), cap(g), cost(g);
101  Digraph::NodeMap<Value> sup(g);
102  Timer ti;
103
104  ti.restart();
105  readDimacsMin(is, g, lower, cap, cost, sup, infty, desc);
106  ti.stop();
107  Value sum_sup = 0;
108  for (Digraph::NodeIt n(g); n != INVALID; ++n) {
109    sum_sup += sup[n];
110  }
111  if (report) {
112    std::cerr << "Sum of supply values: " << sum_sup << "\n";
113    if (sum_sup <= 0)
114      std::cerr << "GEQ supply contraints are used for NetworkSimplex\n\n";
115    else
116      std::cerr << "LEQ supply contraints are used for NetworkSimplex\n\n";
117  }
118  if (report) std::cerr << "Read the file: " << ti << '\n';
119
120  typedef NetworkSimplex<Digraph, Value> MCF;
121  ti.restart();
122  MCF ns(g);
123  ns.lowerMap(lower).upperMap(cap).costMap(cost).supplyMap(sup);
124  if (sum_sup > 0) ns.supplyType(ns.LEQ);
125  if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n';
126  ti.restart();
127  typename MCF::ProblemType res = ns.run();
128  if (report) {
129    std::cerr << "Run NetworkSimplex: " << ti << "\n\n";
130    std::cerr << "Feasible flow: " << (res == MCF::OPTIMAL ? "found" :
131                                       "not found") << '\n';
132    if (res) std::cerr << "Min flow cost: "
133                       << ns.template totalCost<LargeValue>() << '\n';
134  }
135}
136
137void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
138              DimacsDescriptor &desc)
139{
140  bool report = !ap.given("q");
141  Graph g;
142  Timer ti;
143  ti.restart();
144  readDimacsMat(is, g, desc);
145  if(report) std::cerr << "Read the file: " << ti << '\n';
146  ti.restart();
147  MaxMatching<Graph> mat(g);
148  if(report) std::cerr << "Setup MaxMatching class: " << ti << '\n';
149  ti.restart();
150  mat.run();
151  if(report) std::cerr << "Run MaxMatching: " << ti << '\n';
152  if(report) std::cerr << "\nCardinality of max matching: "
153                       << mat.matchingSize() << '\n';
154}
155
156
157template<class Value, class LargeValue>
158void solve(ArgParser &ap, std::istream &is, std::ostream &os,
159           DimacsDescriptor &desc)
160{
161  std::stringstream iss(static_cast<std::string>(ap["infcap"]));
162  Value infty;
163  iss >> infty;
164  if(iss.fail())
165    {
166      std::cerr << "Cannot interpret '"
167                << static_cast<std::string>(ap["infcap"]) << "' as infinite"
168                << std::endl;
169      exit(1);
170    }
171
172  switch(desc.type)
173    {
174    case DimacsDescriptor::MIN:
175      solve_min<Value, LargeValue>(ap,is,os,infty,desc);
176      break;
177    case DimacsDescriptor::MAX:
178      solve_max<Value>(ap,is,os,infty,desc);
179      break;
180    case DimacsDescriptor::SP:
181      solve_sp<Value>(ap,is,os,desc);
182      break;
183    case DimacsDescriptor::MAT:
184      solve_mat(ap,is,os,desc);
185      break;
186    default:
187      break;
188    }
189}
190
191int main(int argc, const char *argv[]) {
192
193  std::string inputName;
194  std::string outputName;
195
196  ArgParser ap(argc, argv);
197  ap.other("[INFILE [OUTFILE]]",
198           "If either the INFILE or OUTFILE file is missing the standard\n"
199           "     input/output will be used instead.")
200    .boolOption("q", "Do not print any report")
201    .boolOption("int","Use 'int' for capacities, costs etc. (default)")
202    .optionGroup("datatype","int")
203#ifdef LEMON_HAVE_LONG_LONG
204    .boolOption("long","Use 'long long' for capacities, costs etc.")
205    .optionGroup("datatype","long")
206#endif
207    .boolOption("double","Use 'double' for capacities, costs etc.")
208    .optionGroup("datatype","double")
209    .boolOption("ldouble","Use 'long double' for capacities, costs etc.")
210    .optionGroup("datatype","ldouble")
211    .onlyOneGroup("datatype")
212    .stringOption("infcap","Value used for 'very high' capacities","0")
213    .run();
214
215  std::ifstream input;
216  std::ofstream output;
217
218  switch(ap.files().size())
219    {
220    case 2:
221      output.open(ap.files()[1].c_str());
222      if (!output) {
223        throw IoError("Cannot open the file for writing", ap.files()[1]);
224      }
225      // fall through
226    case 1:
227      input.open(ap.files()[0].c_str());
228      if (!input) {
229        throw IoError("File cannot be found", ap.files()[0]);
230      }
231      // fall through
232    case 0:
233      break;
234    default:
235      std::cerr << ap.commandName() << ": too many arguments\n";
236      return 1;
237    }
238  std::istream& is = (ap.files().size()<1 ? std::cin : input);
239  std::ostream& os = (ap.files().size()<2 ? std::cout : output);
240
241  DimacsDescriptor desc = dimacsType(is);
242
243  if(!ap.given("q"))
244    {
245      std::cout << "Problem type: ";
246      switch(desc.type)
247        {
248        case DimacsDescriptor::MIN:
249          std::cout << "min";
250          break;
251        case DimacsDescriptor::MAX:
252          std::cout << "max";
253          break;
254        case DimacsDescriptor::SP:
255          std::cout << "sp";
256          break;
257        case DimacsDescriptor::MAT:
258          std::cout << "mat";
259          break;
260        default:
261          exit(1);
262          break;
263        }
264      std::cout << "\nNum of nodes: " << desc.nodeNum;
265      std::cout << "\nNum of arcs:  " << desc.edgeNum;
266      std::cout << "\n\n";
267    }
268
269  if(ap.given("double"))
270    solve<double, double>(ap,is,os,desc);
271  else if(ap.given("ldouble"))
272    solve<long double, long double>(ap,is,os,desc);
273#ifdef LEMON_HAVE_LONG_LONG
274  else if(ap.given("long"))
275    solve<long long, long long>(ap,is,os,desc);
276  else solve<int, long long>(ap,is,os,desc);
277#else
278  else solve<int, long>(ap,is,os,desc);
279#endif
280
281  return 0;
282}
Note: See TracBrowser for help on using the repository browser.