COIN-OR::LEMON - Graph Library

Changeset 661:19b6f20e0ea2 in lemon for tools


Ignore:
Timestamp:
04/24/09 12:23:17 (16 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Support LEQ and GEQ supply constraints in dimacs-solver (#234, #219)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • tools/dimacs-solver.cc

    r658 r661  
    9494template<class Value>
    9595void solve_min(ArgParser &ap, std::istream &is, std::ostream &,
    96                DimacsDescriptor &desc)
     96               Value infty, DimacsDescriptor &desc)
    9797{
    9898  bool report = !ap.given("q");
     
    101101  Digraph::NodeMap<Value> sup(g);
    102102  Timer ti;
    103   ti.restart();
    104   readDimacsMin(is, g, lower, cap, cost, sup, 0, desc);
     103
     104  ti.restart();
     105  readDimacsMin(is, g, lower, cap, cost, sup, infty, desc);
     106  ti.stop();
     107  Value sum_sup = 0;
     108  for (Digraph::NodeIt n(g); n != INVALID; ++n) {
     109    sum_sup += sup[n];
     110  }
     111  if (report) {
     112    std::cerr << "Sum of supply values: " << sum_sup << "\n";
     113    if (sum_sup <= 0)
     114      std::cerr << "GEQ supply contraints are used for NetworkSimplex\n\n";
     115    else
     116      std::cerr << "LEQ supply contraints are used for NetworkSimplex\n\n";
     117  }
    105118  if (report) std::cerr << "Read the file: " << ti << '\n';
     119
    106120  ti.restart();
    107121  NetworkSimplex<Digraph, Value> ns(g);
    108122  ns.lowerMap(lower).capacityMap(cap).costMap(cost).supplyMap(sup);
     123  if (sum_sup > 0) ns.problemType(ns.LEQ);
    109124  if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n';
    110125  ti.restart();
    111   ns.run();
    112   if (report) std::cerr << "Run NetworkSimplex: " << ti << '\n';
    113   if (report) std::cerr << "\nMin flow cost: " << ns.totalCost() << '\n';
     126  bool res = ns.run();
     127  if (report) {
     128    std::cerr << "Run NetworkSimplex: " << ti << "\n\n";
     129    std::cerr << "Feasible flow: " << (res ? "found" : "not found") << '\n';
     130    if (res) std::cerr << "Min flow cost: " << ns.totalCost() << '\n';
     131  }
    114132}
    115133
     
    152170    {
    153171    case DimacsDescriptor::MIN:
    154       solve_min<Value>(ap,is,os,desc);
     172      solve_min<Value>(ap,is,os,infty,desc);
    155173      break;
    156174    case DimacsDescriptor::MAX:
Note: See TracChangeset for help on using the changeset viewer.