COIN-OR::LEMON - Graph Library

source: lemon/tools/dimacs-solver.cc @ 687:6c408d864fa1

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

Support negative costs and bounds in NetworkSimplex? (#270)

  • The interface is reworked to support negative costs and bounds.
    • ProblemType? and problemType() are renamed to SupplyType? and supplyType(), see also #234.
    • ProblemType? type is introduced similarly to the LP interface.
    • 'bool run()' is replaced by 'ProblemType? run()' to handle unbounded problem instances, as well.
    • Add INF public member constant similarly to the LP interface.
  • Remove capacityMap() and boundMaps(), see also #266.
  • Update the problem definition in the MCF module.
  • Remove the usage of Circulation (and adaptors) for checking feasibility. Check feasibility by examining the artifical arcs instead (after solving the problem).
  • Additional check for unbounded negative cycles found during the algorithm (it is possible now, since negative costs are allowed).
  • Fix in the constructor (the value types needn't be integer any more), see also #254.
  • Improve and extend the doc.
  • Rework the test file and add test cases for negative costs and bounds.
File size: 7.6 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               Value infty, 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
104  ti.restart();
105  readDimacsMin(is, g, lower, cap, cost, sup, infty, desc);
106  ti.stop();
107  Value sum_sup = 0;
108  for (Digraph::NodeIt n(g); n != INVALID; ++n) {
109    sum_sup += sup[n];
110  }
111  if (report) {
112    std::cerr << "Sum of supply values: " << sum_sup << "\n";
113    if (sum_sup <= 0)
114      std::cerr << "GEQ supply contraints are used for NetworkSimplex\n\n";
115    else
116      std::cerr << "LEQ supply contraints are used for NetworkSimplex\n\n";
117  }
118  if (report) std::cerr << "Read the file: " << ti << '\n';
119
120  ti.restart();
121  NetworkSimplex<Digraph, Value> ns(g);
122  ns.lowerMap(lower).upperMap(cap).costMap(cost).supplyMap(sup);
123  if (sum_sup > 0) ns.supplyType(ns.LEQ);
124  if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n';
125  ti.restart();
126  bool res = ns.run();
127  if (report) {
128    std::cerr << "Run NetworkSimplex: " << ti << "\n\n";
129    std::cerr << "Feasible flow: " << (res ? "found" : "not found") << '\n';
130    if (res) std::cerr << "Min flow cost: " << ns.totalCost() << '\n';
131  }
132}
133
134void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
135              DimacsDescriptor &desc)
136{
137  bool report = !ap.given("q");
138  Graph g;
139  Timer ti;
140  ti.restart();
141  readDimacsMat(is, g, desc);
142  if(report) std::cerr << "Read the file: " << ti << '\n';
143  ti.restart();
144  MaxMatching<Graph> mat(g);
145  if(report) std::cerr << "Setup MaxMatching class: " << ti << '\n';
146  ti.restart();
147  mat.run();
148  if(report) std::cerr << "Run MaxMatching: " << ti << '\n';
149  if(report) std::cerr << "\nCardinality of max matching: "
150                       << mat.matchingSize() << '\n'; 
151}
152
153
154template<class Value>
155void solve(ArgParser &ap, std::istream &is, std::ostream &os,
156           DimacsDescriptor &desc)
157{
158  std::stringstream iss(static_cast<std::string>(ap["infcap"]));
159  Value infty;
160  iss >> infty;
161  if(iss.fail())
162    {
163      std::cerr << "Cannot interpret '"
164                << static_cast<std::string>(ap["infcap"]) << "' as infinite"
165                << std::endl;
166      exit(1);
167    }
168 
169  switch(desc.type)
170    {
171    case DimacsDescriptor::MIN:
172      solve_min<Value>(ap,is,os,infty,desc);
173      break;
174    case DimacsDescriptor::MAX:
175      solve_max<Value>(ap,is,os,infty,desc);
176      break;
177    case DimacsDescriptor::SP:
178      solve_sp<Value>(ap,is,os,desc);
179      break;
180    case DimacsDescriptor::MAT:
181      solve_mat(ap,is,os,desc);
182      break;
183    default:
184      break;
185    }
186}
187
188int main(int argc, const char *argv[]) {
189  typedef SmartDigraph Digraph;
190
191  typedef Digraph::Arc Arc;
192
193  std::string inputName;
194  std::string outputName;
195
196  ArgParser ap(argc, argv);
197  ap.other("[INFILE [OUTFILE]]",
198           "If either the INFILE or OUTFILE file is missing the standard\n"
199           "     input/output will be used instead.")
200    .boolOption("q", "Do not print any report")
201    .boolOption("int","Use 'int' for capacities, costs etc. (default)")
202    .optionGroup("datatype","int")
203#ifdef HAVE_LONG_LONG
204    .boolOption("long","Use 'long long' for capacities, costs etc.")
205    .optionGroup("datatype","long")
206#endif
207    .boolOption("double","Use 'double' for capacities, costs etc.")
208    .optionGroup("datatype","double")
209    .boolOption("ldouble","Use 'long double' for capacities, costs etc.")
210    .optionGroup("datatype","ldouble")
211    .onlyOneGroup("datatype")
212    .stringOption("infcap","Value used for 'very high' capacities","0")
213    .run();
214
215  std::ifstream input;
216  std::ofstream output;
217
218  switch(ap.files().size())
219    {
220    case 2:
221      output.open(ap.files()[1].c_str());
222      if (!output) {
223        throw IoError("Cannot open the file for writing", ap.files()[1]);
224      }
225    case 1:
226      input.open(ap.files()[0].c_str());
227      if (!input) {
228        throw IoError("File cannot be found", ap.files()[0]);
229      }
230    case 0:
231      break;
232    default:
233      std::cerr << ap.commandName() << ": too many arguments\n";
234      return 1;
235    }
236  std::istream& is = (ap.files().size()<1 ? std::cin : input);
237  std::ostream& os = (ap.files().size()<2 ? std::cout : output);
238
239  DimacsDescriptor desc = dimacsType(is);
240 
241  if(!ap.given("q"))
242    {
243      std::cout << "Problem type: ";
244      switch(desc.type)
245        {
246        case DimacsDescriptor::MIN:
247          std::cout << "min";
248          break;
249        case DimacsDescriptor::MAX:
250          std::cout << "max";
251          break;
252        case DimacsDescriptor::SP:
253          std::cout << "sp";
254        case DimacsDescriptor::MAT:
255          std::cout << "mat";
256          break;
257        default:
258          exit(1);
259          break;
260        }
261      std::cout << "\nNum of nodes: " << desc.nodeNum;
262      std::cout << "\nNum of arcs:  " << desc.edgeNum;
263      std::cout << "\n\n";
264    }
265   
266  if(ap.given("double"))
267    solve<double>(ap,is,os,desc);
268  else if(ap.given("ldouble"))
269    solve<long double>(ap,is,os,desc);
270#ifdef HAVE_LONG_LONG
271  else if(ap.given("long"))
272    solve<long long>(ap,is,os,desc);
273#endif
274  else solve<int>(ap,is,os,desc);
275
276  return 0;
277}
Note: See TracBrowser for help on using the repository browser.