COIN-OR::LEMON - Graph Library

Changeset 526:28b154307c0d in lemon-1.2


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

DIMACS solver utility (#226)

Location:
tools
Files:
1 edited
1 copied

Legend:

Unmodified
Added
Removed
  • tools/Makefile.am

    r523 r526  
    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

    r440 r526  
    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.