Support LEQ and GEQ supply constraints in dimacs-solver (#234, #219)
authorPeter Kovacs <kpeter@inf.elte.hu>
Fri, 24 Apr 2009 12:23:17 +0200
changeset 66119b6f20e0ea2
parent 660 b1811c363299
child 662 e3d9bff447ed
Support LEQ and GEQ supply constraints in dimacs-solver (#234, #219)
tools/dimacs-solver.cc
     1.1 --- a/tools/dimacs-solver.cc	Fri Apr 24 12:22:06 2009 +0200
     1.2 +++ b/tools/dimacs-solver.cc	Fri Apr 24 12:23:17 2009 +0200
     1.3 @@ -93,24 +93,42 @@
     1.4  
     1.5  template<class Value>
     1.6  void solve_min(ArgParser &ap, std::istream &is, std::ostream &,
     1.7 -               DimacsDescriptor &desc)
     1.8 +               Value infty, DimacsDescriptor &desc)
     1.9  {
    1.10    bool report = !ap.given("q");
    1.11    Digraph g;
    1.12    Digraph::ArcMap<Value> lower(g), cap(g), cost(g);
    1.13    Digraph::NodeMap<Value> sup(g);
    1.14    Timer ti;
    1.15 +
    1.16    ti.restart();
    1.17 -  readDimacsMin(is, g, lower, cap, cost, sup, 0, desc);
    1.18 +  readDimacsMin(is, g, lower, cap, cost, sup, infty, desc);
    1.19 +  ti.stop();
    1.20 +  Value sum_sup = 0;
    1.21 +  for (Digraph::NodeIt n(g); n != INVALID; ++n) {
    1.22 +    sum_sup += sup[n];
    1.23 +  }
    1.24 +  if (report) {
    1.25 +    std::cerr << "Sum of supply values: " << sum_sup << "\n";
    1.26 +    if (sum_sup <= 0)
    1.27 +      std::cerr << "GEQ supply contraints are used for NetworkSimplex\n\n";
    1.28 +    else
    1.29 +      std::cerr << "LEQ supply contraints are used for NetworkSimplex\n\n";
    1.30 +  }
    1.31    if (report) std::cerr << "Read the file: " << ti << '\n';
    1.32 +
    1.33    ti.restart();
    1.34    NetworkSimplex<Digraph, Value> ns(g);
    1.35    ns.lowerMap(lower).capacityMap(cap).costMap(cost).supplyMap(sup);
    1.36 +  if (sum_sup > 0) ns.problemType(ns.LEQ);
    1.37    if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n';
    1.38    ti.restart();
    1.39 -  ns.run();
    1.40 -  if (report) std::cerr << "Run NetworkSimplex: " << ti << '\n';
    1.41 -  if (report) std::cerr << "\nMin flow cost: " << ns.totalCost() << '\n';
    1.42 +  bool res = ns.run();
    1.43 +  if (report) {
    1.44 +    std::cerr << "Run NetworkSimplex: " << ti << "\n\n";
    1.45 +    std::cerr << "Feasible flow: " << (res ? "found" : "not found") << '\n';
    1.46 +    if (res) std::cerr << "Min flow cost: " << ns.totalCost() << '\n';
    1.47 +  }
    1.48  }
    1.49  
    1.50  void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
    1.51 @@ -151,7 +169,7 @@
    1.52    switch(desc.type)
    1.53      {
    1.54      case DimacsDescriptor::MIN:
    1.55 -      solve_min<Value>(ap,is,os,desc);
    1.56 +      solve_min<Value>(ap,is,os,infty,desc);
    1.57        break;
    1.58      case DimacsDescriptor::MAX:
    1.59        solve_max<Value>(ap,is,os,infty,desc);