COIN-OR::LEMON - Graph Library

source: lemon/tools/dimacs-solver.cc @ 652:5232721b3f14

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

Rework the interface of NetworkSimplex? (#234)

The parameters of the problem can be set with separate functions
instead of different constructors.

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