Support min cost flow in dimacs-solver (#234)
authorPeter Kovacs <kpeter@inf.elte.hu>
Tue, 24 Feb 2009 09:52:26 +0100
changeset 594a79ef774fae1
parent 593 e8349c6f12ca
child 595 425cc8328c0e
Support min cost flow in dimacs-solver (#234)
tools/dimacs-solver.cc
     1.1 --- a/tools/dimacs-solver.cc	Tue Feb 24 09:46:02 2009 +0100
     1.2 +++ b/tools/dimacs-solver.cc	Tue Feb 24 09:52:26 2009 +0100
     1.3 @@ -44,6 +44,7 @@
     1.4  #include <lemon/dijkstra.h>
     1.5  #include <lemon/preflow.h>
     1.6  #include <lemon/max_matching.h>
     1.7 +#include <lemon/network_simplex.h>
     1.8  
     1.9  using namespace lemon;
    1.10  typedef SmartDigraph Digraph;
    1.11 @@ -91,6 +92,29 @@
    1.12    if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n';  
    1.13  }
    1.14  
    1.15 +template<class Value>
    1.16 +void solve_min(ArgParser &ap, std::istream &is, std::ostream &,
    1.17 +               DimacsDescriptor &desc)
    1.18 +{
    1.19 +  bool report = !ap.given("q");
    1.20 +  Digraph g;
    1.21 +  Digraph::ArcMap<Value> lower(g), cap(g), cost(g);
    1.22 +  Digraph::NodeMap<Value> sup(g);
    1.23 +  Timer ti;
    1.24 +  ti.restart();
    1.25 +  readDimacsMin(is, g, lower, cap, cost, sup, desc);
    1.26 +  if (report) std::cerr << "Read the file: " << ti << '\n';
    1.27 +  ti.restart();
    1.28 +  NetworkSimplex< Digraph, Digraph::ArcMap<Value>, Digraph::ArcMap<Value>,
    1.29 +                  Digraph::ArcMap<Value>, Digraph::NodeMap<Value> >
    1.30 +    ns(g, lower, cap, cost, sup);
    1.31 +  if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n';
    1.32 +  ti.restart();
    1.33 +  ns.run();
    1.34 +  if (report) std::cerr << "Run NetworkSimplex: " << ti << '\n';
    1.35 +  if (report) std::cerr << "\nMin flow cost: " << ns.totalCost() << '\n';
    1.36 +}
    1.37 +
    1.38  void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
    1.39                DimacsDescriptor &desc)
    1.40  {
    1.41 @@ -118,8 +142,7 @@
    1.42    switch(desc.type)
    1.43      {
    1.44      case DimacsDescriptor::MIN:
    1.45 -      std::cerr <<
    1.46 -        "\n\n Sorry, the min. cost flow solver is not yet available.\n";
    1.47 +      solve_min<Value>(ap,is,os,desc);
    1.48        break;
    1.49      case DimacsDescriptor::MAX:
    1.50        solve_max<Value>(ap,is,os,desc);