diff --git a/tools/Makefile.am b/tools/Makefile.am --- a/tools/Makefile.am +++ b/tools/Makefile.am @@ -1,6 +1,7 @@ if WANT_TOOLS bin_PROGRAMS += \ + tools/dimacs-solver \ tools/dimacs-to-lgf \ tools/lgf-gen @@ -8,5 +9,6 @@ endif WANT_TOOLS +tools_dimacs_solver_SOURCES = tools/dimacs-solver.cc tools_dimacs_to_lgf_SOURCES = tools/dimacs-to-lgf.cc tools_lgf_gen_SOURCES = tools/lgf-gen.cc diff --git a/tools/dimacs-to-lgf.cc b/tools/dimacs-solver.cc copy from tools/dimacs-to-lgf.cc copy to tools/dimacs-solver.cc --- a/tools/dimacs-to-lgf.cc +++ b/tools/dimacs-solver.cc @@ -25,7 +25,7 @@ /// /// See /// \verbatim -/// dimacs-to-lgf --help +/// dimacs-solver --help /// \endverbatim /// for more info on usage. /// @@ -37,13 +37,105 @@ #include #include #include +#include #include #include -using namespace std; +#include +#include +#include + using namespace lemon; +typedef SmartDigraph Digraph; +DIGRAPH_TYPEDEFS(Digraph); +typedef SmartGraph Graph; +template +void solve_sp(ArgParser &ap, std::istream &is, std::ostream &, + DimacsDescriptor &desc) +{ + bool report = !ap.given("q"); + Digraph g; + Node s; + Digraph::ArcMap len(g); + Timer t; + t.restart(); + readDimacsSp(is, g, len, s, desc); + if(report) std::cerr << "Read the file: " << t << '\n'; + t.restart(); + Dijkstra > dij(g,len); + if(report) std::cerr << "Setup Dijkstra class: " << t << '\n'; + t.restart(); + dij.run(s); + if(report) std::cerr << "Run Dijkstra: " << t << '\n'; +} + +template +void solve_max(ArgParser &ap, std::istream &is, std::ostream &, + DimacsDescriptor &desc) +{ + bool report = !ap.given("q"); + Digraph g; + Node s,t; + Digraph::ArcMap cap(g); + Timer ti; + ti.restart(); + readDimacsMax(is, g, cap, s, t, desc); + if(report) std::cerr << "Read the file: " << ti << '\n'; + ti.restart(); + Preflow > pre(g,cap,s,t); + if(report) std::cerr << "Setup Preflow class: " << ti << '\n'; + ti.restart(); + pre.run(); + if(report) std::cerr << "Run Preflow: " << ti << '\n'; + if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n'; +} + +void solve_mat(ArgParser &ap, std::istream &is, std::ostream &, + DimacsDescriptor &desc) +{ + bool report = !ap.given("q"); + Graph g; + Timer ti; + ti.restart(); + readDimacsMat(is, g, desc); + if(report) std::cerr << "Read the file: " << ti << '\n'; + ti.restart(); + MaxMatching mat(g); + if(report) std::cerr << "Setup MaxMatching class: " << ti << '\n'; + ti.restart(); + mat.run(); + if(report) std::cerr << "Run MaxMatching: " << ti << '\n'; + if(report) std::cerr << "\nCardinality of max matching: " + << mat.matchingSize() << '\n'; +} + + +template +void solve(ArgParser &ap, std::istream &is, std::ostream &os, + DimacsDescriptor &desc) +{ + switch(desc.type) + { + case DimacsDescriptor::MIN: + std::cerr << + "\n\n Sorry, the min. cost flow solver is not yet available.\n" + << std::endl; + break; + case DimacsDescriptor::MAX: + solve_max(ap,is,os,desc); + break; + case DimacsDescriptor::SP: + solve_sp(ap,is,os,desc); + break; + case DimacsDescriptor::MAT: + solve_mat(ap,is,os,desc); + break; + default: + break; + } +} int main(int argc, const char *argv[]) { typedef SmartDigraph Digraph; @@ -62,10 +154,22 @@ ap.other("[INFILE [OUTFILE]]", "If either the INFILE or OUTFILE file is missing the standard\n" " input/output will be used instead.") + .boolOption("q", "Do not print any report") + .boolOption("int","Use 'int' for capacities, costs etc. (default)") + .optionGroup("datatype","int") +#ifdef HAVE_LONG_LONG + .boolOption("long","Use 'long long' for capacities, costs etc.") + .optionGroup("datatype","long") +#endif + .boolOption("double","Use 'double' for capacities, costs etc.") + .optionGroup("datatype","double") + .boolOption("ldouble","Use 'long double' for capacities, costs etc.") + .optionGroup("datatype","ldouble") + .onlyOneGroup("datatype") .run(); - ifstream input; - ofstream output; + std::ifstream input; + std::ofstream output; switch(ap.files().size()) { @@ -82,68 +186,48 @@ case 0: break; default: - cerr << ap.commandName() << ": too many arguments\n"; + std::cerr << ap.commandName() << ": too many arguments\n"; return 1; } - istream& is = (ap.files().size()<1 ? cin : input); - ostream& os = (ap.files().size()<2 ? cout : output); + std::istream& is = (ap.files().size()<1 ? std::cin : input); + std::ostream& os = (ap.files().size()<2 ? std::cout : output); DimacsDescriptor desc = dimacsType(is); - switch(desc.type) + + if(!ap.given("q")) { - case DimacsDescriptor::MIN: - { - Digraph digraph; - DoubleArcMap lower(digraph), capacity(digraph), cost(digraph); - DoubleNodeMap supply(digraph); - readDimacsMin(is, digraph, lower, capacity, cost, supply, desc); - DigraphWriter(digraph, os). - nodeMap("supply", supply). - arcMap("lower", lower). - arcMap("capacity", capacity). - arcMap("cost", cost). - attribute("problem","min"). - run(); - } - break; - case DimacsDescriptor::MAX: - { - Digraph digraph; - Node s, t; - DoubleArcMap capacity(digraph); - readDimacsMax(is, digraph, capacity, s, t, desc); - DigraphWriter(digraph, os). - arcMap("capacity", capacity). - node("source", s). - node("target", t). - attribute("problem","max"). - run(); - } - break; - case DimacsDescriptor::SP: - { - Digraph digraph; - Node s; - DoubleArcMap capacity(digraph); - readDimacsSp(is, digraph, capacity, s, desc); - DigraphWriter(digraph, os). - arcMap("capacity", capacity). - node("source", s). - attribute("problem","sp"). - run(); - } - break; - case DimacsDescriptor::MAT: - { - Digraph digraph; - readDimacsMat(is, digraph,desc); - DigraphWriter(digraph, os). - attribute("problem","mat"). - run(); - } - break; - default: - break; + std::cout << "Problem type: "; + switch(desc.type) + { + case DimacsDescriptor::MIN: + std::cout << "min"; + break; + case DimacsDescriptor::MAX: + std::cout << "max"; + break; + case DimacsDescriptor::SP: + std::cout << "sp"; + case DimacsDescriptor::MAT: + std::cout << "mat"; + break; + default: + exit(1); + break; + } + std::cout << "\nNum of nodes: " << desc.nodeNum; + std::cout << "\nNum of arcs: " << desc.edgeNum; + std::cout << '\n' << std::endl; } + + if(ap.given("double")) + solve(ap,is,os,desc); + else if(ap.given("ldouble")) + solve(ap,is,os,desc); +#ifdef HAVE_LONG_LONG + else if(ap.given("long")) + solve(ap,is,os,desc); +#endif + else solve(ap,is,os,desc); + return 0; }