Add missing include header and std:: namespace spec. (#487)
1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2013
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
21 ///\brief DIMACS problem solver.
23 /// This program solves various problems given in DIMACS format.
27 /// dimacs-solver --help
29 /// for more info on usage.
35 #include <lemon/smart_graph.h>
36 #include <lemon/dimacs.h>
37 #include <lemon/lgf_writer.h>
38 #include <lemon/time_measure.h>
40 #include <lemon/arg_parser.h>
41 #include <lemon/error.h>
43 #include <lemon/dijkstra.h>
44 #include <lemon/preflow.h>
45 #include <lemon/matching.h>
46 #include <lemon/network_simplex.h>
48 using namespace lemon;
49 typedef SmartDigraph Digraph;
50 DIGRAPH_TYPEDEFS(Digraph);
51 typedef SmartGraph Graph;
54 void solve_sp(ArgParser &ap, std::istream &is, std::ostream &,
55 DimacsDescriptor &desc)
57 bool report = !ap.given("q");
60 Digraph::ArcMap<Value> len(g);
63 readDimacsSp(is, g, len, s, desc);
64 if(report) std::cerr << "Read the file: " << t << '\n';
66 Dijkstra<Digraph, Digraph::ArcMap<Value> > dij(g,len);
67 if(report) std::cerr << "Setup Dijkstra class: " << t << '\n';
70 if(report) std::cerr << "Run Dijkstra: " << t << '\n';
74 void solve_max(ArgParser &ap, std::istream &is, std::ostream &,
75 Value infty, DimacsDescriptor &desc)
77 bool report = !ap.given("q");
80 Digraph::ArcMap<Value> cap(g);
83 readDimacsMax(is, g, cap, s, t, infty, desc);
84 if(report) std::cerr << "Read the file: " << ti << '\n';
86 Preflow<Digraph, Digraph::ArcMap<Value> > pre(g,cap,s,t);
87 if(report) std::cerr << "Setup Preflow class: " << ti << '\n';
90 if(report) std::cerr << "Run Preflow: " << ti << '\n';
91 if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n';
94 template<class Value, class LargeValue>
95 void solve_min(ArgParser &ap, std::istream &is, std::ostream &,
96 Value infty, DimacsDescriptor &desc)
98 bool report = !ap.given("q");
100 Digraph::ArcMap<Value> lower(g), cap(g), cost(g);
101 Digraph::NodeMap<Value> sup(g);
105 readDimacsMin(is, g, lower, cap, cost, sup, infty, desc);
108 for (Digraph::NodeIt n(g); n != INVALID; ++n) {
112 std::cerr << "Sum of supply values: " << sum_sup << "\n";
114 std::cerr << "GEQ supply contraints are used for NetworkSimplex\n\n";
116 std::cerr << "LEQ supply contraints are used for NetworkSimplex\n\n";
118 if (report) std::cerr << "Read the file: " << ti << '\n';
120 typedef NetworkSimplex<Digraph, Value> MCF;
123 ns.lowerMap(lower).upperMap(cap).costMap(cost).supplyMap(sup);
124 if (sum_sup > 0) ns.supplyType(ns.LEQ);
125 if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n';
127 typename MCF::ProblemType res = ns.run();
129 std::cerr << "Run NetworkSimplex: " << ti << "\n\n";
130 std::cerr << "Feasible flow: " << (res == MCF::OPTIMAL ? "found" :
131 "not found") << '\n';
132 if (res) std::cerr << "Min flow cost: "
133 << ns.template totalCost<LargeValue>() << '\n';
137 void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
138 DimacsDescriptor &desc)
140 bool report = !ap.given("q");
144 readDimacsMat(is, g, desc);
145 if(report) std::cerr << "Read the file: " << ti << '\n';
147 MaxMatching<Graph> mat(g);
148 if(report) std::cerr << "Setup MaxMatching class: " << ti << '\n';
151 if(report) std::cerr << "Run MaxMatching: " << ti << '\n';
152 if(report) std::cerr << "\nCardinality of max matching: "
153 << mat.matchingSize() << '\n';
157 template<class Value, class LargeValue>
158 void solve(ArgParser &ap, std::istream &is, std::ostream &os,
159 DimacsDescriptor &desc)
161 std::stringstream iss(static_cast<std::string>(ap["infcap"]));
166 std::cerr << "Cannot interpret '"
167 << static_cast<std::string>(ap["infcap"]) << "' as infinite"
174 case DimacsDescriptor::MIN:
175 solve_min<Value, LargeValue>(ap,is,os,infty,desc);
177 case DimacsDescriptor::MAX:
178 solve_max<Value>(ap,is,os,infty,desc);
180 case DimacsDescriptor::SP:
181 solve_sp<Value>(ap,is,os,desc);
183 case DimacsDescriptor::MAT:
184 solve_mat(ap,is,os,desc);
191 int main(int argc, const char *argv[]) {
193 std::string inputName;
194 std::string outputName;
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 LEMON_HAVE_LONG_LONG
204 .boolOption("long","Use 'long long' for capacities, costs etc.")
205 .optionGroup("datatype","long")
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")
216 std::ofstream output;
218 switch(ap.files().size())
221 output.open(ap.files()[1].c_str());
223 throw IoError("Cannot open the file for writing", ap.files()[1]);
226 input.open(ap.files()[0].c_str());
228 throw IoError("File cannot be found", ap.files()[0]);
233 std::cerr << ap.commandName() << ": too many arguments\n";
236 std::istream& is = (ap.files().size()<1 ? std::cin : input);
237 std::ostream& os = (ap.files().size()<2 ? std::cout : output);
239 DimacsDescriptor desc = dimacsType(is);
243 std::cout << "Problem type: ";
246 case DimacsDescriptor::MIN:
249 case DimacsDescriptor::MAX:
252 case DimacsDescriptor::SP:
254 case DimacsDescriptor::MAT:
261 std::cout << "\nNum of nodes: " << desc.nodeNum;
262 std::cout << "\nNum of arcs: " << desc.edgeNum;
266 if(ap.given("double"))
267 solve<double, double>(ap,is,os,desc);
268 else if(ap.given("ldouble"))
269 solve<long double, long double>(ap,is,os,desc);
270 #ifdef LEMON_HAVE_LONG_LONG
271 else if(ap.given("long"))
272 solve<long long, long long>(ap,is,os,desc);
273 else solve<int, long long>(ap,is,os,desc);
275 else solve<int, long>(ap,is,os,desc);