alpar@385: /* -*- mode: C++; indent-tabs-mode: nil; -*- alpar@385: * alpar@385: * This file is a part of LEMON, a generic C++ optimization library. alpar@385: * alpar@440: * Copyright (C) 2003-2009 alpar@385: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@385: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@385: * alpar@385: * Permission to use, modify and distribute this software is granted alpar@385: * provided that this copyright notice appears in all copies. For alpar@385: * precise terms see the accompanying LICENSE file. alpar@385: * alpar@385: * This software is provided "AS IS" with no warranty of any kind, alpar@385: * express or implied, and with no claim as to its suitability for any alpar@385: * purpose. alpar@385: * alpar@385: */ alpar@385: alpar@385: ///\ingroup tools alpar@385: ///\file kpeter@518: ///\brief DIMACS problem solver. alpar@385: /// kpeter@518: /// This program solves various problems given in DIMACS format. alpar@385: /// alpar@385: /// See alpar@385: /// \verbatim alpar@510: /// dimacs-solver --help alpar@385: /// \endverbatim alpar@385: /// for more info on usage. alpar@385: /// alpar@385: alpar@385: #include alpar@385: #include alpar@385: #include alpar@385: alpar@385: #include alpar@385: #include alpar@385: #include alpar@510: #include alpar@385: alpar@385: #include alpar@387: #include alpar@385: alpar@510: #include alpar@510: #include alpar@510: #include kpeter@594: #include alpar@510: alpar@385: using namespace lemon; alpar@510: typedef SmartDigraph Digraph; alpar@510: DIGRAPH_TYPEDEFS(Digraph); alpar@510: typedef SmartGraph Graph; alpar@385: alpar@510: template alpar@510: void solve_sp(ArgParser &ap, std::istream &is, std::ostream &, alpar@510: DimacsDescriptor &desc) alpar@510: { alpar@510: bool report = !ap.given("q"); alpar@510: Digraph g; alpar@510: Node s; alpar@510: Digraph::ArcMap len(g); alpar@510: Timer t; alpar@510: t.restart(); alpar@510: readDimacsSp(is, g, len, s, desc); alpar@510: if(report) std::cerr << "Read the file: " << t << '\n'; alpar@510: t.restart(); alpar@510: Dijkstra > dij(g,len); alpar@510: if(report) std::cerr << "Setup Dijkstra class: " << t << '\n'; alpar@510: t.restart(); alpar@510: dij.run(s); alpar@510: if(report) std::cerr << "Run Dijkstra: " << t << '\n'; alpar@510: } alpar@510: alpar@510: template alpar@510: void solve_max(ArgParser &ap, std::istream &is, std::ostream &, alpar@510: DimacsDescriptor &desc) alpar@510: { alpar@510: bool report = !ap.given("q"); alpar@510: Digraph g; alpar@510: Node s,t; alpar@510: Digraph::ArcMap cap(g); alpar@510: Timer ti; alpar@510: ti.restart(); alpar@510: readDimacsMax(is, g, cap, s, t, desc); alpar@510: if(report) std::cerr << "Read the file: " << ti << '\n'; alpar@510: ti.restart(); alpar@510: Preflow > pre(g,cap,s,t); alpar@510: if(report) std::cerr << "Setup Preflow class: " << ti << '\n'; alpar@510: ti.restart(); alpar@510: pre.run(); alpar@510: if(report) std::cerr << "Run Preflow: " << ti << '\n'; alpar@510: if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n'; alpar@510: } alpar@510: kpeter@594: template kpeter@594: void solve_min(ArgParser &ap, std::istream &is, std::ostream &, kpeter@594: DimacsDescriptor &desc) kpeter@594: { kpeter@594: bool report = !ap.given("q"); kpeter@594: Digraph g; kpeter@594: Digraph::ArcMap lower(g), cap(g), cost(g); kpeter@594: Digraph::NodeMap sup(g); kpeter@594: Timer ti; kpeter@594: ti.restart(); kpeter@594: readDimacsMin(is, g, lower, cap, cost, sup, desc); kpeter@594: if (report) std::cerr << "Read the file: " << ti << '\n'; kpeter@594: ti.restart(); kpeter@597: NetworkSimplex ns(g); kpeter@597: ns.lowerMap(lower).capacityMap(cap).costMap(cost).supplyMap(sup); kpeter@594: if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n'; kpeter@594: ti.restart(); kpeter@594: ns.run(); kpeter@594: if (report) std::cerr << "Run NetworkSimplex: " << ti << '\n'; kpeter@594: if (report) std::cerr << "\nMin flow cost: " << ns.totalCost() << '\n'; kpeter@594: } kpeter@594: alpar@510: void solve_mat(ArgParser &ap, std::istream &is, std::ostream &, alpar@510: DimacsDescriptor &desc) alpar@510: { alpar@510: bool report = !ap.given("q"); alpar@510: Graph g; alpar@510: Timer ti; alpar@510: ti.restart(); alpar@510: readDimacsMat(is, g, desc); alpar@510: if(report) std::cerr << "Read the file: " << ti << '\n'; alpar@510: ti.restart(); alpar@510: MaxMatching mat(g); alpar@510: if(report) std::cerr << "Setup MaxMatching class: " << ti << '\n'; alpar@510: ti.restart(); alpar@510: mat.run(); alpar@510: if(report) std::cerr << "Run MaxMatching: " << ti << '\n'; alpar@510: if(report) std::cerr << "\nCardinality of max matching: " alpar@510: << mat.matchingSize() << '\n'; alpar@510: } alpar@510: alpar@510: alpar@510: template alpar@510: void solve(ArgParser &ap, std::istream &is, std::ostream &os, alpar@510: DimacsDescriptor &desc) alpar@510: { alpar@510: switch(desc.type) alpar@510: { alpar@510: case DimacsDescriptor::MIN: kpeter@594: solve_min(ap,is,os,desc); alpar@510: break; alpar@510: case DimacsDescriptor::MAX: alpar@510: solve_max(ap,is,os,desc); alpar@510: break; alpar@510: case DimacsDescriptor::SP: alpar@510: solve_sp(ap,is,os,desc); alpar@510: break; alpar@510: case DimacsDescriptor::MAT: alpar@510: solve_mat(ap,is,os,desc); alpar@510: break; alpar@510: default: alpar@510: break; alpar@510: } alpar@510: } alpar@385: alpar@385: int main(int argc, const char *argv[]) { alpar@385: typedef SmartDigraph Digraph; alpar@385: alpar@385: typedef Digraph::Arc Arc; alpar@385: alpar@385: std::string inputName; alpar@385: std::string outputName; alpar@385: alpar@385: ArgParser ap(argc, argv); alpar@387: ap.other("[INFILE [OUTFILE]]", alpar@387: "If either the INFILE or OUTFILE file is missing the standard\n" alpar@387: " input/output will be used instead.") alpar@510: .boolOption("q", "Do not print any report") alpar@510: .boolOption("int","Use 'int' for capacities, costs etc. (default)") alpar@510: .optionGroup("datatype","int") alpar@510: #ifdef HAVE_LONG_LONG alpar@510: .boolOption("long","Use 'long long' for capacities, costs etc.") alpar@510: .optionGroup("datatype","long") alpar@510: #endif alpar@510: .boolOption("double","Use 'double' for capacities, costs etc.") alpar@510: .optionGroup("datatype","double") alpar@510: .boolOption("ldouble","Use 'long double' for capacities, costs etc.") alpar@510: .optionGroup("datatype","ldouble") alpar@510: .onlyOneGroup("datatype") alpar@385: .run(); alpar@385: alpar@510: std::ifstream input; alpar@510: std::ofstream output; alpar@387: alpar@387: switch(ap.files().size()) alpar@387: { alpar@387: case 2: alpar@387: output.open(ap.files()[1].c_str()); alpar@387: if (!output) { alpar@387: throw IoError("Cannot open the file for writing", ap.files()[1]); alpar@387: } alpar@387: case 1: alpar@387: input.open(ap.files()[0].c_str()); alpar@387: if (!input) { alpar@387: throw IoError("File cannot be found", ap.files()[0]); alpar@387: } alpar@387: case 0: alpar@387: break; alpar@387: default: alpar@510: std::cerr << ap.commandName() << ": too many arguments\n"; alpar@387: return 1; kpeter@518: } alpar@510: std::istream& is = (ap.files().size()<1 ? std::cin : input); alpar@510: std::ostream& os = (ap.files().size()<2 ? std::cout : output); alpar@387: alpar@387: DimacsDescriptor desc = dimacsType(is); alpar@510: alpar@510: if(!ap.given("q")) alpar@387: { alpar@510: std::cout << "Problem type: "; alpar@510: switch(desc.type) alpar@510: { alpar@510: case DimacsDescriptor::MIN: alpar@510: std::cout << "min"; alpar@510: break; alpar@510: case DimacsDescriptor::MAX: alpar@510: std::cout << "max"; alpar@510: break; alpar@510: case DimacsDescriptor::SP: alpar@510: std::cout << "sp"; alpar@510: case DimacsDescriptor::MAT: alpar@510: std::cout << "mat"; alpar@510: break; alpar@510: default: alpar@510: exit(1); alpar@510: break; alpar@510: } alpar@510: std::cout << "\nNum of nodes: " << desc.nodeNum; alpar@510: std::cout << "\nNum of arcs: " << desc.edgeNum; kpeter@518: std::cout << "\n\n"; alpar@385: } alpar@510: alpar@510: if(ap.given("double")) alpar@510: solve(ap,is,os,desc); alpar@510: else if(ap.given("ldouble")) alpar@510: solve(ap,is,os,desc); alpar@510: #ifdef HAVE_LONG_LONG alpar@510: else if(ap.given("long")) alpar@510: solve(ap,is,os,desc); alpar@510: #endif alpar@510: else solve(ap,is,os,desc); alpar@510: alpar@385: return 0; alpar@385: }