COIN-OR::LEMON - Graph Library

source: lemon/tools/dimacs-solver.cc @ 641:d657c71db7db

Last change on this file since 641:d657c71db7db was 641:d657c71db7db, checked in by Peter Kovacs <kpeter@…>, 16 years ago

Rename max_matching.h to matching.h (#265)

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/// \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
47using namespace lemon;
48typedef SmartDigraph Digraph;
49DIGRAPH_TYPEDEFS(Digraph);
50typedef SmartGraph Graph;
51
52template<class Value>
53void solve_sp(ArgParser &ap, std::istream &is, std::ostream &,
54              DimacsDescriptor &desc)
55{
56  bool report = !ap.given("q");
57  Digraph g;
58  Node s;
59  Digraph::ArcMap<Value> len(g);
60  Timer t;
61  t.restart();
62  readDimacsSp(is, g, len, s, desc);
63  if(report) std::cerr << "Read the file: " << t << '\n';
64  t.restart();
65  Dijkstra<Digraph, Digraph::ArcMap<Value> > dij(g,len);
66  if(report) std::cerr << "Setup Dijkstra class: " << t << '\n';
67  t.restart();
68  dij.run(s);
69  if(report) std::cerr << "Run Dijkstra: " << t << '\n';
70}
71
72template<class Value>
73void solve_max(ArgParser &ap, std::istream &is, std::ostream &,
74               Value infty, DimacsDescriptor &desc)
75{
76  bool report = !ap.given("q");
77  Digraph g;
78  Node s,t;
79  Digraph::ArcMap<Value> cap(g);
80  Timer ti;
81  ti.restart();
82  readDimacsMax(is, g, cap, s, t, infty, desc);
83  if(report) std::cerr << "Read the file: " << ti << '\n';
84  ti.restart();
85  Preflow<Digraph, Digraph::ArcMap<Value> > pre(g,cap,s,t);
86  if(report) std::cerr << "Setup Preflow class: " << ti << '\n';
87  ti.restart();
88  pre.run();
89  if(report) std::cerr << "Run Preflow: " << ti << '\n';
90  if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n'; 
91}
92
93void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
94              DimacsDescriptor &desc)
95{
96  bool report = !ap.given("q");
97  Graph g;
98  Timer ti;
99  ti.restart();
100  readDimacsMat(is, g, desc);
101  if(report) std::cerr << "Read the file: " << ti << '\n';
102  ti.restart();
103  MaxMatching<Graph> mat(g);
104  if(report) std::cerr << "Setup MaxMatching class: " << ti << '\n';
105  ti.restart();
106  mat.run();
107  if(report) std::cerr << "Run MaxMatching: " << ti << '\n';
108  if(report) std::cerr << "\nCardinality of max matching: "
109                       << mat.matchingSize() << '\n'; 
110}
111
112
113template<class Value>
114void solve(ArgParser &ap, std::istream &is, std::ostream &os,
115           DimacsDescriptor &desc)
116{
117  std::stringstream iss(static_cast<std::string>(ap["infcap"]));
118  Value infty;
119  iss >> infty;
120  if(iss.fail())
121    {
122      std::cerr << "Cannot interpret '"
123                << static_cast<std::string>(ap["infcap"]) << "' as infinite"
124                << std::endl;
125      exit(1);
126    }
127 
128  switch(desc.type)
129    {
130    case DimacsDescriptor::MIN:
131      std::cerr <<
132        "\n\n Sorry, the min. cost flow solver is not yet available.\n";
133      break;
134    case DimacsDescriptor::MAX:
135      solve_max<Value>(ap,is,os,infty,desc);
136      break;
137    case DimacsDescriptor::SP:
138      solve_sp<Value>(ap,is,os,desc);
139      break;
140    case DimacsDescriptor::MAT:
141      solve_mat(ap,is,os,desc);
142      break;
143    default:
144      break;
145    }
146}
147
148int main(int argc, const char *argv[]) {
149  typedef SmartDigraph Digraph;
150
151  typedef Digraph::Arc Arc;
152
153  std::string inputName;
154  std::string outputName;
155
156  ArgParser ap(argc, argv);
157  ap.other("[INFILE [OUTFILE]]",
158           "If either the INFILE or OUTFILE file is missing the standard\n"
159           "     input/output will be used instead.")
160    .boolOption("q", "Do not print any report")
161    .boolOption("int","Use 'int' for capacities, costs etc. (default)")
162    .optionGroup("datatype","int")
163#ifdef HAVE_LONG_LONG
164    .boolOption("long","Use 'long long' for capacities, costs etc.")
165    .optionGroup("datatype","long")
166#endif
167    .boolOption("double","Use 'double' for capacities, costs etc.")
168    .optionGroup("datatype","double")
169    .boolOption("ldouble","Use 'long double' for capacities, costs etc.")
170    .optionGroup("datatype","ldouble")
171    .onlyOneGroup("datatype")
172    .stringOption("infcap","Value used for 'very high' capacities","0")
173    .run();
174
175  std::ifstream input;
176  std::ofstream output;
177
178  switch(ap.files().size())
179    {
180    case 2:
181      output.open(ap.files()[1].c_str());
182      if (!output) {
183        throw IoError("Cannot open the file for writing", ap.files()[1]);
184      }
185    case 1:
186      input.open(ap.files()[0].c_str());
187      if (!input) {
188        throw IoError("File cannot be found", ap.files()[0]);
189      }
190    case 0:
191      break;
192    default:
193      std::cerr << ap.commandName() << ": too many arguments\n";
194      return 1;
195    }
196  std::istream& is = (ap.files().size()<1 ? std::cin : input);
197  std::ostream& os = (ap.files().size()<2 ? std::cout : output);
198
199  DimacsDescriptor desc = dimacsType(is);
200 
201  if(!ap.given("q"))
202    {
203      std::cout << "Problem type: ";
204      switch(desc.type)
205        {
206        case DimacsDescriptor::MIN:
207          std::cout << "min";
208          break;
209        case DimacsDescriptor::MAX:
210          std::cout << "max";
211          break;
212        case DimacsDescriptor::SP:
213          std::cout << "sp";
214        case DimacsDescriptor::MAT:
215          std::cout << "mat";
216          break;
217        default:
218          exit(1);
219          break;
220        }
221      std::cout << "\nNum of nodes: " << desc.nodeNum;
222      std::cout << "\nNum of arcs:  " << desc.edgeNum;
223      std::cout << "\n\n";
224    }
225   
226  if(ap.given("double"))
227    solve<double>(ap,is,os,desc);
228  else if(ap.given("ldouble"))
229    solve<long double>(ap,is,os,desc);
230#ifdef HAVE_LONG_LONG
231  else if(ap.given("long"))
232    solve<long long>(ap,is,os,desc);
233#endif
234  else solve<int>(ap,is,os,desc);
235
236  return 0;
237}
Note: See TracBrowser for help on using the repository browser.