tools/dimacs-solver.cc
changeset 530 1c5d6e47921f
parent 440 88ed40ad0d4f
child 532 997a75bac45a
equal deleted inserted replaced
3:b9773283e6cf 0:77697ce85cca
    23 /// This program converts various DIMACS formats to the LEMON Digraph Format
    23 /// This program converts various DIMACS formats to the LEMON Digraph Format
    24 /// (LGF).
    24 /// (LGF).
    25 ///
    25 ///
    26 /// See
    26 /// See
    27 /// \verbatim
    27 /// \verbatim
    28 ///  dimacs-to-lgf --help
    28 ///  dimacs-solver --help
    29 /// \endverbatim
    29 /// \endverbatim
    30 /// for more info on usage.
    30 /// for more info on usage.
    31 ///
    31 ///
    32 
    32 
    33 #include <iostream>
    33 #include <iostream>
    35 #include <cstring>
    35 #include <cstring>
    36 
    36 
    37 #include <lemon/smart_graph.h>
    37 #include <lemon/smart_graph.h>
    38 #include <lemon/dimacs.h>
    38 #include <lemon/dimacs.h>
    39 #include <lemon/lgf_writer.h>
    39 #include <lemon/lgf_writer.h>
       
    40 #include <lemon/time_measure.h>
    40 
    41 
    41 #include <lemon/arg_parser.h>
    42 #include <lemon/arg_parser.h>
    42 #include <lemon/error.h>
    43 #include <lemon/error.h>
    43 
    44 
    44 using namespace std;
    45 #include <lemon/dijkstra.h>
       
    46 #include <lemon/preflow.h>
       
    47 #include <lemon/max_matching.h>
       
    48 
    45 using namespace lemon;
    49 using namespace lemon;
    46 
    50 typedef SmartDigraph Digraph;
       
    51 DIGRAPH_TYPEDEFS(Digraph);
       
    52 typedef SmartGraph Graph;
       
    53 
       
    54 template<class Value>
       
    55 void solve_sp(ArgParser &ap, std::istream &is, std::ostream &,
       
    56               DimacsDescriptor &desc)
       
    57 {
       
    58   bool report = !ap.given("q");
       
    59   Digraph g;
       
    60   Node s;
       
    61   Digraph::ArcMap<Value> len(g);
       
    62   Timer t;
       
    63   t.restart();
       
    64   readDimacsSp(is, g, len, s, desc);
       
    65   if(report) std::cerr << "Read the file: " << t << '\n';
       
    66   t.restart();
       
    67   Dijkstra<Digraph, Digraph::ArcMap<Value> > dij(g,len);
       
    68   if(report) std::cerr << "Setup Dijkstra class: " << t << '\n';
       
    69   t.restart();
       
    70   dij.run(s);
       
    71   if(report) std::cerr << "Run Dijkstra: " << t << '\n';
       
    72 }
       
    73 
       
    74 template<class Value>
       
    75 void solve_max(ArgParser &ap, std::istream &is, std::ostream &,
       
    76               DimacsDescriptor &desc)
       
    77 {
       
    78   bool report = !ap.given("q");
       
    79   Digraph g;
       
    80   Node s,t;
       
    81   Digraph::ArcMap<Value> cap(g);
       
    82   Timer ti;
       
    83   ti.restart();
       
    84   readDimacsMax(is, g, cap, s, t, desc);
       
    85   if(report) std::cerr << "Read the file: " << ti << '\n';
       
    86   ti.restart();
       
    87   Preflow<Digraph, Digraph::ArcMap<Value> > pre(g,cap,s,t);
       
    88   if(report) std::cerr << "Setup Preflow class: " << ti << '\n';
       
    89   ti.restart();
       
    90   pre.run();
       
    91   if(report) std::cerr << "Run Preflow: " << ti << '\n';
       
    92   if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n';  
       
    93 }
       
    94 
       
    95 void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
       
    96               DimacsDescriptor &desc)
       
    97 {
       
    98   bool report = !ap.given("q");
       
    99   Graph g;
       
   100   Timer ti;
       
   101   ti.restart();
       
   102   readDimacsMat(is, g, desc);
       
   103   if(report) std::cerr << "Read the file: " << ti << '\n';
       
   104   ti.restart();
       
   105   MaxMatching<Graph> mat(g);
       
   106   if(report) std::cerr << "Setup MaxMatching class: " << ti << '\n';
       
   107   ti.restart();
       
   108   mat.run();
       
   109   if(report) std::cerr << "Run MaxMatching: " << ti << '\n';
       
   110   if(report) std::cerr << "\nCardinality of max matching: "
       
   111                        << mat.matchingSize() << '\n';  
       
   112 }
       
   113 
       
   114 
       
   115 template<class Value>
       
   116 void solve(ArgParser &ap, std::istream &is, std::ostream &os,
       
   117            DimacsDescriptor &desc)
       
   118 {
       
   119   switch(desc.type)
       
   120     {
       
   121     case DimacsDescriptor::MIN:
       
   122       std::cerr <<
       
   123         "\n\n Sorry, the min. cost flow solver is not yet available.\n"
       
   124                 << std::endl;
       
   125       break;
       
   126     case DimacsDescriptor::MAX:
       
   127       solve_max<Value>(ap,is,os,desc);
       
   128       break;
       
   129     case DimacsDescriptor::SP:
       
   130       solve_sp<Value>(ap,is,os,desc);
       
   131       break;
       
   132     case DimacsDescriptor::MAT:
       
   133       solve_mat(ap,is,os,desc);
       
   134       break;
       
   135     default:
       
   136       break;
       
   137     }
       
   138 }
    47 
   139 
    48 int main(int argc, const char *argv[]) {
   140 int main(int argc, const char *argv[]) {
    49   typedef SmartDigraph Digraph;
   141   typedef SmartDigraph Digraph;
    50 
   142 
    51   typedef Digraph::Arc Arc;
   143   typedef Digraph::Arc Arc;
    60 
   152 
    61   ArgParser ap(argc, argv);
   153   ArgParser ap(argc, argv);
    62   ap.other("[INFILE [OUTFILE]]",
   154   ap.other("[INFILE [OUTFILE]]",
    63            "If either the INFILE or OUTFILE file is missing the standard\n"
   155            "If either the INFILE or OUTFILE file is missing the standard\n"
    64            "     input/output will be used instead.")
   156            "     input/output will be used instead.")
       
   157     .boolOption("q", "Do not print any report")
       
   158     .boolOption("int","Use 'int' for capacities, costs etc. (default)")
       
   159     .optionGroup("datatype","int")
       
   160 #ifdef HAVE_LONG_LONG
       
   161     .boolOption("long","Use 'long long' for capacities, costs etc.")
       
   162     .optionGroup("datatype","long")
       
   163 #endif
       
   164     .boolOption("double","Use 'double' for capacities, costs etc.")
       
   165     .optionGroup("datatype","double")
       
   166     .boolOption("ldouble","Use 'long double' for capacities, costs etc.")
       
   167     .optionGroup("datatype","ldouble")
       
   168     .onlyOneGroup("datatype")
    65     .run();
   169     .run();
    66 
   170 
    67   ifstream input;
   171   std::ifstream input;
    68   ofstream output;
   172   std::ofstream output;
    69 
   173 
    70   switch(ap.files().size())
   174   switch(ap.files().size())
    71     {
   175     {
    72     case 2:
   176     case 2:
    73       output.open(ap.files()[1].c_str());
   177       output.open(ap.files()[1].c_str());
    80         throw IoError("File cannot be found", ap.files()[0]);
   184         throw IoError("File cannot be found", ap.files()[0]);
    81       }
   185       }
    82     case 0:
   186     case 0:
    83       break;
   187       break;
    84     default:
   188     default:
    85       cerr << ap.commandName() << ": too many arguments\n";
   189       std::cerr << ap.commandName() << ": too many arguments\n";
    86       return 1;
   190       return 1;
    87   }
   191   }
    88   istream& is = (ap.files().size()<1 ? cin : input);
   192   std::istream& is = (ap.files().size()<1 ? std::cin : input);
    89   ostream& os = (ap.files().size()<2 ? cout : output);
   193   std::ostream& os = (ap.files().size()<2 ? std::cout : output);
    90 
   194 
    91   DimacsDescriptor desc = dimacsType(is);
   195   DimacsDescriptor desc = dimacsType(is);
    92   switch(desc.type)
   196   
       
   197   if(!ap.given("q"))
    93     {
   198     {
    94     case DimacsDescriptor::MIN:
   199       std::cout << "Problem type: ";
    95       {
   200       switch(desc.type)
    96         Digraph digraph;
   201         {
    97         DoubleArcMap lower(digraph), capacity(digraph), cost(digraph);
   202         case DimacsDescriptor::MIN:
    98         DoubleNodeMap supply(digraph);
   203           std::cout << "min";
    99         readDimacsMin(is, digraph, lower, capacity, cost, supply, desc);
   204           break;
   100         DigraphWriter<Digraph>(digraph, os).
   205         case DimacsDescriptor::MAX:
   101           nodeMap("supply", supply).
   206           std::cout << "max";
   102           arcMap("lower", lower).
   207           break;
   103           arcMap("capacity", capacity).
   208         case DimacsDescriptor::SP:
   104           arcMap("cost", cost).
   209           std::cout << "sp";
   105           attribute("problem","min").
   210         case DimacsDescriptor::MAT:
   106           run();
   211           std::cout << "mat";
   107       }
   212           break;
   108       break;
   213         default:
   109     case DimacsDescriptor::MAX:
   214           exit(1);
   110       {
   215           break;
   111         Digraph digraph;
   216         }
   112         Node s, t;
   217       std::cout << "\nNum of nodes: " << desc.nodeNum;
   113         DoubleArcMap capacity(digraph);
   218       std::cout << "\nNum of arcs:  " << desc.edgeNum;
   114         readDimacsMax(is, digraph, capacity, s, t, desc);
   219       std::cout << '\n' << std::endl;
   115         DigraphWriter<Digraph>(digraph, os).
       
   116           arcMap("capacity", capacity).
       
   117           node("source", s).
       
   118           node("target", t).
       
   119           attribute("problem","max").
       
   120           run();
       
   121       }
       
   122       break;
       
   123     case DimacsDescriptor::SP:
       
   124       {
       
   125         Digraph digraph;
       
   126         Node s;
       
   127         DoubleArcMap capacity(digraph);
       
   128         readDimacsSp(is, digraph, capacity, s, desc);
       
   129         DigraphWriter<Digraph>(digraph, os).
       
   130           arcMap("capacity", capacity).
       
   131           node("source", s).
       
   132           attribute("problem","sp").
       
   133           run();
       
   134       }
       
   135       break;
       
   136     case DimacsDescriptor::MAT:
       
   137       {
       
   138         Digraph digraph;
       
   139         readDimacsMat(is, digraph,desc);
       
   140         DigraphWriter<Digraph>(digraph, os).
       
   141           attribute("problem","mat").
       
   142           run();
       
   143       }
       
   144       break;
       
   145     default:
       
   146       break;
       
   147     }
   220     }
       
   221     
       
   222   if(ap.given("double"))
       
   223     solve<double>(ap,is,os,desc);
       
   224   else if(ap.given("ldouble"))
       
   225     solve<long double>(ap,is,os,desc);
       
   226 #ifdef HAVE_LONG_LONG
       
   227   else if(ap.given("long"))
       
   228     solve<long long>(ap,is,os,desc);
       
   229 #endif
       
   230   else solve<int>(ap,is,os,desc);
       
   231 
   148   return 0;
   232   return 0;
   149 }
   233 }