Changeset 658:85cb3aa71cce in lemon for tools/dimacs-solver.cc

Timestamp:

04/21/09 16:18:54 (15 years ago)

Author:

Alpar Juttner <alpar@…>

Branch:

default

Children:

659:0c8e5c688440, 660:b1811c363299, 666:ec817dfc2cb7

Parents:

647:0ba8dfce7259 (diff), 657:dacc2cee2b4c (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Phase:

public

Message:

Merge and fix

Files:

• tools/dimacs-solver.cc (modified) (3 diffs)
• tools/dimacs-solver.cc (modified) (8 diffs)

tools/dimacs-solver.cc

@@ -44 +44 @@
 #include <lemon/preflow.h>
 #include <lemon/matching.h>
+#include <lemon/network_simplex.h>
 
 using namespace lemon;
@@ -91 +92 @@
 }
 
+template<class Value>
+void solve_min(ArgParser &ap, std::istream &is, std::ostream &,
+               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, 0, desc);
+  if (report) std::cerr << "Read the file: " << ti << '\n';
+  ti.restart();
+  NetworkSimplex<Digraph, Value> ns(g);
+  ns.lowerMap(lower).capacityMap(cap).costMap(cost).supplyMap(sup);
+  if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n';
+  ti.restart();
+  ns.run();
+  if (report) std::cerr << "Run NetworkSimplex: " << ti << '\n';
+  if (report) std::cerr << "\nMin flow cost: " << ns.totalCost() << '\n';
+}
+
 void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
               DimacsDescriptor &desc)
@@ -129 +152 @@
     {
     case DimacsDescriptor::MIN:
-      std::cerr <<
-        "\n\n Sorry, the min. cost flow solver is not yet available.\n";
+      solve_min<Value>(ap,is,os,desc);
       break;
     case DimacsDescriptor::MAX:

tools/dimacs-solver.cc

@@ -24 +24 @@
 ///
 /// See
-/// \verbatim
-///  dimacs-solver --help
-/// \endverbatim
+/// \code
+///   dimacs-solver --help
+/// \endcode
 /// for more info on usage.
-///
 
 #include <iostream>
@@ -44 +43 @@
 #include <lemon/dijkstra.h>
 #include <lemon/preflow.h>
-#include <lemon/max_matching.h>
+#include <lemon/matching.h>
 #include <lemon/network_simplex.h>
 
@@ -74 +73 @@
 template<class Value>
 void solve_max(ArgParser &ap, std::istream &is, std::ostream &,
-              DimacsDescriptor &desc)
+               Value infty, DimacsDescriptor &desc)
 {
   bool report = !ap.given("q");
@@ -82 +81 @@
   Timer ti;
   ti.restart();
-  readDimacsMax(is, g, cap, s, t, desc);
+  readDimacsMax(is, g, cap, s, t, infty, desc);
   if(report) std::cerr << "Read the file: " << ti << '\n';
   ti.restart();
@@ -103 +102 @@
   Timer ti;
   ti.restart();
-  readDimacsMin(is, g, lower, cap, cost, sup, desc);
+  readDimacsMin(is, g, lower, cap, cost, sup, 0, desc);
   if (report) std::cerr << "Read the file: " << ti << '\n';
   ti.restart();
@@ -139 +138 @@
            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)
     {
@@ -145 +155 @@
       break;
     case DimacsDescriptor::MAX:
-      solve_max<Value>(ap,is,os,desc);
+      solve_max<Value>(ap,is,os,infty,desc);
       break;
     case DimacsDescriptor::SP:
@@ -182 +192 @@
     .optionGroup("datatype","ldouble")
     .onlyOneGroup("datatype")
+    .stringOption("infcap","Value used for 'very high' capacities","0")
     .run();