lemon/dimacs.h
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 24 Mar 2009 00:18:25 +0100
changeset 604 8c3112a66878
parent 440 88ed40ad0d4f
child 561 6e0525ec5355
permissions -rw-r--r--
Use XTI implementation instead of ATI in NetworkSimplex (#234)

XTI (eXtended Threaded Index) is an imporved version of the widely
known ATI (Augmented Threaded Index) method for storing and updating
the spanning tree structure in Network Simplex algorithms.

In the ATI data structure three indices are stored for each node:
predecessor, thread and depth. In the XTI data structure depth is
replaced by the number of successors and the last successor
(according to the thread index).
alpar@385
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@385
     2
 *
alpar@385
     3
 * This file is a part of LEMON, a generic C++ optimization library.
alpar@385
     4
 *
alpar@440
     5
 * Copyright (C) 2003-2009
alpar@385
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@385
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@385
     8
 *
alpar@385
     9
 * Permission to use, modify and distribute this software is granted
alpar@385
    10
 * provided that this copyright notice appears in all copies. For
alpar@385
    11
 * precise terms see the accompanying LICENSE file.
alpar@385
    12
 *
alpar@385
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@385
    14
 * express or implied, and with no claim as to its suitability for any
alpar@385
    15
 * purpose.
alpar@385
    16
 *
alpar@385
    17
 */
alpar@385
    18
alpar@385
    19
#ifndef LEMON_DIMACS_H
alpar@385
    20
#define LEMON_DIMACS_H
alpar@385
    21
alpar@385
    22
#include <iostream>
alpar@385
    23
#include <string>
alpar@385
    24
#include <vector>
alpar@385
    25
#include <lemon/maps.h>
alpar@387
    26
#include <lemon/error.h>
alpar@385
    27
alpar@385
    28
/// \ingroup dimacs_group
alpar@385
    29
/// \file
alpar@385
    30
/// \brief DIMACS file format reader.
alpar@385
    31
alpar@385
    32
namespace lemon {
alpar@385
    33
alpar@385
    34
  /// \addtogroup dimacs_group
alpar@385
    35
  /// @{
alpar@385
    36
alpar@387
    37
  /// DIMACS file type descriptor.
alpar@387
    38
  struct DimacsDescriptor
alpar@387
    39
  {
alpar@387
    40
    ///File type enum
alpar@387
    41
    enum Type
alpar@387
    42
      {
alpar@387
    43
        NONE, MIN, MAX, SP, MAT
alpar@387
    44
      };
alpar@387
    45
    ///The file type
alpar@387
    46
    Type type;
kpeter@388
    47
    ///The number of nodes in the graph
alpar@387
    48
    int nodeNum;
kpeter@388
    49
    ///The number of edges in the graph
alpar@387
    50
    int edgeNum;
alpar@387
    51
    int lineShift;
alpar@387
    52
    /// Constructor. Sets the type to NONE.
alpar@387
    53
    DimacsDescriptor() : type(NONE) {}
alpar@387
    54
  };
alpar@387
    55
alpar@387
    56
  ///Discover the type of a DIMACS file
alpar@387
    57
alpar@387
    58
  ///It starts seeking the begining of the file for the problem type
kpeter@388
    59
  ///and size info. The found data is returned in a special struct
alpar@387
    60
  ///that can be evaluated and passed to the appropriate reader
alpar@387
    61
  ///function.
alpar@387
    62
  DimacsDescriptor dimacsType(std::istream& is)
alpar@387
    63
  {
alpar@387
    64
    DimacsDescriptor r;
alpar@387
    65
    std::string problem,str;
alpar@387
    66
    char c;
alpar@387
    67
    r.lineShift=0;
alpar@387
    68
    while (is >> c)
alpar@387
    69
      switch(c)
alpar@387
    70
        {
alpar@387
    71
        case 'p':
alpar@387
    72
          if(is >> problem >> r.nodeNum >> r.edgeNum)
alpar@387
    73
            {
alpar@387
    74
              getline(is, str);
alpar@387
    75
              r.lineShift++;
alpar@387
    76
              if(problem=="min") r.type=DimacsDescriptor::MIN;
alpar@387
    77
              else if(problem=="max") r.type=DimacsDescriptor::MAX;
alpar@387
    78
              else if(problem=="sp") r.type=DimacsDescriptor::SP;
alpar@387
    79
              else if(problem=="mat") r.type=DimacsDescriptor::MAT;
alpar@387
    80
              else throw FormatError("Unknown problem type");
alpar@387
    81
              return r;
alpar@387
    82
            }
alpar@387
    83
          else
alpar@387
    84
            {
alpar@387
    85
              throw FormatError("Missing or wrong problem type declaration.");
alpar@387
    86
            }
alpar@387
    87
          break;
alpar@387
    88
        case 'c':
alpar@387
    89
          getline(is, str);
alpar@387
    90
          r.lineShift++;
alpar@387
    91
          break;
alpar@387
    92
        default:
alpar@387
    93
          throw FormatError("Unknown DIMACS declaration.");
alpar@387
    94
        }
alpar@387
    95
    throw FormatError("Missing problem type declaration.");
alpar@387
    96
  }
alpar@387
    97
alpar@387
    98
alpar@387
    99
kpeter@388
   100
  /// DIMACS minimum cost flow reader function.
alpar@385
   101
  ///
kpeter@388
   102
  /// This function reads a minimum cost flow instance from DIMACS format,
kpeter@388
   103
  /// i.e. from a DIMACS file having a line starting with
alpar@385
   104
  /// \code
alpar@385
   105
  ///   p min
alpar@385
   106
  /// \endcode
alpar@387
   107
  /// At the beginning, \c g is cleared by \c g.clear(). The supply
alpar@385
   108
  /// amount of the nodes are written to \c supply (signed). The
alpar@385
   109
  /// lower bounds, capacities and costs of the arcs are written to
alpar@385
   110
  /// \c lower, \c capacity and \c cost.
alpar@387
   111
  ///
alpar@387
   112
  /// If the file type was previously evaluated by dimacsType(), then
alpar@387
   113
  /// the descriptor struct should be given by the \c dest parameter.
alpar@385
   114
  template <typename Digraph, typename LowerMap,
alpar@387
   115
            typename CapacityMap, typename CostMap,
alpar@387
   116
            typename SupplyMap>
alpar@387
   117
  void readDimacsMin(std::istream& is,
alpar@387
   118
                     Digraph &g,
alpar@387
   119
                     LowerMap& lower,
alpar@387
   120
                     CapacityMap& capacity,
alpar@387
   121
                     CostMap& cost,
alpar@387
   122
                     SupplyMap& supply,
alpar@387
   123
                     DimacsDescriptor desc=DimacsDescriptor())
alpar@385
   124
  {
alpar@385
   125
    g.clear();
alpar@385
   126
    std::vector<typename Digraph::Node> nodes;
alpar@385
   127
    typename Digraph::Arc e;
alpar@385
   128
    std::string problem, str;
alpar@385
   129
    char c;
alpar@385
   130
    int i, j;
alpar@387
   131
    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
alpar@387
   132
    if(desc.type!=DimacsDescriptor::MIN)
alpar@387
   133
      throw FormatError("Problem type mismatch");
alpar@387
   134
alpar@387
   135
    nodes.resize(desc.nodeNum + 1);
alpar@387
   136
    for (int k = 1; k <= desc.nodeNum; ++k) {
alpar@387
   137
      nodes[k] = g.addNode();
alpar@387
   138
      supply.set(nodes[k], 0);
alpar@387
   139
    }
alpar@387
   140
alpar@385
   141
    typename SupplyMap::Value sup;
alpar@385
   142
    typename CapacityMap::Value low;
alpar@385
   143
    typename CapacityMap::Value cap;
alpar@385
   144
    typename CostMap::Value co;
alpar@385
   145
    while (is >> c) {
alpar@385
   146
      switch (c) {
alpar@385
   147
      case 'c': // comment line
alpar@385
   148
        getline(is, str);
alpar@385
   149
        break;
alpar@385
   150
      case 'n': // node definition line
alpar@385
   151
        is >> i >> sup;
alpar@385
   152
        getline(is, str);
alpar@385
   153
        supply.set(nodes[i], sup);
alpar@385
   154
        break;
alpar@385
   155
      case 'a': // arc (arc) definition line
alpar@385
   156
        is >> i >> j >> low >> cap >> co;
alpar@385
   157
        getline(is, str);
alpar@385
   158
        e = g.addArc(nodes[i], nodes[j]);
alpar@385
   159
        lower.set(e, low);
alpar@385
   160
        if (cap >= 0)
alpar@385
   161
          capacity.set(e, cap);
alpar@385
   162
        else
alpar@385
   163
          capacity.set(e, -1);
alpar@385
   164
        cost.set(e, co);
alpar@385
   165
        break;
alpar@385
   166
      }
alpar@385
   167
    }
alpar@385
   168
  }
alpar@385
   169
alpar@385
   170
  template<typename Digraph, typename CapacityMap>
alpar@387
   171
  void _readDimacs(std::istream& is,
alpar@387
   172
                   Digraph &g,
alpar@387
   173
                   CapacityMap& capacity,
alpar@387
   174
                   typename Digraph::Node &s,
alpar@387
   175
                   typename Digraph::Node &t,
alpar@387
   176
                   DimacsDescriptor desc=DimacsDescriptor()) {
alpar@385
   177
    g.clear();
alpar@387
   178
    s=t=INVALID;
alpar@385
   179
    std::vector<typename Digraph::Node> nodes;
alpar@385
   180
    typename Digraph::Arc e;
alpar@385
   181
    char c, d;
alpar@385
   182
    int i, j;
alpar@385
   183
    typename CapacityMap::Value _cap;
alpar@385
   184
    std::string str;
alpar@387
   185
    nodes.resize(desc.nodeNum + 1);
alpar@387
   186
    for (int k = 1; k <= desc.nodeNum; ++k) {
alpar@387
   187
      nodes[k] = g.addNode();
alpar@387
   188
    }
alpar@387
   189
alpar@385
   190
    while (is >> c) {
alpar@385
   191
      switch (c) {
alpar@385
   192
      case 'c': // comment line
alpar@385
   193
        getline(is, str);
alpar@385
   194
        break;
alpar@385
   195
      case 'n': // node definition line
alpar@387
   196
        if (desc.type==DimacsDescriptor::SP) { // shortest path problem
alpar@385
   197
          is >> i;
alpar@385
   198
          getline(is, str);
alpar@385
   199
          s = nodes[i];
alpar@385
   200
        }
alpar@387
   201
        if (desc.type==DimacsDescriptor::MAX) { // max flow problem
alpar@385
   202
          is >> i >> d;
alpar@385
   203
          getline(is, str);
alpar@385
   204
          if (d == 's') s = nodes[i];
alpar@385
   205
          if (d == 't') t = nodes[i];
alpar@385
   206
        }
alpar@385
   207
        break;
alpar@385
   208
      case 'a': // arc (arc) definition line
alpar@387
   209
        if (desc.type==DimacsDescriptor::SP ||
alpar@387
   210
            desc.type==DimacsDescriptor::MAX) {
alpar@385
   211
          is >> i >> j >> _cap;
alpar@385
   212
          getline(is, str);
alpar@385
   213
          e = g.addArc(nodes[i], nodes[j]);
alpar@385
   214
          capacity.set(e, _cap);
alpar@385
   215
        } else {
alpar@385
   216
          is >> i >> j;
alpar@385
   217
          getline(is, str);
alpar@385
   218
          g.addArc(nodes[i], nodes[j]);
alpar@385
   219
        }
alpar@385
   220
        break;
alpar@385
   221
      }
alpar@385
   222
    }
alpar@385
   223
  }
alpar@385
   224
kpeter@388
   225
  /// DIMACS maximum flow reader function.
alpar@387
   226
  ///
kpeter@388
   227
  /// This function reads a maximum flow instance from DIMACS format,
kpeter@388
   228
  /// i.e. from a DIMACS file having a line starting with
alpar@387
   229
  /// \code
alpar@387
   230
  ///   p max
alpar@387
   231
  /// \endcode
alpar@387
   232
  /// At the beginning, \c g is cleared by \c g.clear(). The arc
alpar@387
   233
  /// capacities are written to \c capacity and \c s and \c t are
alpar@387
   234
  /// set to the source and the target nodes.
alpar@387
   235
  ///
alpar@387
   236
  /// If the file type was previously evaluated by dimacsType(), then
alpar@387
   237
  /// the descriptor struct should be given by the \c dest parameter.
alpar@387
   238
  template<typename Digraph, typename CapacityMap>
alpar@387
   239
  void readDimacsMax(std::istream& is,
alpar@387
   240
                     Digraph &g,
alpar@387
   241
                     CapacityMap& capacity,
alpar@387
   242
                     typename Digraph::Node &s,
alpar@387
   243
                     typename Digraph::Node &t,
alpar@387
   244
                     DimacsDescriptor desc=DimacsDescriptor()) {
alpar@387
   245
    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
alpar@387
   246
    if(desc.type!=DimacsDescriptor::MAX)
alpar@387
   247
      throw FormatError("Problem type mismatch");
alpar@387
   248
    _readDimacs(is,g,capacity,s,t,desc);
alpar@387
   249
  }
alpar@387
   250
alpar@385
   251
  /// DIMACS shortest path reader function.
alpar@385
   252
  ///
alpar@385
   253
  /// This function reads a shortest path instance from DIMACS format,
kpeter@388
   254
  /// i.e. from a DIMACS file having a line starting with
alpar@385
   255
  /// \code
alpar@385
   256
  ///   p sp
alpar@385
   257
  /// \endcode
alpar@387
   258
  /// At the beginning, \c g is cleared by \c g.clear(). The arc
kpeter@388
   259
  /// lengths are written to \c length and \c s is set to the
alpar@385
   260
  /// source node.
alpar@387
   261
  ///
alpar@387
   262
  /// If the file type was previously evaluated by dimacsType(), then
alpar@387
   263
  /// the descriptor struct should be given by the \c dest parameter.
alpar@387
   264
  template<typename Digraph, typename LengthMap>
alpar@387
   265
  void readDimacsSp(std::istream& is,
alpar@387
   266
                    Digraph &g,
alpar@387
   267
                    LengthMap& length,
alpar@387
   268
                    typename Digraph::Node &s,
alpar@387
   269
                    DimacsDescriptor desc=DimacsDescriptor()) {
alpar@386
   270
    typename Digraph::Node t;
alpar@387
   271
    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
alpar@387
   272
    if(desc.type!=DimacsDescriptor::SP)
alpar@387
   273
      throw FormatError("Problem type mismatch");
alpar@387
   274
    _readDimacs(is, g, length, s, t,desc);
alpar@385
   275
  }
alpar@385
   276
alpar@385
   277
  /// DIMACS capacitated digraph reader function.
alpar@385
   278
  ///
alpar@385
   279
  /// This function reads an arc capacitated digraph instance from
alpar@387
   280
  /// DIMACS 'mat' or 'sp' format.
alpar@387
   281
  /// At the beginning, \c g is cleared by \c g.clear()
alpar@387
   282
  /// and the arc capacities/lengths are written to \c capacity.
alpar@387
   283
  ///
alpar@387
   284
  /// If the file type was previously evaluated by dimacsType(), then
alpar@387
   285
  /// the descriptor struct should be given by the \c dest parameter.
alpar@385
   286
  template<typename Digraph, typename CapacityMap>
alpar@387
   287
  void readDimacsCap(std::istream& is,
alpar@387
   288
                     Digraph &g,
alpar@387
   289
                     CapacityMap& capacity,
alpar@387
   290
                     DimacsDescriptor desc=DimacsDescriptor()) {
alpar@386
   291
    typename Digraph::Node u,v;
alpar@387
   292
    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
alpar@387
   293
    if(desc.type!=DimacsDescriptor::MAX || desc.type!=DimacsDescriptor::SP)
alpar@387
   294
      throw FormatError("Problem type mismatch");
alpar@387
   295
    _readDimacs(is, g, capacity, u, v, desc);
alpar@385
   296
  }
alpar@385
   297
alpar@525
   298
  template<typename Graph>
alpar@525
   299
  typename enable_if<lemon::UndirectedTagIndicator<Graph>,void>::type
alpar@525
   300
  _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t,
alpar@525
   301
              dummy<0> = 0)
alpar@525
   302
  {
alpar@525
   303
    g.addEdge(s,t);
alpar@525
   304
  }
alpar@525
   305
  template<typename Graph>
alpar@525
   306
  typename disable_if<lemon::UndirectedTagIndicator<Graph>,void>::type
alpar@525
   307
  _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t,
alpar@525
   308
              dummy<1> = 1)
