COIN-OR::LEMON - Graph Library

Changeset 573:28b154307c0d in lemon


Ignore:
Timestamp:
02/23/09 12:49:57 (9 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Message:

DIMACS solver utility (#226)

Location:
tools
Files:
1 edited
1 copied

Legend:

Unmodified
Added
Removed
  • tools/Makefile.am

    r570 r573  
    22 
    33bin_PROGRAMS += \ 
     4        tools/dimacs-solver \ 
    45        tools/dimacs-to-lgf \ 
    56        tools/lgf-gen 
     
    910endif WANT_TOOLS 
    1011 
     12tools_dimacs_solver_SOURCES = tools/dimacs-solver.cc 
    1113tools_dimacs_to_lgf_SOURCES = tools/dimacs-to-lgf.cc 
    1214tools_lgf_gen_SOURCES = tools/lgf-gen.cc 
  • tools/dimacs-solver.cc

    r463 r573  
    2626/// See 
    2727/// \verbatim 
    28 ///  dimacs-to-lgf --help 
     28///  dimacs-solver --help 
    2929/// \endverbatim 
    3030/// for more info on usage. 
     
    3838#include <lemon/dimacs.h> 
    3939#include <lemon/lgf_writer.h> 
     40#include <lemon/time_measure.h> 
    4041 
    4142#include <lemon/arg_parser.h> 
    4243#include <lemon/error.h> 
    4344 
    44 using namespace std; 
     45#include <lemon/dijkstra.h> 
     46#include <lemon/preflow.h> 
     47#include <lemon/max_matching.h> 
     48 
    4549using namespace lemon; 
    46  
     50typedef SmartDigraph Digraph; 
     51DIGRAPH_TYPEDEFS(Digraph); 
     52typedef SmartGraph Graph; 
     53 
     54template<class Value> 
     55void 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 
     74template<class Value> 
     75void 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 
     95void 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 
     115template<class Value> 
     116void 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} 
    47139 
    48140int main(int argc, const char *argv[]) { 
     
    63155           "If either the INFILE or OUTFILE file is missing the standard\n" 
    64156           "     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") 
    65169    .run(); 
    66170 
    67   ifstream input; 
    68   ofstream output; 
     171  std::ifstream input; 
     172  std::ofstream output; 
    69173 
    70174  switch(ap.files().size()) 
     
    83187      break; 
    84188    default: 
    85       cerr << ap.commandName() << ": too many arguments\n"; 
     189      std::cerr << ap.commandName() << ": too many arguments\n"; 
    86190      return 1; 
    87191  } 
    88   istream& is = (ap.files().size()<1 ? cin : input); 
    89   ostream& os = (ap.files().size()<2 ? cout : output); 
     192  std::istream& is = (ap.files().size()<1 ? std::cin : input); 
     193  std::ostream& os = (ap.files().size()<2 ? std::cout : output); 
    90194 
    91195  DimacsDescriptor desc = dimacsType(is); 
    92   switch(desc.type) 
     196   
     197  if(!ap.given("q")) 
    93198    { 
    94     case DimacsDescriptor::MIN: 
    95       { 
    96         Digraph digraph; 
    97         DoubleArcMap lower(digraph), capacity(digraph), cost(digraph); 
    98         DoubleNodeMap supply(digraph); 
    99         readDimacsMin(is, digraph, lower, capacity, cost, supply, desc); 
    100         DigraphWriter<Digraph>(digraph, os). 
    101           nodeMap("supply", supply). 
    102           arcMap("lower", lower). 
    103           arcMap("capacity", capacity). 
    104           arcMap("cost", cost). 
    105           attribute("problem","min"). 
    106           run(); 
    107       } 
    108       break; 
    109     case DimacsDescriptor::MAX: 
    110       { 
    111         Digraph digraph; 
    112         Node s, t; 
    113         DoubleArcMap capacity(digraph); 
    114         readDimacsMax(is, digraph, capacity, s, t, desc); 
    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; 
     199      std::cout << "Problem type: "; 
     200      switch(desc.type) 
     201        { 
     202        case DimacsDescriptor::MIN: 
     203          std::cout << "min"; 
     204          break; 
     205        case DimacsDescriptor::MAX: 
     206          std::cout << "max"; 
     207          break; 
     208        case DimacsDescriptor::SP: 
     209          std::cout << "sp"; 
     210        case DimacsDescriptor::MAT: 
     211          std::cout << "mat"; 
     212          break; 
     213        default: 
     214          exit(1); 
     215          break; 
     216        } 
     217      std::cout << "\nNum of nodes: " << desc.nodeNum; 
     218      std::cout << "\nNum of arcs:  " << desc.edgeNum; 
     219      std::cout << '\n' << std::endl; 
    147220    } 
     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 
    148232  return 0; 
    149233} 
Note: See TracChangeset for help on using the changeset viewer.