1.1 --- a/tools/Makefile.am Mon Feb 23 11:48:47 2009 +0000
1.2 +++ b/tools/Makefile.am Mon Feb 23 11:49:57 2009 +0000
1.3 @@ -1,6 +1,7 @@
1.4 if WANT_TOOLS
1.5
1.6 bin_PROGRAMS += \
1.7 + tools/dimacs-solver \
1.8 tools/dimacs-to-lgf \
1.9 tools/lgf-gen
1.10
1.11 @@ -8,5 +9,6 @@
1.12
1.13 endif WANT_TOOLS
1.14
1.15 +tools_dimacs_solver_SOURCES = tools/dimacs-solver.cc
1.16 tools_dimacs_to_lgf_SOURCES = tools/dimacs-to-lgf.cc
1.17 tools_lgf_gen_SOURCES = tools/lgf-gen.cc
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/tools/dimacs-solver.cc Mon Feb 23 11:49:57 2009 +0000
2.3 @@ -0,0 +1,233 @@
2.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
2.5 + *
2.6 + * This file is a part of LEMON, a generic C++ optimization library.
2.7 + *
2.8 + * Copyright (C) 2003-2009
2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.11 + *
2.12 + * Permission to use, modify and distribute this software is granted
2.13 + * provided that this copyright notice appears in all copies. For
2.14 + * precise terms see the accompanying LICENSE file.
2.15 + *
2.16 + * This software is provided "AS IS" with no warranty of any kind,
2.17 + * express or implied, and with no claim as to its suitability for any
2.18 + * purpose.
2.19 + *
2.20 + */
2.21 +
2.22 +///\ingroup tools
2.23 +///\file
2.24 +///\brief DIMACS to LGF converter.
2.25 +///
2.26 +/// This program converts various DIMACS formats to the LEMON Digraph Format
2.27 +/// (LGF).
2.28 +///
2.29 +/// See
2.30 +/// \verbatim
2.31 +/// dimacs-solver --help
2.32 +/// \endverbatim
2.33 +/// for more info on usage.
2.34 +///
2.35 +
2.36 +#include <iostream>
2.37 +#include <fstream>
2.38 +#include <cstring>
2.39 +
2.40 +#include <lemon/smart_graph.h>
2.41 +#include <lemon/dimacs.h>
2.42 +#include <lemon/lgf_writer.h>
2.43 +#include <lemon/time_measure.h>
2.44 +
2.45 +#include <lemon/arg_parser.h>
2.46 +#include <lemon/error.h>
2.47 +
2.48 +#include <lemon/dijkstra.h>
2.49 +#include <lemon/preflow.h>
2.50 +#include <lemon/max_matching.h>
2.51 +
2.52 +using namespace lemon;
2.53 +typedef SmartDigraph Digraph;
2.54 +DIGRAPH_TYPEDEFS(Digraph);
2.55 +typedef SmartGraph Graph;
2.56 +
2.57 +template<class Value>
2.58 +void solve_sp(ArgParser &ap, std::istream &is, std::ostream &,
2.59 + DimacsDescriptor &desc)
2.60 +{
2.61 + bool report = !ap.given("q");
2.62 + Digraph g;
2.63 + Node s;
2.64 + Digraph::ArcMap<Value> len(g);
2.65 + Timer t;
2.66 + t.restart();
2.67 + readDimacsSp(is, g, len, s, desc);
2.68 + if(report) std::cerr << "Read the file: " << t << '\n';
2.69 + t.restart();
2.70 + Dijkstra<Digraph, Digraph::ArcMap<Value> > dij(g,len);
2.71 + if(report) std::cerr << "Setup Dijkstra class: " << t << '\n';
2.72 + t.restart();
2.73 + dij.run(s);
2.74 + if(report) std::cerr << "Run Dijkstra: " << t << '\n';
2.75 +}
2.76 +
2.77 +template<class Value>
2.78 +void solve_max(ArgParser &ap, std::istream &is, std::ostream &,
2.79 + DimacsDescriptor &desc)
2.80 +{
2.81 + bool report = !ap.given("q");
2.82 + Digraph g;
2.83 + Node s,t;
2.84 + Digraph::ArcMap<Value> cap(g);
2.85 + Timer ti;
2.86 + ti.restart();
2.87 + readDimacsMax(is, g, cap, s, t, desc);
2.88 + if(report) std::cerr << "Read the file: " << ti << '\n';
2.89 + ti.restart();
2.90 + Preflow<Digraph, Digraph::ArcMap<Value> > pre(g,cap,s,t);
2.91 + if(report) std::cerr << "Setup Preflow class: " << ti << '\n';
2.92 + ti.restart();
2.93 + pre.run();
2.94 + if(report) std::cerr << "Run Preflow: " << ti << '\n';
2.95 + if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n';
2.96 +}
2.97 +
2.98 +void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
2.99 + DimacsDescriptor &desc)
2.100 +{
2.101 + bool report = !ap.given("q");
2.102 + Graph g;
2.103 + Timer ti;
2.104 + ti.restart();
2.105 + readDimacsMat(is, g, desc);
2.106 + if(report) std::cerr << "Read the file: " << ti << '\n';
2.107 + ti.restart();
2.108 + MaxMatching<Graph> mat(g);
2.109 + if(report) std::cerr << "Setup MaxMatching class: " << ti << '\n';
2.110 + ti.restart();
2.111 + mat.run();
2.112 + if(report) std::cerr << "Run MaxMatching: " << ti << '\n';
2.113 + if(report) std::cerr << "\nCardinality of max matching: "
2.114 + << mat.matchingSize() << '\n';
2.115 +}
2.116 +
2.117 +
2.118 +template<class Value>
2.119 +void solve(ArgParser &ap, std::istream &is, std::ostream &os,
2.120 + DimacsDescriptor &desc)
2.121 +{
2.122 + switch(desc.type)
2.123 + {
2.124 + case DimacsDescriptor::MIN:
2.125 + std::cerr <<
2.126 + "\n\n Sorry, the min. cost flow solver is not yet available.\n"
2.127 + << std::endl;
2.128 + break;
2.129 + case DimacsDescriptor::MAX:
2.130 + solve_max<Value>(ap,is,os,desc);
2.131 + break;
2.132 + case DimacsDescriptor::SP:
2.133 + solve_sp<Value>(ap,is,os,desc);
2.134 + break;
2.135 + case DimacsDescriptor::MAT:
2.136 + solve_mat(ap,is,os,desc);
2.137 + break;
2.138 + default:
2.139 + break;
2.140 + }
2.141 +}
2.142 +
2.143 +int main(int argc, const char *argv[]) {
2.144 + typedef SmartDigraph Digraph;
2.145 +
2.146 + typedef Digraph::Arc Arc;
2.147 + typedef Digraph::Node Node;
2.148 + typedef Digraph::ArcIt ArcIt;
2.149 + typedef Digraph::NodeIt NodeIt;
2.150 + typedef Digraph::ArcMap<double> DoubleArcMap;
2.151 + typedef Digraph::NodeMap<double> DoubleNodeMap;
2.152 +
2.153 + std::string inputName;
2.154 + std::string outputName;
2.155 +
2.156 + ArgParser ap(argc, argv);
2.157 + ap.other("[INFILE [OUTFILE]]",
2.158 + "If either the INFILE or OUTFILE file is missing the standard\n"
2.159 + " input/output will be used instead.")
2.160 + .boolOption("q", "Do not print any report")
2.161 + .boolOption("int","Use 'int' for capacities, costs etc. (default)")
2.162 + .optionGroup("datatype","int")
2.163 +#ifdef HAVE_LONG_LONG
2.164 + .boolOption("long","Use 'long long' for capacities, costs etc.")
2.165 + .optionGroup("datatype","long")
2.166 +#endif
2.167 + .boolOption("double","Use 'double' for capacities, costs etc.")
2.168 + .optionGroup("datatype","double")
2.169 + .boolOption("ldouble","Use 'long double' for capacities, costs etc.")
2.170 + .optionGroup("datatype","ldouble")
2.171 + .onlyOneGroup("datatype")
2.172 + .run();
2.173 +
2.174 + std::ifstream input;
2.175 + std::ofstream output;
2.176 +
2.177 + switch(ap.files().size())
2.178 + {
2.179 + case 2:
2.180 + output.open(ap.files()[1].c_str());
2.181 + if (!output) {
2.182 + throw IoError("Cannot open the file for writing", ap.files()[1]);
2.183 + }
2.184 + case 1:
2.185 + input.open(ap.files()[0].c_str());
2.186 + if (!input) {
2.187 + throw IoError("File cannot be found", ap.files()[0]);
2.188 + }
2.189 + case 0:
2.190 + break;
2.191 + default:
2.192 + std::cerr << ap.commandName() << ": too many arguments\n";
2.193 + return 1;
2.194 + }
2.195 + std::istream& is = (ap.files().size()<1 ? std::cin : input);
2.196 + std::ostream& os = (ap.files().size()<2 ? std::cout : output);
2.197 +
2.198 + DimacsDescriptor desc = dimacsType(is);
2.199 +
2.200 + if(!ap.given("q"))
2.201 + {
2.202 + std::cout << "Problem type: ";
2.203 + switch(desc.type)
2.204 + {
2.205 + case DimacsDescriptor::MIN:
2.206 + std::cout << "min";
2.207 + break;
2.208 + case DimacsDescriptor::MAX:
2.209 + std::cout << "max";
2.210 + break;
2.211 + case DimacsDescriptor::SP:
2.212 + std::cout << "sp";
2.213 + case DimacsDescriptor::MAT:
2.214 + std::cout << "mat";
2.215 + break;
2.216 + default:
2.217 + exit(1);
2.218 + break;
2.219 + }
2.220 + std::cout << "\nNum of nodes: " << desc.nodeNum;
2.221 + std::cout << "\nNum of arcs: " << desc.edgeNum;
2.222 + std::cout << '\n' << std::endl;
2.223 + }
2.224 +
2.225 + if(ap.given("double"))
2.226 + solve<double>(ap,is,os,desc);
2.227 + else if(ap.given("ldouble"))
2.228 + solve<long double>(ap,is,os,desc);
2.229 +#ifdef HAVE_LONG_LONG
2.230 + else if(ap.given("long"))
2.231 + solve<long long>(ap,is,os,desc);
2.232 +#endif
2.233 + else solve<int>(ap,is,os,desc);
2.234 +
2.235 + return 0;
2.236 +}