alpar@525
   309
  {
alpar@525
   310
    g.addArc(s,t);
alpar@525
   311
  }
alpar@525
   312
  
alpar@525
   313
  /// DIMACS plain (di)graph reader function.
alpar@385
   314
  ///
alpar@525
   315
  /// This function reads a (di)graph without any designated nodes and
alpar@385
   316
  /// maps from DIMACS format, i.e. from DIMACS files having a line
alpar@385
   317
  /// starting with
alpar@385
   318
  /// \code
alpar@385
   319
  ///   p mat
alpar@385
   320
  /// \endcode
alpar@387
   321
  /// At the beginning, \c g is cleared by \c g.clear().
alpar@387
   322
  ///
alpar@387
   323
  /// If the file type was previously evaluated by dimacsType(), then
alpar@387
   324
  /// the descriptor struct should be given by the \c dest parameter.
alpar@525
   325
  template<typename Graph>
alpar@525
   326
  void readDimacsMat(std::istream& is, Graph &g,
alpar@525
   327
                     DimacsDescriptor desc=DimacsDescriptor())
alpar@525
   328
  {
alpar@387
   329
    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
alpar@387
   330
    if(desc.type!=DimacsDescriptor::MAT)
alpar@387
   331
      throw FormatError("Problem type mismatch");
alpar@525
   332
alpar@525
   333
    g.clear();
alpar@525
   334
    std::vector<typename Graph::Node> nodes;
alpar@525
   335
    char c;
alpar@525
   336
    int i, j;
alpar@525
   337
    std::string str;
alpar@525
   338
    nodes.resize(desc.nodeNum + 1);
alpar@525
   339
    for (int k = 1; k <= desc.nodeNum; ++k) {
alpar@525
   340
      nodes[k] = g.addNode();
alpar@525
   341
    }
alpar@525
   342
    
alpar@525
   343
    while (is >> c) {
alpar@525
   344
      switch (c) {
alpar@525
   345
      case 'c': // comment line
alpar@525
   346
        getline(is, str);
alpar@525
   347
        break;
alpar@525
   348
      case 'n': // node definition line
alpar@525
   349
        break;
alpar@525
   350
      case 'a': // arc (arc) definition line
alpar@525
   351
        is >> i >> j;
alpar@525
   352
        getline(is, str);
alpar@525
   353
        _addArcEdge(g,nodes[i], nodes[j]);
alpar@525
   354
        break;
alpar@525
   355
      }
alpar@525
   356
    }
alpar@385
   357
  }
