tools/dimacs-solver.cc
changeset 604 8c3112a66878
parent 532 997a75bac45a
child 605 5232721b3f14
equal deleted inserted replaced
1:2a25b5457ab5 6:f80552137d64
    42 #include <lemon/error.h>
    42 #include <lemon/error.h>
    43 
    43 
    44 #include <lemon/dijkstra.h>
    44 #include <lemon/dijkstra.h>
    45 #include <lemon/preflow.h>
    45 #include <lemon/preflow.h>
    46 #include <lemon/max_matching.h>
    46 #include <lemon/max_matching.h>
       
    47 #include <lemon/network_simplex.h>
    47 
    48 
    48 using namespace lemon;
    49 using namespace lemon;
    49 typedef SmartDigraph Digraph;
    50 typedef SmartDigraph Digraph;
    50 DIGRAPH_TYPEDEFS(Digraph);
    51 DIGRAPH_TYPEDEFS(Digraph);
    51 typedef SmartGraph Graph;
    52 typedef SmartGraph Graph;
    89   pre.run();
    90   pre.run();
    90   if(report) std::cerr << "Run Preflow: " << ti << '\n';
    91   if(report) std::cerr << "Run Preflow: " << ti << '\n';
    91   if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n';  
    92   if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n';  
    92 }
    93 }
    93 
    94 
       
    95 template<class Value>
       
    96 void solve_min(ArgParser &ap, std::istream &is, std::ostream &,
       
    97                DimacsDescriptor &desc)
       
    98 {
       
    99   bool report = !ap.given("q");
       
   100   Digraph g;
       
   101   Digraph::ArcMap<Value> lower(g), cap(g), cost(g);
       
   102   Digraph::NodeMap<Value> sup(g);
       
   103   Timer ti;
       
   104   ti.restart();
       
   105   readDimacsMin(is, g, lower, cap, cost, sup, desc);
       
   106   if (report) std::cerr << "Read the file: " << ti << '\n';
       
   107   ti.restart();
       
   108   NetworkSimplex< Digraph, Digraph::ArcMap<Value>, Digraph::ArcMap<Value>,
       
   109                   Digraph::ArcMap<Value>, Digraph::NodeMap<Value> >
       
   110     ns(g, lower, cap, cost, sup);
       
   111   if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n';
       
   112   ti.restart();
       
   113   ns.run();
       
   114   if (report) std::cerr << "Run NetworkSimplex: " << ti << '\n';
       
   115   if (report) std::cerr << "\nMin flow cost: " << ns.totalCost() << '\n';
       
   116 }
       
   117 
    94 void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
   118 void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
    95               DimacsDescriptor &desc)
   119               DimacsDescriptor &desc)
    96 {
   120 {
    97   bool report = !ap.given("q");
   121   bool report = !ap.given("q");
    98   Graph g;
   122   Graph g;
   116            DimacsDescriptor &desc)
   140            DimacsDescriptor &desc)
   117 {
   141 {
   118   switch(desc.type)
   142   switch(desc.type)
   119     {
   143     {
   120     case DimacsDescriptor::MIN:
   144     case DimacsDescriptor::MIN:
   121       std::cerr <<
   145       solve_min<Value>(ap,is,os,desc);
   122         "\n\n Sorry, the min. cost flow solver is not yet available.\n";
       
   123       break;
   146       break;
   124     case DimacsDescriptor::MAX:
   147     case DimacsDescriptor::MAX:
   125       solve_max<Value>(ap,is,os,desc);
   148       solve_max<Value>(ap,is,os,desc);
   126       break;
   149       break;
   127     case DimacsDescriptor::SP:
   150     case DimacsDescriptor::SP: