COIN-OR::LEMON - Graph Library

source: lemon-main/tools/dimacs-solver.cc @ 846:9d380bf27194

Last change on this file since 846:9d380bf27194 was 846:9d380bf27194, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Use 'long long' flow cost in dimacs-solver.cc (#347)

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