COIN-OR::LEMON - Graph Library

source: lemon/tools/dimacs-solver.cc @ 573:28b154307c0d

Last change on this file since 573:28b154307c0d was 573:28b154307c0d, checked in by Alpar Juttner <alpar@…>, 10 years ago

DIMACS solver utility (#226)

File size: 6.2 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 to LGF converter.
22///
23/// This program converts various DIMACS formats to the LEMON Digraph Format
24/// (LGF).
25///
26/// See
27/// \verbatim
28///  dimacs-solver --help
29/// \endverbatim
30/// for more info on usage.
31///
32
33#include <iostream>
34#include <fstream>
35#include <cstring>
36
37#include <lemon/smart_graph.h>
38#include <lemon/dimacs.h>
39#include <lemon/lgf_writer.h>
40#include <lemon/time_measure.h>
41
42#include <lemon/arg_parser.h>
43#include <lemon/error.h>
44
45#include <lemon/dijkstra.h>
46#include <lemon/preflow.h>
47#include <lemon/max_matching.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
95void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
96              DimacsDescriptor &desc)
97{
98  bool report = !ap.given("q");
99  Graph g;
100  Timer ti;
101  ti.restart();
102  readDimacsMat(is, g, desc);
103  if(report) std::cerr << "Read the file: " << ti << '\n';
104  ti.restart();
105  MaxMatching<Graph> mat(g);
106  if(report) std::cerr << "Setup MaxMatching class: " << ti << '\n';
107  ti.restart();
108  mat.run();
109  if(report) std::cerr << "Run MaxMatching: " << ti << '\n';
110  if(report) std::cerr << "\nCardinality of max matching: "
111                       << mat.matchingSize() << '\n'; 
112}
113
114
115template<class Value>
116void solve(ArgParser &ap, std::istream &is, std::ostream &os,
117           DimacsDescriptor &desc)
118{
119  switch(desc.type)
120    {
121    case DimacsDescriptor::MIN:
122      std::cerr <<
123        "\n\n Sorry, the min. cost flow solver is not yet available.\n"
124                << std::endl;
125      break;
126    case DimacsDescriptor::MAX:
127      solve_max<Value>(ap,is,os,desc);
128      break;
129    case DimacsDescriptor::SP:
130      solve_sp<Value>(ap,is,os,desc);
131      break;
132    case DimacsDescriptor::MAT:
133      solve_mat(ap,is,os,desc);
134      break;
135    default:
136      break;
137    }
138}
139
140int main(int argc, const char *argv[]) {
141  typedef SmartDigraph Digraph;
142
143  typedef Digraph::Arc Arc;
144  typedef Digraph::Node Node;
145  typedef Digraph::ArcIt ArcIt;
146  typedef Digraph::NodeIt NodeIt;
147  typedef Digraph::ArcMap<double> DoubleArcMap;
148  typedef Digraph::NodeMap<double> DoubleNodeMap;
149
150  std::string inputName;
151  std::string outputName;
152
153  ArgParser ap(argc, argv);
154  ap.other("[INFILE [OUTFILE]]",
155           "If either the INFILE or OUTFILE file is missing the standard\n"
156           "     input/output will be used instead.")
157    .boolOption("q", "Do not print any report")
158    .boolOption("int","Use 'int' for capacities, costs etc. (default)")
159    .optionGroup("datatype","int")
160#ifdef HAVE_LONG_LONG
161    .boolOption("long","Use 'long long' for capacities, costs etc.")
162    .optionGroup("datatype","long")
163#endif
164    .boolOption("double","Use 'double' for capacities, costs etc.")
165    .optionGroup("datatype","double")
166    .boolOption("ldouble","Use 'long double' for capacities, costs etc.")
167    .optionGroup("datatype","ldouble")
168    .onlyOneGroup("datatype")
169    .run();
170
171  std::ifstream input;
172  std::ofstream output;
173
174  switch(ap.files().size())
175    {
176    case 2:
177      output.open(ap.files()[1].c_str());
178      if (!output) {
179        throw IoError("Cannot open the file for writing", ap.files()[1]);
180      }
181    case 1:
182      input.open(ap.files()[0].c_str());
183      if (!input) {
184        throw IoError("File cannot be found", ap.files()[0]);
185      }
186    case 0:
187      break;
188    default:
189      std::cerr << ap.commandName() << ": too many arguments\n";
190      return 1;
191  }
192  std::istream& is = (ap.files().size()<1 ? std::cin : input);
193  std::ostream& os = (ap.files().size()<2 ? std::cout : output);
194
195  DimacsDescriptor desc = dimacsType(is);
196 
197  if(!ap.given("q"))
198    {
199      std::cout << "Problem type: ";
200      switch(desc.type)
201        {
202        case DimacsDescriptor::MIN:
203          std::cout << "min";
204          break;
205        case DimacsDescriptor::MAX:
206          std::cout << "max";
207          break;
208        case DimacsDescriptor::SP:
209          std::cout << "sp";
210        case DimacsDescriptor::MAT:
211          std::cout << "mat";
212          break;
213        default:
214          exit(1);
215          break;
216        }
217      std::cout << "\nNum of nodes: " << desc.nodeNum;
218      std::cout << "\nNum of arcs:  " << desc.edgeNum;
219      std::cout << '\n' << std::endl;
220    }
221   
222  if(ap.given("double"))
223    solve<double>(ap,is,os,desc);
224  else if(ap.given("ldouble"))
225    solve<long double>(ap,is,os,desc);
226#ifdef HAVE_LONG_LONG
227  else if(ap.given("long"))
228    solve<long long>(ap,is,os,desc);
229#endif
230  else solve<int>(ap,is,os,desc);
231
232  return 0;
233}
Note: See TracBrowser for help on using the repository browser.