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@877: * Copyright (C) 2003-2010 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@532: ///\brief DIMACS problem solver. alpar@385: /// kpeter@532: /// This program solves various problems given in DIMACS format. alpar@385: /// alpar@385: /// See kpeter@584: /// \code kpeter@584: /// dimacs-solver --help kpeter@584: /// \endcode alpar@385: /// for more info on usage. alpar@385: alpar@385: #include alpar@385: #include alpar@385: #include alpar@385: alpar@385: #include alpar@385: #include alpar@385: #include alpar@526: #include alpar@385: alpar@385: #include alpar@387: #include alpar@385: alpar@526: #include alpar@526: #include kpeter@594: #include kpeter@602: #include alpar@526: alpar@385: using namespace lemon; alpar@526: typedef SmartDigraph Digraph; alpar@526: DIGRAPH_TYPEDEFS(Digraph); alpar@526: typedef SmartGraph Graph; alpar@385: alpar@526: template alpar@526: void solve_sp(ArgParser &ap, std::istream &is, std::ostream &, alpar@526: DimacsDescriptor &desc) alpar@526: { alpar@526: bool report = !ap.given("q"); alpar@526: Digraph g; alpar@526: Node s; alpar@526: Digraph::ArcMap len(g); alpar@526: Timer t; alpar@526: t.restart(); alpar@526: readDimacsSp(is, g, len, s, desc); alpar@526: if(report) std::cerr << "Read the file: " << t << '\n'; alpar@526: t.restart(); alpar@526: Dijkstra > dij(g,len); alpar@526: if(report) std::cerr << "Setup Dijkstra class: " << t << '\n'; alpar@526: t.restart(); alpar@526: dij.run(s); alpar@526: if(report) std::cerr << "Run Dijkstra: " << t << '\n'; alpar@526: } alpar@526: alpar@526: template alpar@526: void solve_max(ArgParser &ap, std::istream &is, std::ostream &, alpar@561: Value infty, DimacsDescriptor &desc) alpar@526: { alpar@526: bool report = !ap.given("q"); alpar@526: Digraph g; alpar@526: Node s,t; alpar@526: Digraph::ArcMap cap(g); alpar@526: Timer ti; alpar@526: ti.restart(); alpar@561: readDimacsMax(is, g, cap, s, t, infty, desc); alpar@526: if(report) std::cerr << "Read the file: " << ti << '\n'; alpar@526: ti.restart(); alpar@526: Preflow > pre(g,cap,s,t); alpar@526: if(report) std::cerr << "Setup Preflow class: " << ti << '\n'; alpar@526: ti.restart(); alpar@526: pre.run(); alpar@526: if(report) std::cerr << "Run Preflow: " << ti << '\n'; alpar@877: if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n'; alpar@526: } alpar@526: kpeter@846: template kpeter@602: void solve_min(ArgParser &ap, std::istream &is, std::ostream &, kpeter@614: Value infty, DimacsDescriptor &desc) kpeter@602: { kpeter@602: bool report = !ap.given("q"); kpeter@602: Digraph g; kpeter@602: Digraph::ArcMap lower(g), cap(g), cost(g); kpeter@602: Digraph::NodeMap sup(g); kpeter@602: Timer ti; kpeter@614: kpeter@602: ti.restart(); kpeter@614: readDimacsMin(is, g, lower, cap, cost, sup, infty, desc); kpeter@614: ti.stop(); kpeter@614: Value sum_sup = 0; kpeter@614: for (Digraph::NodeIt n(g); n != INVALID; ++n) { kpeter@614: sum_sup += sup[n]; kpeter@614: } kpeter@614: if (report) { kpeter@614: std::cerr << "Sum of supply values: " << sum_sup << "\n"; kpeter@614: if (sum_sup <= 0) kpeter@614: std::cerr << "GEQ supply contraints are used for NetworkSimplex\n\n"; kpeter@614: else kpeter@614: std::cerr << "LEQ supply contraints are used for NetworkSimplex\n\n"; kpeter@614: } kpeter@602: if (report) std::cerr << "Read the file: " << ti << '\n'; kpeter@614: kpeter@967: typedef NetworkSimplex MCF; kpeter@602: ti.restart(); kpeter@967: MCF ns(g); kpeter@640: ns.lowerMap(lower).upperMap(cap).costMap(cost).supplyMap(sup); kpeter@640: if (sum_sup > 0) ns.supplyType(ns.LEQ); kpeter@602: if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n'; kpeter@602: ti.restart(); kpeter@967: typename MCF::ProblemType res = ns.run(); kpeter@614: if (report) { kpeter@614: std::cerr << "Run NetworkSimplex: " << ti << "\n\n"; kpeter@967: std::cerr << "Feasible flow: " << (res == MCF::OPTIMAL ? "found" : "not found") << '\n'; kpeter@846: if (res) std::cerr << "Min flow cost: " kpeter@846: << ns.template totalCost() << '\n'; kpeter@614: } kpeter@602: } kpeter@602: alpar@526: void solve_mat(ArgParser &ap, std::istream &is, std::ostream &, alpar@526: DimacsDescriptor &desc) alpar@526: { alpar@526: bool report = !ap.given("q"); alpar@526: Graph g; alpar@526: Timer ti; alpar@526: ti.restart(); alpar@526: readDimacsMat(is, g, desc); alpar@526: if(report) std::cerr << "Read the file: " << ti << '\n'; alpar@526: ti.restart(); alpar@526: MaxMatching mat(g); alpar@526: if(report) std::cerr << "Setup MaxMatching class: " << ti << '\n'; alpar@526: ti.restart(); alpar@526: mat.run(); alpar@526: if(report) std::cerr << "Run MaxMatching: " << ti << '\n'; alpar@526: if(report) std::cerr << "\nCardinality of max matching: " alpar@877: << mat.matchingSize() << '\n'; alpar@526: } alpar@526: alpar@526: kpeter@846: template alpar@526: void solve(ArgParser &ap, std::istream &is, std::ostream &os, alpar@526: DimacsDescriptor &desc) alpar@526: { ladanyi@569: std::stringstream iss(static_cast(ap["infcap"])); alpar@561: Value infty; alpar@561: iss >> infty; alpar@561: if(iss.fail()) alpar@561: { alpar@561: std::cerr << "Cannot interpret '" alpar@561: << static_cast(ap["infcap"]) << "' as infinite" alpar@561: << std::endl; alpar@561: exit(1); alpar@561: } alpar@877: alpar@526: switch(desc.type) alpar@526: { alpar@526: case DimacsDescriptor::MIN: kpeter@846: solve_min(ap,is,os,infty,desc); alpar@526: break; alpar@526: case DimacsDescriptor::MAX: alpar@561: solve_max(ap,is,os,infty,desc); alpar@526: break; alpar@526: case DimacsDescriptor::SP: alpar@526: solve_sp(ap,is,os,desc); alpar@526: break; alpar@526: case DimacsDescriptor::MAT: alpar@526: solve_mat(ap,is,os,desc); alpar@526: break; alpar@526: default: alpar@526: break; alpar@526: } alpar@526: } alpar@385: alpar@385: int main(int argc, const char *argv[]) { 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@526: .boolOption("q", "Do not print any report") alpar@526: .boolOption("int","Use 'int' for capacities, costs etc. (default)") alpar@526: .optionGroup("datatype","int") ladanyi@627: #ifdef LEMON_HAVE_LONG_LONG alpar@526: .boolOption("long","Use 'long long' for capacities, costs etc.") alpar@526: .optionGroup("datatype","long") alpar@526: #endif alpar@526: .boolOption("double","Use 'double' for capacities, costs etc.") alpar@526: .optionGroup("datatype","double") alpar@526: .boolOption("ldouble","Use 'long double' for capacities, costs etc.") alpar@526: .optionGroup("datatype","ldouble") alpar@526: .onlyOneGroup("datatype") alpar@561: .stringOption("infcap","Value used for 'very high' capacities","0") alpar@385: .run(); alpar@385: alpar@526: std::ifstream input; alpar@526: 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@526: std::cerr << ap.commandName() << ": too many arguments\n"; alpar@387: return 1; kpeter@532: } alpar@526: std::istream& is = (ap.files().size()<1 ? std::cin : input); alpar@526: std::ostream& os = (ap.files().size()<2 ? std::cout : output); alpar@387: alpar@387: DimacsDescriptor desc = dimacsType(is); alpar@877: alpar@526: if(!ap.given("q")) alpar@387: { alpar@526: std::cout << "Problem type: "; alpar@526: switch(desc.type) alpar@526: { alpar@526: case DimacsDescriptor::MIN: alpar@526: std::cout << "min"; alpar@526: break; alpar@526: case DimacsDescriptor::MAX: alpar@526: std::cout << "max"; alpar@526: break; alpar@526: case DimacsDescriptor::SP: alpar@526: std::cout << "sp"; alpar@526: case DimacsDescriptor::MAT: alpar@526: std::cout << "mat"; alpar@526: break; alpar@526: default: alpar@526: exit(1); alpar@526: break; alpar@526: } alpar@526: std::cout << "\nNum of nodes: " << desc.nodeNum; alpar@526: std::cout << "\nNum of arcs: " << desc.edgeNum; kpeter@532: std::cout << "\n\n"; alpar@385: } alpar@877: alpar@526: if(ap.given("double")) kpeter@846: solve(ap,is,os,desc); alpar@526: else if(ap.given("ldouble")) kpeter@846: solve(ap,is,os,desc); ladanyi@627: #ifdef LEMON_HAVE_LONG_LONG alpar@526: else if(ap.given("long")) kpeter@846: solve(ap,is,os,desc); kpeter@846: else solve(ap,is,os,desc); kpeter@846: #else kpeter@846: else solve(ap,is,os,desc); alpar@526: #endif alpar@526: alpar@385: return 0; alpar@385: }