COIN-OR::LEMON - Graph Library

source: lemon-main/tools/dimacs-solver.cc @ 611:85cb3aa71cce

Last change on this file since 611:85cb3aa71cce was 611:85cb3aa71cce, checked in by Alpar Juttner <alpar@…>, 15 years ago

Merge and fix

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