lemon/arg_parser.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 13 Nov 2009 00:10:33 +0100
changeset 815 aef153f430e1
parent 311 c887e703b566
child 842 c2ff0a365245
permissions -rw-r--r--
Entirely rework cycle canceling algorithms (#180)

- Move the cycle canceling algorithms (CycleCanceling, CancelAndTighten)
into one class (CycleCanceling).
- Add a Method parameter to the run() function to be able to select
the used cycle canceling method.
- Use the new interface similarly to NetworkSimplex.
- Rework the implementations using an efficient internal structure
for handling the residual network.
This improvement made the codes much faster.
- Handle GEQ supply type (LEQ is not supported).
- Handle infinite upper bounds.
- Handle negative costs (for arcs of finite upper bound).
- Extend the documentation.
alpar@209
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@85
     2
 *
alpar@209
     3
 * This file is a part of LEMON, a generic C++ optimization library.
alpar@85
     4
 *
alpar@440
     5
 * Copyright (C) 2003-2009
alpar@85
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@85
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@85
     8
 *
alpar@85
     9
 * Permission to use, modify and distribute this software is granted
alpar@85
    10
 * provided that this copyright notice appears in all copies. For
alpar@85
    11
 * precise terms see the accompanying LICENSE file.
alpar@85
    12
 *
alpar@85
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@85
    14
 * express or implied, and with no claim as to its suitability for any
alpar@85
    15
 * purpose.
alpar@85
    16
 *
alpar@85
    17
 */
alpar@85
    18
alpar@85
    19
#include <lemon/arg_parser.h>
alpar@85
    20
alpar@85
    21
namespace lemon {
alpar@85
    22
alpar@85
    23
  void ArgParser::_showHelp(void *p)
alpar@85
    24
  {
alpar@85
    25
    (static_cast<ArgParser*>(p))->showHelp();
alpar@85
    26
    exit(1);
alpar@85
    27
  }
alpar@85
    28
ladanyi@311
    29
  ArgParser::ArgParser(int argc, const char * const *argv)
ladanyi@311
    30
    :_argc(argc), _argv(argv), _command_name(argv[0]) {
alpar@85
    31
    funcOption("-help","Print a short help message",_showHelp,this);
alpar@85
    32
    synonym("help","-help");
alpar@85
    33
    synonym("h","-help");
alpar@85
    34
  }
alpar@85
    35
alpar@85
    36
  ArgParser::~ArgParser()
alpar@85
    37
  {
alpar@85
    38
    for(Opts::iterator i=_opts.begin();i!=_opts.end();++i)
alpar@85
    39
      if(i->second.self_delete)
alpar@209
    40
        switch(i->second.type) {
alpar@209
    41
        case BOOL:
alpar@209
    42
          delete i->second.bool_p;
alpar@209
    43
          break;
alpar@209
    44
        case STRING:
alpar@209
    45
          delete i->second.string_p;
alpar@209
    46
          break;
alpar@209
    47
        case DOUBLE:
alpar@209
    48
          delete i->second.double_p;
alpar@209
    49
          break;
alpar@209
    50
        case INTEGER:
alpar@209
    51
          delete i->second.int_p;
alpar@209
    52
          break;
alpar@209
    53
        case UNKNOWN:
alpar@209
    54
          break;
alpar@209
    55
        case FUNC:
alpar@209
    56
          break;
alpar@209
    57
        }
alpar@85
    58
  }
alpar@209
    59
alpar@85
    60
alpar@85
    61
  ArgParser &ArgParser::intOption(const std::string &name,
alpar@209
    62
                               const std::string &help,
alpar@209
    63
                               int value, bool obl)
alpar@85
    64
  {
alpar@85
    65
    ParData p;
alpar@85
    66
    p.int_p=new int(value);
alpar@85
    67
    p.self_delete=true;
alpar@85
    68
    p.help=help;
alpar@85
    69
    p.type=INTEGER;
alpar@85
    70
    p.mandatory=obl;
alpar@85
    71
    _opts[name]=p;
alpar@85
    72
    return *this;
alpar@85
    73
  }
alpar@85
    74
alpar@85
    75
  ArgParser &ArgParser::doubleOption(const std::string &name,
alpar@209
    76
                               const std::string &help,
alpar@209
    77
                               double value, bool obl)
alpar@85
    78
  {
alpar@85
    79
    ParData p;
alpar@85
    80
    p.double_p=new double(value);
alpar@85
    81
    p.self_delete=true;
alpar@85
    82
    p.help=help;
alpar@85
    83
    p.type=DOUBLE;
alpar@85
    84
    p.mandatory=obl;
alpar@85
    85
    _opts[name]=p;
alpar@85
    86
    return *this;
alpar@85
    87
  }
alpar@85
    88
alpar@85
    89
  ArgParser &ArgParser::boolOption(const std::string &name,
alpar@209
    90
                               const std::string &help,
alpar@209
    91
                               bool value, bool obl)
alpar@85
    92
  {
alpar@85
    93
    ParData p;
alpar@85
    94
    p.bool_p=new bool(value);
alpar@85
    95
    p.self_delete=true;
alpar@85
    96
    p.help=help;
alpar@85
    97
    p.type=BOOL;
alpar@85
    98
    p.mandatory=obl;
alpar@85
    99
    _opts[name]=p;
alpar@85
   100
    return *this;
alpar@85
   101
  }
alpar@85
   102
alpar@85
   103
  ArgParser &ArgParser::stringOption(const std::string &name,
alpar@209
   104
                               const std::string &help,
alpar@209
   105
                               std::string value, bool obl)
alpar@85
   106
  {
alpar@85
   107
    ParData p;
alpar@85
   108
    p.string_p=new std::string(value);
alpar@85
   109
    p.self_delete=true;
alpar@85
   110
    p.help=help;
alpar@85
   111
    p.type=STRING;
alpar@85
   112
    p.mandatory=obl;
alpar@85
   113
    _opts[name]=p;
alpar@85
   114
    return *this;
alpar@85
   115
  }
alpar@85
   116
alpar@85
   117
  ArgParser &ArgParser::refOption(const std::string &name,
alpar@209
   118
                               const std::string &help,
alpar@209
   119
                               int &ref, bool obl)
alpar@85
   120
  {
alpar@85
   121
    ParData p;
alpar@85
   122
    p.int_p=&ref;
alpar@85
   123
    p.self_delete=false;
alpar@85
   124
    p.help=help;
alpar@85
   125
    p.type=INTEGER;
alpar@85
   126
    p.mandatory=obl;
alpar@85
   127
    _opts[name]=p;
alpar@85
   128
    return *this;
alpar@85
   129
  }
alpar@85
   130
alpar@85
   131
  ArgParser &ArgParser::refOption(const std::string &name,
alpar@85
   132
                                  const std::string &help,
alpar@85
   133
                                  double &ref, bool obl)
alpar@85
   134
  {
alpar@85
   135
    ParData p;
alpar@85
   136
    p.double_p=&ref;
alpar@85
   137
    p.self_delete=false;
alpar@85
   138
    p.help=help;
alpar@85
   139
    p.type=DOUBLE;
alpar@85
   140
    p.mandatory=obl;
alpar@85
   141
    _opts[name]=p;
alpar@85
   142
    return *this;
alpar@85
   143
  }
alpar@85
   144
alpar@85
   145
  ArgParser &ArgParser::refOption(const std::string &name,
alpar@85
   146
                                  const std::string &help,
alpar@85
   147
                                  bool &ref, bool obl)
alpar@85
   148
  {
alpar@85
   149
    ParData p;
alpar@85
   150
    p.bool_p=&ref;
alpar@85
   151
    p.self_delete=false;
alpar@85
   152
    p.help=help;
alpar@85
   153
    p.type=BOOL;
alpar@85
   154
    p.mandatory=obl;
alpar@85
   155
    _opts[name]=p;
alpar@85
   156
alpar@85
   157
    ref = false;
alpar@85
   158
alpar@85
   159
    return *this;
alpar@85
   160
  }
alpar@85
   161
alpar@85
   162
  ArgParser &ArgParser::refOption(const std::string &name,
alpar@209
   163
                               const std::string &help,
alpar@209
   164
                               std::string &ref, bool obl)
alpar@85
   165
  {
alpar@85
   166
    ParData p;
alpar@85
   167
    p.string_p=&ref;
alpar@85
   168
    p.self_delete=false;
alpar@85
   169
    p.help=help;
alpar@85
   170
    p.type=STRING;
alpar@85
   171
    p.mandatory=obl;
alpar@85
   172
    _opts[name]=p;
alpar@85
   173
    return *this;
alpar@85
   174
  }
alpar@85
   175
alpar@85
   176
  ArgParser &ArgParser::funcOption(const std::string &name,
alpar@209
   177
                               const std::string &help,
alpar@209
   178
                               void (*func)(void *),void *data)
alpar@85
   179
  {
alpar@85
   180
    ParData p;
alpar@85
   181
    p.func_p.p=func;
alpar@85
   182
    p.func_p.data=data;
alpar@85
   183
    p.self_delete=false;
alpar@85
   184
    p.help=help;
alpar@85
   185
    p.type=FUNC;
alpar@85
   186
    p.mandatory=false;
alpar@85
   187
    _opts[name]=p;
alpar@85
   188
    return *this;
alpar@85
   189
  }
alpar@85
   190
alpar@85
   191
  ArgParser &ArgParser::optionGroup(const std::string &group,
alpar@209
   192
                                    const std::string &opt)
alpar@85
   193
  {
alpar@85
   194
    Opts::iterator i = _opts.find(opt);
alpar@85
   195
    LEMON_ASSERT(i!=_opts.end(), "Unknown option: '"+opt+"'");
alpar@209
   196
    LEMON_ASSERT(!(i->second.ingroup),
alpar@85
   197
                 "Option already in option group: '"+opt+"'");
alpar@85
   198
    GroupData &g=_groups[group];
alpar@85
   199
    g.opts.push_back(opt);
alpar@85
   200
    i->second.ingroup=true;
alpar@85
   201
    return *this;
alpar@85
   202
  }
alpar@85
   203
alpar@85
   204
  ArgParser &ArgParser::onlyOneGroup(const std::string &group)
alpar@85
   205
  {
alpar@85
   206
    GroupData &g=_groups[group];
alpar@85
   207
    g.only_one=true;
alpar@85
   208
    return *this;
alpar@85
   209
  }
alpar@85
   210
alpar@85
   211
  ArgParser &ArgParser::synonym(const std::string &syn,
alpar@209
   212
                                const std::string &opt)
alpar@85
   213
  {
alpar@85
   214
    Opts::iterator o = _opts.find(opt);
alpar@85
   215
    Opts::iterator s = _opts.find(syn);
alpar@85
   216
    LEMON_ASSERT(o!=_opts.end(), "Unknown option: '"+opt+"'");
alpar@85
   217
    LEMON_ASSERT(s==_opts.end(), "Option already used: '"+syn+"'");
alpar@85
   218
    ParData p;
alpar@85
   219
    p.help=opt;
alpar@85
   220
    p.mandatory=false;
alpar@85
   221
    p.syn=true;
alpar@85
   222
    _opts[syn]=p;
alpar@85
   223
    o->second.has_syn=true;
alpar@85
   224
    return *this;
alpar@85
   225
  }
alpar@85
   226
alpar@85
   227
  ArgParser &ArgParser::mandatoryGroup(const std::string &group)
alpar@85
   228
  {
alpar@85
   229
    GroupData &g=_groups[group];
alpar@85
   230
    g.mandatory=true;
alpar@85
   231
    return *this;
alpar@85
   232
  }
alpar@85
   233
alpar@85
   234
  ArgParser &ArgParser::other(const std::string &name,
alpar@209
   235
                              const std::string &help)
alpar@85
   236
  {
alpar@85
   237
    _others_help.push_back(OtherArg(name,help));
alpar@85
   238
    return *this;
alpar@85
   239
  }
alpar@85
   240
alpar@214
   241
  void ArgParser::show(std::ostream &os,Opts::const_iterator i) const
alpar@85
   242
  {
alpar@85
   243
    os << "-" << i->first;
alpar@85
   244
    if(i->second.has_syn)
alpar@214
   245
      for(Opts::const_iterator j=_opts.begin();j!=_opts.end();++j)
alpar@209
   246
        if(j->second.syn&&j->second.help==i->first)
alpar@209
   247
          os << "|-" << j->first;
alpar@85
   248
    switch(i->second.type) {
alpar@85
   249
    case STRING:
alpar@85
   250
      os << " str";
alpar@85
   251
      break;
alpar@85
   252
    case INTEGER:
alpar@85
   253
      os << " int";
alpar@85
   254
      break;
alpar@85
   255
    case DOUBLE:
alpar@85
   256
      os << " num";
alpar@85
   257
      break;
alpar@85
   258
    default:
alpar@85
   259
      break;
alpar@85
   260
    }
alpar@85
   261
  }
alpar@85
   262
alpar@214
   263
  void ArgParser::show(std::ostream &os,Groups::const_iterator i) const
alpar@85
   264
  {
alpar@214
   265
    GroupData::Opts::const_iterator o=i->second.opts.begin();
alpar@85
   266
    while(o!=i->second.opts.end()) {
alpar@85
   267
      show(os,_opts.find(*o));
alpar@85
   268
      ++o;
alpar@85
   269
      if(o!=i->second.opts.end()) os<<'|';
alpar@85
   270
    }
alpar@85
   271
  }
alpar@209
   272
alpar@214
   273
  void ArgParser::showHelp(Opts::const_iterator i) const
alpar@85
   274
  {
alpar@85
   275
    if(i->second.help.size()==0||i->second.syn) return;
alpar@85
   276
    std::cerr << "  ";
alpar@85
   277
    show(std::cerr,i);
alpar@85
   278
    std::cerr << std::endl;
alpar@85
   279
    std::cerr << "     " << i->second.help << std::endl;
alpar@85
   280
  }
alpar@214
   281
  void ArgParser::showHelp(std::vector<ArgParser::OtherArg>::const_iterator i)
alpar@214
   282
    const
alpar@85
   283
  {
alpar@85
   284
    if(i->help.size()==0) return;
alpar@85
   285
    std::cerr << "  " << i->name << std::endl
alpar@209
   286
              << "     " << i->help << std::endl;
alpar@85
   287
  }
alpar@209
   288
alpar@214
   289
  void ArgParser::shortHelp() const
alpar@85
   290
  {
alpar@85
   291
    const unsigned int LINE_LEN=77;
alpar@85
   292
    const std::string indent("    ");
alpar@85
   293
    std::cerr << "Usage:\n  " << _command_name;
alpar@85
   294
    int pos=_command_name.size()+2;
alpar@214
   295
    for(Groups::const_iterator g=_groups.begin();g!=_groups.end();++g) {
alpar@85
   296
      std::ostringstream cstr;
alpar@85
   297
      cstr << ' ';
alpar@85
   298
      if(!g->second.mandatory) cstr << '[';
alpar@85
   299
      show(cstr,g);
alpar@85
   300
      if(!g->second.mandatory) cstr << ']';
alpar@85
   301
      if(pos+cstr.str().size()>LINE_LEN) {
alpar@209
   302
        std::cerr << std::endl << indent;
alpar@209
   303
        pos=indent.size();
alpar@85
   304
      }
alpar@85
   305
      std::cerr << cstr.str();
alpar@85
   306
      pos+=cstr.str().size();
alpar@85
   307
    }
alpar@214
   308
    for(Opts::const_iterator i=_opts.begin();i!=_opts.end();++i)
alpar@85
   309
      if(!i->second.ingroup&&!i->second.syn) {
alpar@209
   310
        std::ostringstream cstr;
alpar@209
   311
        cstr << ' ';
alpar@209
   312
        if(!i->second.mandatory) cstr << '[';
alpar@209
   313
        show(cstr,i);
alpar@209
   314
        if(!i->second.mandatory) cstr << ']';
alpar@209
   315
        if(pos+cstr.str().size()>LINE_LEN) {
alpar@209
   316
          std::cerr << std::endl << indent;
alpar@209
   317
          pos=indent.size();
alpar@209
   318
        }
alpar@209
   319
        std::cerr << cstr.str();
alpar@209
   320
        pos+=cstr.str().size();
alpar@85
   321
      }
alpar@214
   322
    for(std::vector<OtherArg>::const_iterator i=_others_help.begin();
alpar@209
   323
        i!=_others_help.end();++i)
alpar@85
   324
      {
alpar@209
   325
        std::ostringstream cstr;
alpar@209
   326
        cstr << ' ' << i->name;
alpar@209
   327
alpar@209
   328
        if(pos+cstr.str().size()>LINE_LEN) {
alpar@209
   329
          std::cerr << std::endl << indent;
alpar@209
   330
          pos=indent.size();
alpar@209
   331
        }
alpar@209
   332
        std::cerr << cstr.str();
alpar@209
   333
        pos+=cstr.str().size();
alpar@85
   334
      }
alpar@85
   335
    std::cerr << std::endl;
alpar@85
   336
  }
alpar@209
   337
alpar@214
   338
  void ArgParser::showHelp() const
alpar@85
   339
  {
alpar@85
   340
    shortHelp();
alpar@85
   341
    std::cerr << "Where:\n";
alpar@214
   342
    for(std::vector<OtherArg>::const_iterator i=_others_help.begin();
alpar@209
   343
        i!=_others_help.end();++i) showHelp(i);
alpar@214
   344
    for(Opts::const_iterator i=_opts.begin();i!=_opts.end();++i) showHelp(i);
alpar@85
   345
    exit(1);
alpar@85
   346
  }
alpar@209
   347
alpar@209
   348
alpar@214
   349
  void ArgParser::unknownOpt(std::string arg) const
alpar@85
   350
  {
alpar@85
   351
    std::cerr << "\nUnknown option: " << arg << "\n";
alpar@85
   352
    std::cerr << "\nType '" << _command_name <<
alpar@85
   353
      " --help' to obtain a short summary on the usage.\n\n";
alpar@85
   354
    exit(1);
alpar@85
   355
  }
alpar@209
   356
alpar@214
   357
  void ArgParser::requiresValue(std::string arg, OptType t) const
alpar@85
   358
  {
alpar@85
   359
    std::cerr << "Argument '" << arg << "' requires a";
alpar@85
   360
    switch(t) {
alpar@85
   361
    case STRING:
alpar@85
   362
      std::cerr << " string";
alpar@85
   363
      break;
alpar@85
   364
    case INTEGER:
alpar@85
   365
      std::cerr << "n integer";
alpar@85
   366
      break;
alpar@85
   367
    case DOUBLE:
alpar@85
   368
      std::cerr << " floating point";
alpar@85
   369
      break;
alpar@85
   370
    default:
alpar@85
   371
      break;
alpar@85
   372
    }
alpar@85
   373
    std::cerr << " value\n\n";
alpar@85
   374
    showHelp();
alpar@85
   375
  }
alpar@209
   376
alpar@85
   377
alpar@214
   378
  void ArgParser::checkMandatories() const
alpar@85
   379
  {
alpar@85
   380
    bool ok=true;
alpar@214
   381
    for(Opts::const_iterator i=_opts.begin();i!=_opts.end();++i)
alpar@209
   382
      if(i->second.mandatory&&!i->second.set)
alpar@209
   383
        {
alpar@209
   384
          if(ok)
alpar@209
   385
            std::cerr << _command_name
alpar@209
   386
                      << ": The following mandatory arguments are missing.\n";
alpar@209
   387
          ok=false;
alpar@209
   388
          showHelp(i);
alpar@209
   389
        }
alpar@214
   390
    for(Groups::const_iterator i=_groups.begin();i!=_groups.end();++i)
alpar@85
   391
      if(i->second.mandatory||i->second.only_one)
alpar@209
   392
        {
alpar@209
   393
          int set=0;
alpar@214
   394
          for(GroupData::Opts::const_iterator o=i->second.opts.begin();
alpar@209
   395
              o!=i->second.opts.end();++o)
alpar@209
   396
            if(_opts.find(*o)->second.set) ++set;
alpar@209
   397
          if(i->second.mandatory&&!set) {
alpar@210
   398
            std::cerr << _command_name <<
alpar@210
   399
              ": At least one of the following arguments is mandatory.\n";
alpar@209
   400
            ok=false;
alpar@214
   401
            for(GroupData::Opts::const_iterator o=i->second.opts.begin();
alpar@209
   402
                o!=i->second.opts.end();++o)
alpar@209
   403
              showHelp(_opts.find(*o));
alpar@209
   404
          }
alpar@209
   405
          if(i->second.only_one&&set>1) {
alpar@210
   406
            std::cerr << _command_name <<
alpar@210
   407
              ": At most one of the following arguments can be given.\n";
alpar@209
   408
            ok=false;
alpar@214
   409
            for(GroupData::Opts::const_iterator o=i->second.opts.begin();
alpar@209
   410
                o!=i->second.opts.end();++o)
alpar@209
   411
              showHelp(_opts.find(*o));
alpar@209
   412
          }
alpar@209
   413
        }
alpar@85
   414
    if(!ok) {
alpar@85
   415
      std::cerr << "\nType '" << _command_name <<
alpar@209
   416
        " --help' to obtain a short summary on the usage.\n\n";
alpar@85
   417
      exit(1);
alpar@85
   418
    }
alpar@85
   419
  }
alpar@85
   420
alpar@85
   421
  ArgParser &ArgParser::parse()
alpar@85
   422
  {
alpar@85
   423
    for(int ar=1; ar<_argc; ++ar) {
alpar@85
   424
      std::string arg(_argv[ar]);
alpar@85
   425
      if (arg[0] != '-' || arg.size() == 1) {
alpar@209
   426
        _file_args.push_back(arg);
alpar@85
   427
      }
alpar@85
   428
      else {
alpar@209
   429
        Opts::iterator i = _opts.find(arg.substr(1));
alpar@209
   430
        if(i==_opts.end()) unknownOpt(arg);
alpar@209
   431
        else {
alpar@209
   432
          if(i->second.syn) i=_opts.find(i->second.help);
alpar@209
   433
          ParData &p(i->second);
alpar@209
   434
          if (p.type==BOOL) *p.bool_p=true;
alpar@209
   435
          else if (p.type==FUNC) p.func_p.p(p.func_p.data);
alpar@209
   436
          else if(++ar==_argc) requiresValue(arg, p.type);
alpar@209
   437
          else {
alpar@209
   438
            std::string val(_argv[ar]);
alpar@209
   439
            std::istringstream vals(val);
alpar@209
   440
            switch(p.type) {
alpar@209
   441
            case STRING:
alpar@209
   442
              *p.string_p=val;
alpar@209
   443
              break;
alpar@209
   444
            case INTEGER:
alpar@209
   445
              vals >> *p.int_p;
alpar@209
   446
              break;
alpar@209
   447
            case DOUBLE:
alpar@209
   448
              vals >> *p.double_p;
alpar@209
   449
              break;
alpar@209
   450
            default:
alpar@209
   451
              break;
alpar@209
   452
            }
alpar@209
   453
            if(p.type!=STRING&&(!vals||!vals.eof()))
alpar@209
   454
              requiresValue(arg, p.type);
alpar@209
   455
          }
alpar@209
   456
          p.set = true;
alpar@209
   457
        }
alpar@85
   458
      }
alpar@85
   459
    }
alpar@85
   460
    checkMandatories();
alpar@85
   461
alpar@85
   462
    return *this;
alpar@209
   463
  }
alpar@85
   464
alpar@85
   465
}