1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/tools/dimacs-solver.cc Mon Feb 23 11:49:57 2009 +0000
1.3 @@ -0,0 +1,233 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2009
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +///\ingroup tools
1.23 +///\file
1.24 +///\brief DIMACS to LGF converter.
1.25 +///
1.26 +/// This program converts various DIMACS formats to the LEMON Digraph Format
1.27 +/// (LGF).
1.28 +///
1.29 +/// See
1.30 +/// \verbatim
1.31 +/// dimacs-solver --help
1.32 +/// \endverbatim
1.33 +/// for more info on usage.
1.34 +///
1.35 +
1.36 +#include <iostream>
1.37 +#include <fstream>
1.38 +#include <cstring>
1.39 +
1.40 +#include <lemon/smart_graph.h>
1.41 +#include <lemon/dimacs.h>
1.42 +#include <lemon/lgf_writer.h>
1.43 +#include <lemon/time_measure.h>
1.44 +
1.45 +#include <lemon/arg_parser.h>
1.46 +#include <lemon/error.h>
1.47 +
1.48 +#include <lemon/dijkstra.h>
1.49 +#include <lemon/preflow.h>
1.50 +#include <lemon/max_matching.h>
1.51 +
1.52 +using namespace lemon;
1.53 +typedef SmartDigraph Digraph;
1.54 +DIGRAPH_TYPEDEFS(Digraph);
1.55 +typedef SmartGraph Graph;
1.56 +
1.57 +template<class Value>
1.58 +void solve_sp(ArgParser &ap, std::istream &is, std::ostream &,
1.59 + DimacsDescriptor &desc)
1.60 +{
1.61 + bool report = !ap.given("q");
1.62 + Digraph g;
1.63 + Node s;
1.64 + Digraph::ArcMap<Value> len(g);
1.65 + Timer t;
1.66 + t.restart();
1.67 + readDimacsSp(is, g, len, s, desc);
1.68 + if(report) std::cerr << "Read the file: " << t << '\n';
1.69 + t.restart();
1.70 + Dijkstra<Digraph, Digraph::ArcMap<Value> > dij(g,len);
1.71 + if(report) std::cerr << "Setup Dijkstra class: " << t << '\n';
1.72 + t.restart();
1.73 + dij.run(s);
1.74 + if(report) std::cerr << "Run Dijkstra: " << t << '\n';
1.75 +}
1.76 +
1.77 +template<class Value>
1.78 +void solve_max(ArgParser &ap, std::istream &is, std::ostream &,
1.79 + DimacsDescriptor &desc)
1.80 +{
1.81 + bool report = !ap.given("q");
1.82 + Digraph g;
1.83 + Node s,t;
1.84 + Digraph::ArcMap<Value> cap(g);
1.85 + Timer ti;
1.86 + ti.restart();
1.87 + readDimacsMax(is, g, cap, s, t, desc);
1.88 + if(report) std::cerr << "Read the file: " << ti << '\n';
1.89 + ti.restart();
1.90 + Preflow<Digraph, Digraph::ArcMap<Value> > pre(g,cap,s,t);
1.91 + if(report) std::cerr << "Setup Preflow class: " << ti << '\n';
1.92 + ti.restart();
1.93 + pre.run();
1.94 + if(report) std::cerr << "Run Preflow: " << ti << '\n';
1.95 + if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n';
1.96 +}
1.97 +
1.98 +void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
1.99 + DimacsDescriptor &desc)
1.100 +{
1.101 + bool report = !ap.given("q");
1.102 + Graph g;
1.103 + Timer ti;
1.104 + ti.restart();
1.105 + readDimacsMat(is, g, desc);
1.106 + if(report) std::cerr << "Read the file: " << ti << '\n';
1.107 + ti.restart();
1.108 + MaxMatching<Graph> mat(g);
1.109 + if(report) std::cerr << "Setup MaxMatching class: " << ti << '\n';
1.110 + ti.restart();
1.111 + mat.run();
1.112 + if(report) std::cerr << "Run MaxMatching: " << ti << '\n';
1.113 + if(report) std::cerr << "\nCardinality of max matching: "
1.114 + << mat.matchingSize() << '\n';
1.115 +}
1.116 +
1.117 +
1.118 +template<class Value>
1.119 +void solve(ArgParser &ap, std::istream &is, std::ostream &os,
1.120 + DimacsDescriptor &desc)
1.121 +{
1.122 + switch(desc.type)
1.123 + {
1.124 + case DimacsDescriptor::MIN:
1.125 + std::cerr <<
1.126 + "\n\n Sorry, the min. cost flow solver is not yet available.\n"
1.127 + << std::endl;
1.128 + break;
1.129 + case DimacsDescriptor::MAX:
1.130 + solve_max<Value>(ap,is,os,desc);
1.131 + break;
1.132 + case DimacsDescriptor::SP:
1.133 + solve_sp<Value>(ap,is,os,desc);
1.134 + break;
1.135 + case DimacsDescriptor::MAT:
1.136 + solve_mat(ap,is,os,desc);
1.137 + break;
1.138 + default:
1.139 + break;
1.140 + }
1.141 +}
1.142 +
1.143 +int main(int argc, const char *argv[]) {
1.144 + typedef SmartDigraph Digraph;
1.145 +
1.146 + typedef Digraph::Arc Arc;
1.147 + typedef Digraph::Node Node;
1.148 + typedef Digraph::ArcIt ArcIt;
1.149 + typedef Digraph::NodeIt NodeIt;
1.150 + typedef Digraph::ArcMap<double> DoubleArcMap;
1.151 + typedef Digraph::NodeMap<double> DoubleNodeMap;
1.152 +
1.153 + std::string inputName;
1.154 + std::string outputName;
1.155 +
1.156 + ArgParser ap(argc, argv);
1.157 + ap.other("[INFILE [OUTFILE]]",
1.158 + "If either the INFILE or OUTFILE file is missing the standard\n"
1.159 + " input/output will be used instead.")
1.160 + .boolOption("q", "Do not print any report")
1.161 + .boolOption("int","Use 'int' for capacities, costs etc. (default)")
1.162 + .optionGroup("datatype","int")
1.163 +#ifdef HAVE_LONG_LONG
1.164 + .boolOption("long","Use 'long long' for capacities, costs etc.")
1.165 + .optionGroup("datatype","long")
1.166 +#endif
1.167 + .boolOption("double","Use 'double' for capacities, costs etc.")
1.168 + .optionGroup("datatype","double")
1.169 + .boolOption("ldouble","Use 'long double' for capacities, costs etc.")
1.170 + .optionGroup("datatype","ldouble")
1.171 + .onlyOneGroup("datatype")
1.172 + .run();
1.173 +
1.174 + std::ifstream input;
1.175 + std::ofstream output;
1.176 +
1.177 + switch(ap.files().size())
1.178 + {
1.179 + case 2:
1.180 + output.open(ap.files()[1].c_str());
1.181 + if (!output) {
1.182 + throw IoError("Cannot open the file for writing", ap.files()[1]);
1.183 + }
1.184 + case 1:
1.185 + input.open(ap.files()[0].c_str());
1.186 + if (!input) {
1.187 + throw IoError("File cannot be found", ap.files()[0]);
1.188 + }
1.189 + case 0:
1.190 + break;
1.191 + default:
1.192 + std::cerr << ap.commandName() << ": too many arguments\n";
1.193 + return 1;
1.194 + }
1.195 + std::istream& is = (ap.files().size()<1 ? std::cin : input);
1.196 + std::ostream& os = (ap.files().size()<2 ? std::cout : output);
1.197 +
1.198 + DimacsDescriptor desc = dimacsType(is);
1.199 +
1.200 + if(!ap.given("q"))
1.201 + {
1.202 + std::cout << "Problem type: ";
1.203 + switch(desc.type)
1.204 + {
1.205 + case DimacsDescriptor::MIN:
1.206 + std::cout << "min";
1.207 + break;
1.208 + case DimacsDescriptor::MAX:
1.209 + std::cout << "max";
1.210 + break;
1.211 + case DimacsDescriptor::SP:
1.212 + std::cout << "sp";
1.213 + case DimacsDescriptor::MAT:
1.214 + std::cout << "mat";
1.215 + break;
1.216 + default:
1.217 + exit(1);
1.218 + break;
1.219 + }
1.220 + std::cout << "\nNum of nodes: " << desc.nodeNum;
1.221 + std::cout << "\nNum of arcs: " << desc.edgeNum;
1.222 + std::cout << '\n' << std::endl;
1.223 + }
1.224 +
1.225 + if(ap.given("double"))
1.226 + solve<double>(ap,is,os,desc);
1.227 + else if(ap.given("ldouble"))
1.228 + solve<long double>(ap,is,os,desc);
1.229 +#ifdef HAVE_LONG_LONG
1.230 + else if(ap.given("long"))
1.231 + solve<long long>(ap,is,os,desc);
1.232 +#endif
1.233 + else solve<int>(ap,is,os,desc);
1.234 +
1.235 + return 0;
1.236 +}