Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/extern/quadriflow/3rd/lemon-1.3.1/tools/dimacs-solver.cc
diff options
context:
space:
mode:
Diffstat (limited to 'extern/quadriflow/3rd/lemon-1.3.1/tools/dimacs-solver.cc')
-rw-r--r--extern/quadriflow/3rd/lemon-1.3.1/tools/dimacs-solver.cc279
1 files changed, 279 insertions, 0 deletions
diff --git a/extern/quadriflow/3rd/lemon-1.3.1/tools/dimacs-solver.cc b/extern/quadriflow/3rd/lemon-1.3.1/tools/dimacs-solver.cc
new file mode 100644
index 00000000000..60da2330e50
--- /dev/null
+++ b/extern/quadriflow/3rd/lemon-1.3.1/tools/dimacs-solver.cc
@@ -0,0 +1,279 @@
+/* -*- 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;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-21 00:51:55 +0300