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" : "not found") << '\n';
131 if (res) std::cerr << "Min flow cost: "
132 << ns.template totalCost<LargeValue>() << '\n';
136 void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
137 DimacsDescriptor &desc)
139 bool report = !ap.given("q");
143 readDimacsMat(is, g, desc);
144 if(report) std::cerr << "Read the file: " << ti << '\n';
146 MaxMatching<Graph> mat(g);
147 if(report) std::cerr << "Setup MaxMatching class: " << ti << '\n';
150 if(report) std::cerr << "Run MaxMatching: " << ti << '\n';
151 if(report) std::cerr << "\nCardinality of max matching: "
152 << mat.matchingSize() << '\n';
156 template<class Value, class LargeValue>
157 void solve(ArgParser &ap, std::istream &is, std::ostream &os,
158 DimacsDescriptor &desc)
160 std::stringstream iss(static_cast<std::string>(ap["infcap"]));
165 std::cerr << "Cannot interpret '"
166 << static_cast<std::string>(ap["infcap"]) << "' as infinite"
173 case DimacsDescriptor::MIN:
174 solve_min<Value, LargeValue>(ap,is,os,infty,desc);
176 case DimacsDescriptor::MAX:
177 solve_max<Value>(ap,is,os,infty,desc);
179 case DimacsDescriptor::SP:
180 solve_sp<Value>(ap,is,os,desc);
182 case DimacsDescriptor::MAT:
183 solve_mat(ap,is,os,desc);
190 int main(int argc, const char *argv[]) {
192 std::string inputName;
193 std::string outputName;
195 ArgParser ap(argc, argv);
196 ap.other("[INFILE [OUTFILE]]",
197 "If either the INFILE or OUTFILE file is missing the standard\n"
198 " input/output will be used instead.")
199 .boolOption("q", "Do not print any report")
200 .boolOption("int","Use 'int' for capacities, costs etc. (default)")
201 .optionGroup("datatype","int")
202 #ifdef LEMON_HAVE_LONG_LONG
203 .boolOption("long","Use 'long long' for capacities, costs etc.")
204 .optionGroup("datatype","long")
206 .boolOption("double","Use 'double' for capacities, costs etc.")
207 .optionGroup("datatype","double")
208 .boolOption("ldouble","Use 'long double' for capacities, costs etc.")
209 .optionGroup("datatype","ldouble")
210 .onlyOneGroup("datatype")
211 .stringOption("infcap","Value used for 'very high' capacities","0")
215 std::ofstream output;
217 switch(ap.files().size())
220 output.open(ap.files()[1].c_str());
222 throw IoError("Cannot open the file for writing", ap.files()[1]);
225 input.open(ap.files()[0].c_str());
227 throw IoError("File cannot be found", ap.files()[0]);
232 std::cerr << ap.commandName() << ": too many arguments\n";
235 std::istream& is = (ap.files().size()<1 ? std::cin : input);
236 std::ostream& os = (ap.files().size()<2 ? std::cout : output);
238 DimacsDescriptor desc = dimacsType(is);
242 std::cout << "Problem type: ";
245 case DimacsDescriptor::MIN:
248 case DimacsDescriptor::MAX:
251 case DimacsDescriptor::SP:
253 case DimacsDescriptor::MAT:
260 std::cout << "\nNum of nodes: " << desc.nodeNum;
261 std::cout << "\nNum of arcs: " << desc.edgeNum;
265 if(ap.given("double"))
266 solve<double, double>(ap,is,os,desc);
267 else if(ap.given("ldouble"))
268 solve<long double, long double>(ap,is,os,desc);
269 #ifdef LEMON_HAVE_LONG_LONG
270 else if(ap.given("long"))
271 solve<long long, long long>(ap,is,os,desc);
272 else solve<int, long long>(ap,is,os,desc);
274 else solve<int, long>(ap,is,os,desc);