alpar@400: /* -*- mode: C++; indent-tabs-mode: nil; -*- alpar@400: * alpar@400: * This file is a part of LEMON, a generic C++ optimization library. alpar@400: * alpar@1270: * Copyright (C) 2003-2013 alpar@400: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@400: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@400: * alpar@400: * Permission to use, modify and distribute this software is granted alpar@400: * provided that this copyright notice appears in all copies. For alpar@400: * precise terms see the accompanying LICENSE file. alpar@400: * alpar@400: * This software is provided "AS IS" with no warranty of any kind, alpar@400: * express or implied, and with no claim as to its suitability for any alpar@400: * purpose. alpar@400: * alpar@400: */ alpar@400: alpar@400: ///\ingroup tools alpar@400: ///\file kpeter@579: ///\brief DIMACS problem solver. alpar@400: /// kpeter@579: /// This program solves various problems given in DIMACS format. alpar@400: /// alpar@400: /// See kpeter@631: /// \code kpeter@631: /// dimacs-solver --help kpeter@631: /// \endcode alpar@400: /// for more info on usage. alpar@400: alpar@400: #include alpar@400: #include alpar@400: #include alpar@400: alpar@400: #include alpar@400: #include alpar@400: #include alpar@573: #include alpar@400: alpar@400: #include alpar@402: #include alpar@400: alpar@573: #include alpar@573: #include kpeter@641: #include kpeter@649: #include alpar@573: alpar@400: using namespace lemon; alpar@573: typedef SmartDigraph Digraph; alpar@573: DIGRAPH_TYPEDEFS(Digraph); alpar@573: typedef SmartGraph Graph; alpar@400: alpar@573: template alpar@573: void solve_sp(ArgParser &ap, std::istream &is, std::ostream &, alpar@573: DimacsDescriptor &desc) alpar@573: { alpar@573: bool report = !ap.given("q"); alpar@573: Digraph g; alpar@573: Node s; alpar@573: Digraph::ArcMap len(g); alpar@573: Timer t; alpar@573: t.restart(); alpar@573: readDimacsSp(is, g, len, s, desc); alpar@573: if(report) std::cerr << "Read the file: " << t << '\n'; alpar@573: t.restart(); alpar@573: Dijkstra > dij(g,len); alpar@573: if(report) std::cerr << "Setup Dijkstra class: " << t << '\n'; alpar@573: t.restart(); alpar@573: dij.run(s); alpar@573: if(report) std::cerr << "Run Dijkstra: " << t << '\n'; alpar@573: } alpar@573: alpar@573: template alpar@573: void solve_max(ArgParser &ap, std::istream &is, std::ostream &, alpar@608: Value infty, DimacsDescriptor &desc) alpar@573: { alpar@573: bool report = !ap.given("q"); alpar@573: Digraph g; alpar@573: Node s,t; alpar@573: Digraph::ArcMap cap(g); alpar@573: Timer ti; alpar@573: ti.restart(); alpar@608: readDimacsMax(is, g, cap, s, t, infty, desc); alpar@573: if(report) std::cerr << "Read the file: " << ti << '\n'; alpar@573: ti.restart(); alpar@573: Preflow > pre(g,cap,s,t); alpar@573: if(report) std::cerr << "Setup Preflow class: " << ti << '\n'; alpar@573: ti.restart(); alpar@573: pre.run(); alpar@573: if(report) std::cerr << "Run Preflow: " << ti << '\n'; alpar@956: if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n'; alpar@573: } alpar@573: kpeter@919: template kpeter@649: void solve_min(ArgParser &ap, std::istream &is, std::ostream &, kpeter@661: Value infty, DimacsDescriptor &desc) kpeter@649: { kpeter@649: bool report = !ap.given("q"); kpeter@649: Digraph g; kpeter@649: Digraph::ArcMap lower(g), cap(g), cost(g); kpeter@649: Digraph::NodeMap sup(g); kpeter@649: Timer ti; kpeter@661: kpeter@649: ti.restart(); kpeter@661: readDimacsMin(is, g, lower, cap, cost, sup, infty, desc); kpeter@661: ti.stop(); kpeter@661: Value sum_sup = 0; kpeter@661: for (Digraph::NodeIt n(g); n != INVALID; ++n) { kpeter@661: sum_sup += sup[n]; kpeter@661: } kpeter@661: if (report) { kpeter@661: std::cerr << "Sum of supply values: " << sum_sup << "\n"; kpeter@661: if (sum_sup <= 0) kpeter@661: std::cerr << "GEQ supply contraints are used for NetworkSimplex\n\n"; kpeter@661: else kpeter@661: std::cerr << "LEQ supply contraints are used for NetworkSimplex\n\n"; kpeter@661: } kpeter@649: if (report) std::cerr << "Read the file: " << ti << '\n'; kpeter@661: kpeter@1167: typedef NetworkSimplex MCF; kpeter@649: ti.restart(); kpeter@1167: MCF ns(g); kpeter@687: ns.lowerMap(lower).upperMap(cap).costMap(cost).supplyMap(sup); kpeter@687: if (sum_sup > 0) ns.supplyType(ns.LEQ); kpeter@649: if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n'; kpeter@649: ti.restart(); kpeter@1167: typename MCF::ProblemType res = ns.run(); kpeter@661: if (report) { kpeter@661: std::cerr << "Run NetworkSimplex: " << ti << "\n\n"; alpar@1271: std::cerr << "Feasible flow: " << (res == MCF::OPTIMAL ? "found" : alpar@1271: "not found") << '\n'; kpeter@919: if (res) std::cerr << "Min flow cost: " kpeter@919: << ns.template totalCost() << '\n'; kpeter@661: } kpeter@649: } kpeter@649: alpar@573: void solve_mat(ArgParser &ap, std::istream &is, std::ostream &, alpar@573: DimacsDescriptor &desc) alpar@573: { alpar@573: bool report = !ap.given("q"); alpar@573: Graph g; alpar@573: Timer ti; alpar@573: ti.restart(); alpar@573: readDimacsMat(is, g, desc); alpar@573: if(report) std::cerr << "Read the file: " << ti << '\n'; alpar@573: ti.restart(); alpar@573: MaxMatching mat(g); alpar@573: if(report) std::cerr << "Setup MaxMatching class: " << ti << '\n'; alpar@573: ti.restart(); alpar@573: mat.run(); alpar@573: if(report) std::cerr << "Run MaxMatching: " << ti << '\n'; alpar@573: if(report) std::cerr << "\nCardinality of max matching: " alpar@956: << mat.matchingSize() << '\n'; alpar@573: } alpar@573: alpar@573: kpeter@919: template alpar@573: void solve(ArgParser &ap, std::istream &is, std::ostream &os, alpar@573: DimacsDescriptor &desc) alpar@573: { ladanyi@616: std::stringstream iss(static_cast(ap["infcap"])); alpar@608: Value infty; alpar@608: iss >> infty; alpar@608: if(iss.fail()) alpar@608: { alpar@608: std::cerr << "Cannot interpret '" alpar@608: << static_cast(ap["infcap"]) << "' as infinite" alpar@608: << std::endl; alpar@608: exit(1); alpar@608: } alpar@956: alpar@573: switch(desc.type) alpar@573: { alpar@573: case DimacsDescriptor::MIN: kpeter@919: solve_min(ap,is,os,infty,desc); alpar@573: break; alpar@573: case DimacsDescriptor::MAX: alpar@608: solve_max(ap,is,os,infty,desc); alpar@573: break; alpar@573: case DimacsDescriptor::SP: alpar@573: solve_sp(ap,is,os,desc); alpar@573: break; alpar@573: case DimacsDescriptor::MAT: alpar@573: solve_mat(ap,is,os,desc); alpar@573: break; alpar@573: default: alpar@573: break; alpar@573: } alpar@573: } alpar@400: alpar@400: int main(int argc, const char *argv[]) { alpar@400: alpar@400: std::string inputName; alpar@400: std::string outputName; alpar@400: alpar@400: ArgParser ap(argc, argv); alpar@402: ap.other("[INFILE [OUTFILE]]", alpar@402: "If either the INFILE or OUTFILE file is missing the standard\n" alpar@402: " input/output will be used instead.") alpar@573: .boolOption("q", "Do not print any report") alpar@573: .boolOption("int","Use 'int' for capacities, costs etc. (default)") alpar@573: .optionGroup("datatype","int") ladanyi@674: #ifdef LEMON_HAVE_LONG_LONG alpar@573: .boolOption("long","Use 'long long' for capacities, costs etc.") alpar@573: .optionGroup("datatype","long") alpar@573: #endif alpar@573: .boolOption("double","Use 'double' for capacities, costs etc.") alpar@573: .optionGroup("datatype","double") alpar@573: .boolOption("ldouble","Use 'long double' for capacities, costs etc.") alpar@573: .optionGroup("datatype","ldouble") alpar@573: .onlyOneGroup("datatype") alpar@608: .stringOption("infcap","Value used for 'very high' capacities","0") alpar@400: .run(); alpar@400: alpar@573: std::ifstream input; alpar@573: std::ofstream output; alpar@402: alpar@402: switch(ap.files().size()) alpar@402: { alpar@402: case 2: alpar@402: output.open(ap.files()[1].c_str()); alpar@402: if (!output) { alpar@402: throw IoError("Cannot open the file for writing", ap.files()[1]); alpar@402: } kpeter@1386: // fall through alpar@402: case 1: alpar@402: input.open(ap.files()[0].c_str()); alpar@402: if (!input) { alpar@402: throw IoError("File cannot be found", ap.files()[0]); alpar@402: } kpeter@1386: // fall through alpar@402: case 0: alpar@402: break; alpar@402: default: alpar@573: std::cerr << ap.commandName() << ": too many arguments\n"; alpar@402: return 1; kpeter@579: } alpar@573: std::istream& is = (ap.files().size()<1 ? std::cin : input); alpar@573: std::ostream& os = (ap.files().size()<2 ? std::cout : output); alpar@402: alpar@402: DimacsDescriptor desc = dimacsType(is); alpar@956: alpar@573: if(!ap.given("q")) alpar@402: { alpar@573: std::cout << "Problem type: "; alpar@573: switch(desc.type) alpar@573: { alpar@573: case DimacsDescriptor::MIN: alpar@573: std::cout << "min"; alpar@573: break; alpar@573: case DimacsDescriptor::MAX: alpar@573: std::cout << "max"; alpar@573: break; alpar@573: case DimacsDescriptor::SP: alpar@573: std::cout << "sp"; kpeter@1386: break; alpar@573: case DimacsDescriptor::MAT: alpar@573: std::cout << "mat"; alpar@573: break; alpar@573: default: alpar@573: exit(1); alpar@573: break; alpar@573: } alpar@573: std::cout << "\nNum of nodes: " << desc.nodeNum; alpar@573: std::cout << "\nNum of arcs: " << desc.edgeNum; kpeter@579: std::cout << "\n\n"; alpar@400: } alpar@956: alpar@573: if(ap.given("double")) kpeter@919: solve(ap,is,os,desc); alpar@573: else if(ap.given("ldouble")) kpeter@919: solve(ap,is,os,desc); ladanyi@674: #ifdef LEMON_HAVE_LONG_LONG alpar@573: else if(ap.given("long")) kpeter@919: solve(ap,is,os,desc); kpeter@919: else solve(ap,is,os,desc); kpeter@919: #else kpeter@919: else solve(ap,is,os,desc); alpar@573: #endif alpar@573: alpar@400: return 0; alpar@400: }