COIN-OR::LEMON - Graph Library

source: lemon/tools/dimacs-solver.cc @ 649:a79ef774fae1

Last change on this file since 649:a79ef774fae1 was 649:a79ef774fae1, checked in by Peter Kovacs <kpeter@…>, 11 years ago

Support min cost flow in dimacs-solver (#234)

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