COIN-OR::LEMON - Graph Library

source: lemon/tools/dimacs-solver.cc @ 1424:7edc220d6244

1.2
Last change on this file since 1424:7edc220d6244 was 1424:7edc220d6244, checked in by Alpar Juttner <alpar@…>, 5 months ago

Backport relevant parts of bugfixes [ad22262328b3], [61fdd06833a6] and [4add05447ca0] to branch 1.2 (#623)

File size: 7.8 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-2010
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" : "not found") << '\n';
131    if (res) std::cerr << "Min flow cost: "
132                       << ns.template totalCost<LargeValue>() << '\n';
133  }
134}
135
136void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
137              DimacsDescriptor &desc)
138{
139  bool report = !ap.given("q");
140  Graph g;
141  Timer ti;
142  ti.restart();
143  readDimacsMat(is, g, desc);
144  if(report) std::cerr << "Read the file: " << ti << '\n';
145  ti.restart();
146  MaxMatching<Graph> mat(g);
147  if(report) std::cerr << "Setup MaxMatching class: " << ti << '\n';
148  ti.restart();
149  mat.run();
150  if(report) std::cerr << "Run MaxMatching: " << ti << '\n';
151  if(report) std::cerr << "\nCardinality of max matching: "
152                       << mat.matchingSize() << '\n';
153}
154
155
156template<class Value, class LargeValue>
157void solve(ArgParser &ap, std::istream &is, std::ostream &os,
158           DimacsDescriptor &desc)
159{
160  std::stringstream iss(static_cast<std::string>(ap["infcap"]));
161  Value infty;
162  iss >> infty;
163  if(iss.fail())
164    {
165      std::cerr << "Cannot interpret '"
166                << static_cast<std::string>(ap["infcap"]) << "' as infinite"
167                << std::endl;
168      exit(1);
169    }
170
171  switch(desc.type)
172    {
173    case DimacsDescriptor::MIN:
174      solve_min<Value, LargeValue>(ap,is,os,infty,desc);
175      break;
176    case DimacsDescriptor::MAX:
177      solve_max<Value>(ap,is,os,infty,desc);
178      break;
179    case DimacsDescriptor::SP:
180      solve_sp<Value>(ap,is,os,desc);
181      break;
182    case DimacsDescriptor::MAT:
183      solve_mat(ap,is,os,desc);
184      break;
185    default:
186      break;
187    }
188}
189
190int main(int argc, const char *argv[]) {
191
192  std::string inputName;
193  std::string outputName;
194
195  ArgParser ap(argc, argv);
196  ap.other("[INFILE [OUTFILE]]",
197           "If either the INFILE or OUTFILE file is missing the standard\n"
198           "     input/output will be used instead.")
199    .boolOption("q", "Do not print any report")
200    .boolOption("int","Use 'int' for capacities, costs etc. (default)")
201    .optionGroup("datatype","int")
202#ifdef LEMON_HAVE_LONG_LONG
203    .boolOption("long","Use 'long long' for capacities, costs etc.")
204    .optionGroup("datatype","long")
205#endif
206    .boolOption("double","Use 'double' for capacities, costs etc.")
207    .optionGroup("datatype","double")
208    .boolOption("ldouble","Use 'long double' for capacities, costs etc.")
209    .optionGroup("datatype","ldouble")
210    .onlyOneGroup("datatype")
211    .stringOption("infcap","Value used for 'very high' capacities","0")
212    .run();
213
214  std::ifstream input;
215  std::ofstream output;
216
217  switch(ap.files().size())
218    {
219    case 2:
220      output.open(ap.files()[1].c_str());
221      if (!output) {
222        throw IoError("Cannot open the file for writing", ap.files()[1]);
223      }
224      // fall through
225    case 1:
226      input.open(ap.files()[0].c_str());
227      if (!input) {
228        throw IoError("File cannot be found", ap.files()[0]);
229      }
230      // fall through
231    case 0:
232      break;
233    default:
234      std::cerr << ap.commandName() << ": too many arguments\n";
235      return 1;
236    }
237  std::istream& is = (ap.files().size()<1 ? std::cin : input);
238  std::ostream& os = (ap.files().size()<2 ? std::cout : output);
239
240  DimacsDescriptor desc = dimacsType(is);
241
242  if(!ap.given("q"))
243    {
244      std::cout << "Problem type: ";
245      switch(desc.type)
246        {
247        case DimacsDescriptor::MIN:
248          std::cout << "min";
249          break;
250        case DimacsDescriptor::MAX:
251          std::cout << "max";
252          break;
253        case DimacsDescriptor::SP:
254          std::cout << "sp";
255          break;
256        case DimacsDescriptor::MAT:
257          std::cout << "mat";
258          break;
259        default:
260          exit(1);
261          break;
262        }
263      std::cout << "\nNum of nodes: " << desc.nodeNum;
264      std::cout << "\nNum of arcs:  " << desc.edgeNum;
265      std::cout << "\n\n";
266    }
267
268  if(ap.given("double"))
269    solve<double, double>(ap,is,os,desc);
270  else if(ap.given("ldouble"))
271    solve<long double, long double>(ap,is,os,desc);
272#ifdef LEMON_HAVE_LONG_LONG
273  else if(ap.given("long"))
274    solve<long long, long long>(ap,is,os,desc);
275  else solve<int, long long>(ap,is,os,desc);
276#else
277  else solve<int, long>(ap,is,os,desc);
278#endif
279
280  return 0;
281}
Note: See TracBrowser for help on using the repository browser.