alpar@385
   358
alpar@385
   359
  /// DIMACS plain digraph writer function.
alpar@385
   360
  ///
alpar@385
   361
  /// This function writes a digraph without any designated nodes and
alpar@385
   362
  /// maps into DIMACS format, i.e. into DIMACS file having a line
alpar@385
   363
  /// starting with
alpar@385
   364
  /// \code
alpar@385
   365
  ///   p mat
alpar@385
   366
  /// \endcode
alpar@387
   367
  /// If \c comment is not empty, then it will be printed in the first line
alpar@387
   368
  /// prefixed by 'c'.
alpar@385
   369
  template<typename Digraph>
alpar@387
   370
  void writeDimacsMat(std::ostream& os, const Digraph &g,
alpar@387
   371
                      std::string comment="") {
alpar@385
   372
    typedef typename Digraph::NodeIt NodeIt;
alpar@385
   373
    typedef typename Digraph::ArcIt ArcIt;
alpar@385
   374
alpar@440
   375
    if(!comment.empty())
alpar@387
   376
      os << "c " << comment << std::endl;
alpar@385
   377
    os << "p mat " << g.nodeNum() << " " << g.arcNum() << std::endl;
alpar@385
   378
alpar@385
   379
    typename Digraph::template NodeMap<int> nodes(g);
alpar@385
   380
    int i = 1;
alpar@385
   381
    for(NodeIt v(g); v != INVALID; ++v) {
alpar@385
   382
      nodes.set(v, i);
alpar@385
   383
      ++i;
alpar@385
   384
    }
alpar@385
   385
    for(ArcIt e(g); e != INVALID; ++e) {
alpar@385
   386
      os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)]
alpar@385
   387
         << std::endl;
alpar@385
   388
    }
alpar@385
   389
  }
alpar@385
   390
alpar@385
   391
  /// @}
alpar@385
   392
alpar@385
   393
} //namespace lemon
alpar@385
   394
alpar@385
   395
#endif //LEMON_DIMACS_H