tools/dimacs-solver.cc
changeset 658 85cb3aa71cce
parent 641 d657c71db7db
parent 652 5232721b3f14
child 661 19b6f20e0ea2
equal deleted inserted replaced
5:5f41d8241315 8:997fb113da93
    41 #include <lemon/error.h>
    41 #include <lemon/error.h>
    42 
    42 
    43 #include <lemon/dijkstra.h>
    43 #include <lemon/dijkstra.h>
    44 #include <lemon/preflow.h>
    44 #include <lemon/preflow.h>
    45 #include <lemon/matching.h>
    45 #include <lemon/matching.h>
       
    46 #include <lemon/network_simplex.h>
    46 
    47 
    47 using namespace lemon;
    48 using namespace lemon;
    48 typedef SmartDigraph Digraph;
    49 typedef SmartDigraph Digraph;
    49 DIGRAPH_TYPEDEFS(Digraph);
    50 DIGRAPH_TYPEDEFS(Digraph);
    50 typedef SmartGraph Graph;
    51 typedef SmartGraph Graph;
    88   pre.run();
    89   pre.run();
    89   if(report) std::cerr << "Run Preflow: " << ti << '\n';
    90   if(report) std::cerr << "Run Preflow: " << ti << '\n';
    90   if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n';  
    91   if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n';  
    91 }
    92 }
    92 
    93 
       
    94 template<class Value>
       
    95 void solve_min(ArgParser &ap, std::istream &is, std::ostream &,
       
    96                DimacsDescriptor &desc)
       
    97 {
       
    98   bool report = !ap.given("q");
       
    99   Digraph g;
       
   100   Digraph::ArcMap<Value> lower(g), cap(g), cost(g);
       
   101   Digraph::NodeMap<Value> sup(g);
       
   102   Timer ti;
       
   103   ti.restart();
       
   104   readDimacsMin(is, g, lower, cap, cost, sup, 0, desc);
       
   105   if (report) std::cerr << "Read the file: " << ti << '\n';
       
   106   ti.restart();
       
   107   NetworkSimplex<Digraph, Value> ns(g);
       
   108   ns.lowerMap(lower).capacityMap(cap).costMap(cost).supplyMap(sup);
       
   109   if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n';
       
   110   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';
       
   114 }
       
   115 
    93 void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
   116 void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
    94               DimacsDescriptor &desc)
   117               DimacsDescriptor &desc)
    95 {
   118 {
    96   bool report = !ap.given("q");
   119   bool report = !ap.given("q");
    97   Graph g;
   120   Graph g;
   126     }
   149     }
   127   
   150   
   128   switch(desc.type)
   151   switch(desc.type)
   129     {
   152     {
   130     case DimacsDescriptor::MIN:
   153     case DimacsDescriptor::MIN:
   131       std::cerr <<
   154       solve_min<Value>(ap,is,os,desc);
   132         "\n\n Sorry, the min. cost flow solver is not yet available.\n";
       
   133       break;
   155       break;
   134     case DimacsDescriptor::MAX:
   156     case DimacsDescriptor::MAX:
   135       solve_max<Value>(ap,is,os,infty,desc);
   157       solve_max<Value>(ap,is,os,infty,desc);
   136       break;
   158       break;
   137     case DimacsDescriptor::SP:
   159     case DimacsDescriptor::SP: