tools/dimacs-solver.cc
changeset 614 19b6f20e0ea2
parent 611 85cb3aa71cce
child 627 20dac2104519
child 640 6c408d864fa1
equal deleted inserted replaced
8:997fb113da93 9:38fc7b0f1a2a
    91   if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n';  
    91   if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n';  
    92 }
    92 }
    93 
    93 
    94 template<class Value>
    94 template<class Value>
    95 void solve_min(ArgParser &ap, std::istream &is, std::ostream &,
    95 void solve_min(ArgParser &ap, std::istream &is, std::ostream &,
    96                DimacsDescriptor &desc)
    96                Value infty, DimacsDescriptor &desc)
    97 {
    97 {
    98   bool report = !ap.given("q");
    98   bool report = !ap.given("q");
    99   Digraph g;
    99   Digraph g;
   100   Digraph::ArcMap<Value> lower(g), cap(g), cost(g);
   100   Digraph::ArcMap<Value> lower(g), cap(g), cost(g);
   101   Digraph::NodeMap<Value> sup(g);
   101   Digraph::NodeMap<Value> sup(g);
   102   Timer ti;
   102   Timer ti;
   103   ti.restart();
   103 
   104   readDimacsMin(is, g, lower, cap, cost, sup, 0, desc);
   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   }
   105   if (report) std::cerr << "Read the file: " << ti << '\n';
   118   if (report) std::cerr << "Read the file: " << ti << '\n';
       
   119 
   106   ti.restart();
   120   ti.restart();
   107   NetworkSimplex<Digraph, Value> ns(g);
   121   NetworkSimplex<Digraph, Value> ns(g);
   108   ns.lowerMap(lower).capacityMap(cap).costMap(cost).supplyMap(sup);
   122   ns.lowerMap(lower).capacityMap(cap).costMap(cost).supplyMap(sup);
       
   123   if (sum_sup > 0) ns.problemType(ns.LEQ);
   109   if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n';
   124   if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n';
   110   ti.restart();
   125   ti.restart();
   111   ns.run();
   126   bool res = ns.run();
   112   if (report) std::cerr << "Run NetworkSimplex: " << ti << '\n';
   127   if (report) {
   113   if (report) std::cerr << "\nMin flow cost: " << ns.totalCost() << '\n';
   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   }
   114 }
   132 }
   115 
   133 
   116 void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
   134 void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
   117               DimacsDescriptor &desc)
   135               DimacsDescriptor &desc)
   118 {
   136 {
   149     }
   167     }
   150   
   168   
   151   switch(desc.type)
   169   switch(desc.type)
   152     {
   170     {
   153     case DimacsDescriptor::MIN:
   171     case DimacsDescriptor::MIN:
   154       solve_min<Value>(ap,is,os,desc);
   172       solve_min<Value>(ap,is,os,infty,desc);
   155       break;
   173       break;
   156     case DimacsDescriptor::MAX:
   174     case DimacsDescriptor::MAX:
   157       solve_max<Value>(ap,is,os,infty,desc);
   175       solve_max<Value>(ap,is,os,infty,desc);
   158       break;
   176       break;
   159     case DimacsDescriptor::SP:
   177     case DimacsDescriptor::SP: