Page MenuHome
Differential D5594 Diff 18104 extern/quadriflow/3rd/lemon-1.3.1/tools/dimacs-solver.cc

Changeset View

Standalone View

View Options

extern/quadriflow/3rd/lemon-1.3.1/tools/dimacs-solver.cc

  • This file was added.
/* -*- mode: C++; indent-tabs-mode: nil; -*-
*
* This file is a part of LEMON, a generic C++ optimization library.
*
* Copyright (C) 2003-2013
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
*
* Permission to use, modify and distribute this software is granted
* provided that this copyright notice appears in all copies. For
* precise terms see the accompanying LICENSE file.
*
* This software is provided "AS IS" with no warranty of any kind,
* express or implied, and with no claim as to its suitability for any
* purpose.
*
*/
///\ingroup tools
///\file
///\brief DIMACS problem solver.
///
/// This program solves various problems given in DIMACS format.
///
/// See
/// \code
/// dimacs-solver --help
/// \endcode
/// for more info on usage.
#include <iostream>
#include <fstream>
#include <cstring>
#include <lemon/smart_graph.h>
#include <lemon/dimacs.h>
#include <lemon/lgf_writer.h>
#include <lemon/time_measure.h>
#include <lemon/arg_parser.h>
#include <lemon/error.h>
#include <lemon/dijkstra.h>
#include <lemon/preflow.h>
#include <lemon/matching.h>
#include <lemon/network_simplex.h>
using namespace lemon;
typedef SmartDigraph Digraph;
DIGRAPH_TYPEDEFS(Digraph);
typedef SmartGraph Graph;
template<class Value>
void solve_sp(ArgParser &ap, std::istream &is, std::ostream &,
DimacsDescriptor &desc)
{
bool report = !ap.given("q");
Digraph g;
Node s;
Digraph::ArcMap<Value> len(g);
Timer t;
t.restart();
readDimacsSp(is, g, len, s, desc);
if(report) std::cerr << "Read the file: " << t << '\n';
t.restart();
Dijkstra<Digraph, Digraph::ArcMap<Value> > 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<class Value>
void solve_max(ArgParser &ap, std::istream &is, std::ostream &,
Value infty, DimacsDescriptor &desc)
{
bool report = !ap.given("q");
Digraph g;
Node s,t;
Digraph::ArcMap<Value> cap(g);
Timer ti;
ti.restart();
readDimacsMax(is, g, cap, s, t, infty, desc);
if(report) std::cerr << "Read the file: " << ti << '\n';
ti.restart();
Preflow<Digraph, Digraph::ArcMap<Value> > 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';
}
template<class Value, class LargeValue>
void solve_min(ArgParser &ap, std::istream &is, std::ostream &,
Value infty, DimacsDescriptor &desc)
{
bool report = !ap.given("q");
Digraph g;
Digraph::ArcMap<Value> lower(g), cap(g), cost(g);
Digraph::NodeMap<Value> sup(g);
Timer ti;
ti.restart();
readDimacsMin(is, g, lower, cap, cost, sup, infty, desc);
ti.stop();
Value sum_sup = 0;
for (Digraph::NodeIt n(g); n != INVALID; ++n) {
sum_sup += sup[n];
}
if (report) {
std::cerr << "Sum of supply values: " << sum_sup << "\n";
if (sum_sup <= 0)
std::cerr << "GEQ supply contraints are used for NetworkSimplex\n\n";
else
std::cerr << "LEQ supply contraints are used for NetworkSimplex\n\n";
}
if (report) std::cerr << "Read the file: " << ti << '\n';
typedef NetworkSimplex<Digraph, Value> MCF;
ti.restart();
MCF ns(g);
ns.lowerMap(lower).upperMap(cap).costMap(cost).supplyMap(sup);
if (sum_sup > 0) ns.supplyType(ns.LEQ);
if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n';
ti.restart();
typename MCF::ProblemType res = ns.run();
if (report) {
std::cerr << "Run NetworkSimplex: " << ti << "\n\n";
std::cerr << "Feasible flow: " << (res == MCF::OPTIMAL ? "found" :
"not found") << '\n';
if (res) std::cerr << "Min flow cost: "
<< ns.template totalCost<LargeValue>() << '\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<Graph> 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<class Value, class LargeValue>
void solve(ArgParser &ap, std::istream &is, std::ostream &os,
DimacsDescriptor &desc)
{
std::stringstream iss(static_cast<std::string>(ap["infcap"]));
Value infty;
iss >> infty;
if(iss.fail())
{
std::cerr << "Cannot interpret '"
<< static_cast<std::string>(ap["infcap"]) << "' as infinite"
<< std::endl;
exit(1);
}
switch(desc.type)
{
case DimacsDescriptor::MIN:
solve_min<Value, LargeValue>(ap,is,os,infty,desc);
break;
case DimacsDescriptor::MAX:
solve_max<Value>(ap,is,os,infty,desc);
break;
case DimacsDescriptor::SP:
solve_sp<Value>(ap,is,os,desc);
break;
case DimacsDescriptor::MAT:
solve_mat(ap,is,os,desc);
break;
default:
break;
}
}
int main(int argc, const char *argv[]) {
std::string inputName;
std::string outputName;
ArgParser ap(argc, argv);
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 LEMON_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")
.stringOption("infcap","Value used for 'very high' capacities","0")
.run();
std::ifstream input;
std::ofstream output;
switch(ap.files().size())
{
case 2:
output.open(ap.files()[1].c_str());
if (!output) {
throw IoError("Cannot open the file for writing", ap.files()[1]);
}
case 1:
input.open(ap.files()[0].c_str());
if (!input) {
throw IoError("File cannot be found", ap.files()[0]);
}
case 0:
break;
default:
std::cerr << ap.commandName() << ": too many arguments\n";
return 1;
}
std::istream& is = (ap.files().size()<1 ? std::cin : input);
std::ostream& os = (ap.files().size()<2 ? std::cout : output);
DimacsDescriptor desc = dimacsType(is);
if(!ap.given("q"))
{
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\n";
}
if(ap.given("double"))
solve<double, double>(ap,is,os,desc);
else if(ap.given("ldouble"))
solve<long double, long double>(ap,is,os,desc);
#ifdef LEMON_HAVE_LONG_LONG
else if(ap.given("long"))
solve<long long, long long>(ap,is,os,desc);
else solve<int, long long>(ap,is,os,desc);
#else
else solve<int, long>(ap,is,os,desc);
#endif
return 0;
}