COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 561:6e0525ec5355 in lemon-main


Ignore:
Timestamp:
03/30/09 17:46:37 (16 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Children:
562:538b3dd9a2c0, 1158:f37f0845cf32
Phase:
public
Message:

Accept negative values as unbounded capacity in dimacs readers (#243)
and some doc improvements.

Files:
3 edited

Legend:

Unmodified
Added
Removed

  • lemon/dimacs.h

    r525 r561  
    2323#include <string>
    2424#include <vector>
     25#include <limits>
    2526#include <lemon/maps.h>
    2627#include <lemon/error.h>
    27 
    2828/// \ingroup dimacs_group
    2929/// \file
    … …  
    5656  ///Discover the type of a DIMACS file
    5757
    58   ///It starts seeking the begining of the file for the problem type
     58  ///It starts seeking the beginning of the file for the problem type
    5959  ///and size info. The found data is returned in a special struct
    6060  ///that can be evaluated and passed to the appropriate reader
    … …  
    106106  /// \endcode
    107107  /// At the beginning, \c g is cleared by \c g.clear(). The supply
    108   /// amount of the nodes are written to \c supply (signed). The
    109   /// lower bounds, capacities and costs of the arcs are written to
    110   /// \c lower, \c capacity and \c cost.
     108  /// amount of the nodes are written to the \c supply node map
     109  /// (they are signed values). The lower bounds, capacities and costs
     110  /// of the arcs are written to the \c lower, \c capacity and \c cost
     111  /// arc maps.
     112  ///
     113  /// If the capacity of an arc is less than the lower bound, it will
     114  /// be set to "infinite" instead. The actual value of "infinite" is
     115  /// contolled by the \c infty parameter. If it is 0 (the default value),
     116  /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
     117  /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
     118  /// a non-zero value, that value will be used as "infinite".
    111119  ///
    112120  /// If the file type was previously evaluated by dimacsType(), then
    … …  
    121129                     CostMap& cost,
    122130                     SupplyMap& supply,
     131                     typename CapacityMap::Value infty = 0,
    123132                     DimacsDescriptor desc=DimacsDescriptor())
    124133  {
    … …  
    143152    typename CapacityMap::Value cap;
    144153    typename CostMap::Value co;
     154    typedef typename CapacityMap::Value Capacity;
     155    if(infty==0)
     156      infty = std::numeric_limits<Capacity>::has_infinity ?
     157        std::numeric_limits<Capacity>::infinity() :
     158        std::numeric_limits<Capacity>::max();
     159
    145160    while (is >> c) {
    146161      switch (c) {
    … …  
    153168        supply.set(nodes[i], sup);
    154169        break;
    155       case 'a': // arc (arc) definition line
     170      case 'a': // arc definition line
    156171        is >> i >> j >> low >> cap >> co;
    157172        getline(is, str);
    158173        e = g.addArc(nodes[i], nodes[j]);
    159174        lower.set(e, low);
    160         if (cap >= 0)
     175        if (cap >= low)
    161176          capacity.set(e, cap);
    162177        else
    163           capacity.set(e, -1);
     178          capacity.set(e, infty);
    164179        cost.set(e, co);
    165180        break;
    … …  
    174189                   typename Digraph::Node &s,
    175190                   typename Digraph::Node &t,
     191                   typename CapacityMap::Value infty = 0,
    176192                   DimacsDescriptor desc=DimacsDescriptor()) {
    177193    g.clear();
    … …  
    187203      nodes[k] = g.addNode();
    188204    }
    189 
     205    typedef typename CapacityMap::Value Capacity;
     206
     207    if(infty==0)
     208      infty = std::numeric_limits<Capacity>::has_infinity ?
     209        std::numeric_limits<Capacity>::infinity() :
     210        std::numeric_limits<Capacity>::max();
     211 
    190212    while (is >> c) {
    191213      switch (c) {
    … …  
    206228        }
    207229        break;
    208       case 'a': // arc (arc) definition line
    209         if (desc.type==DimacsDescriptor::SP ||
    210             desc.type==DimacsDescriptor::MAX) {
     230      case 'a': // arc definition line
     231        if (desc.type==DimacsDescriptor::SP) {
    211232          is >> i >> j >> _cap;
    212233          getline(is, str);
    213234          e = g.addArc(nodes[i], nodes[j]);
    214235          capacity.set(e, _cap);
    215         } else {
     236        }
     237        else if (desc.type==DimacsDescriptor::MAX) {
     238          is >> i >> j >> _cap;
     239          getline(is, str);
     240          e = g.addArc(nodes[i], nodes[j]);
     241          if (_cap >= 0)
     242            capacity.set(e, _cap);
     243          else
     244            capacity.set(e, infty);
     245        }
     246        else {
    216247          is >> i >> j;
    217248          getline(is, str);
    … …  
    231262  /// \endcode
    232263  /// At the beginning, \c g is cleared by \c g.clear(). The arc
    233   /// capacities are written to \c capacity and \c s and \c t are
    234   /// set to the source and the target nodes.
     264  /// capacities are written to the \c capacity arc map and \c s and
     265  /// \c t are set to the source and the target nodes.
     266  ///
     267  /// If the capacity of an arc is negative, it will
     268  /// be set to "infinite" instead. The actual value of "infinite" is
     269  /// contolled by the \c infty parameter. If it is 0 (the default value),
     270  /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
     271  /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
     272  /// a non-zero value, that value will be used as "infinite".
    235273  ///
    236274  /// If the file type was previously evaluated by dimacsType(), then
    … …  
    242280                     typename Digraph::Node &s,
    243281                     typename Digraph::Node &t,
     282                     typename CapacityMap::Value infty = 0,
    244283                     DimacsDescriptor desc=DimacsDescriptor()) {
    245284    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
    246285    if(desc.type!=DimacsDescriptor::MAX)
    247286      throw FormatError("Problem type mismatch");
    248     _readDimacs(is,g,capacity,s,t,desc);
     287    _readDimacs(is,g,capacity,s,t,infty,desc);
    249288  }
    250289
    … …  
    257296  /// \endcode
    258297  /// At the beginning, \c g is cleared by \c g.clear(). The arc
    259   /// lengths are written to \c length and \c s is set to the
     298  /// lengths are written to the \c length arc map and \c s is set to the
    260299  /// source node.
    261300  ///
    … …  
    272311    if(desc.type!=DimacsDescriptor::SP)
    273312      throw FormatError("Problem type mismatch");
    274     _readDimacs(is, g, length, s, t,desc);
     313    _readDimacs(is, g, length, s, t, 0, desc);
    275314  }
    276315
    … …  
    278317  ///
    279318  /// This function reads an arc capacitated digraph instance from
    280   /// DIMACS 'mat' or 'sp' format.
     319  /// DIMACS 'max' or 'sp' format.
    281320  /// At the beginning, \c g is cleared by \c g.clear()
    282   /// and the arc capacities/lengths are written to \c capacity.
     321  /// and the arc capacities/lengths are written to the \c capacity
     322  /// arc map.
     323  ///
     324  /// In case of the 'max' format, if the capacity of an arc is negative,
     325  /// it will
     326  /// be set to "infinite" instead. The actual value of "infinite" is
     327  /// contolled by the \c infty parameter. If it is 0 (the default value),
     328  /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
     329  /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
     330  /// a non-zero value, that value will be used as "infinite".
    283331  ///
    284332  /// If the file type was previously evaluated by dimacsType(), then
    … …  
    288336                     Digraph &g,
    289337                     CapacityMap& capacity,
     338                     typename CapacityMap::Value infty = 0,
    290339                     DimacsDescriptor desc=DimacsDescriptor()) {
    291340    typename Digraph::Node u,v;
    … …  
    293342    if(desc.type!=DimacsDescriptor::MAX || desc.type!=DimacsDescriptor::SP)
    294343      throw FormatError("Problem type mismatch");
    295     _readDimacs(is, g, capacity, u, v, desc);
     344    _readDimacs(is, g, capacity, u, v, infty, desc);
    296345  }
    297346
    … …  
    348397      case 'n': // node definition line
    349398        break;
    350       case 'a': // arc (arc) definition line
     399      case 'a': // arc definition line
    351400        is >> i >> j;
    352401        getline(is, str);

  • tools/dimacs-solver.cc

    r532 r561  
    7373template<class Value>
    7474void solve_max(ArgParser &ap, std::istream &is, std::ostream &,
    75               DimacsDescriptor &desc)
     75               Value infty, DimacsDescriptor &desc)
    7676{
    7777  bool report = !ap.given("q");
    … …  
    8181  Timer ti;
    8282  ti.restart();
    83   readDimacsMax(is, g, cap, s, t, desc);
     83  readDimacsMax(is, g, cap, s, t, infty, desc);
    8484  if(report) std::cerr << "Read the file: " << ti << '\n';
    8585  ti.restart();
    … …  
    116116           DimacsDescriptor &desc)
    117117{
     118  std::stringstream iss(ap["infcap"]);
     119  Value infty;
     120  iss >> infty;
     121  if(iss.fail())
     122    {
     123      std::cerr << "Cannot interpret '"
     124                << static_cast<std::string>(ap["infcap"]) << "' as infinite"
     125                << std::endl;
     126      exit(1);
     127    }
     128 
    118129  switch(desc.type)
    119130    {
    … …  
    123134      break;
    124135    case DimacsDescriptor::MAX:
    125       solve_max<Value>(ap,is,os,desc);
     136      solve_max<Value>(ap,is,os,infty,desc);
    126137      break;
    127138    case DimacsDescriptor::SP:
    … …  
    160171    .optionGroup("datatype","ldouble")
    161172    .onlyOneGroup("datatype")
     173    .stringOption("infcap","Value used for 'very high' capacities","0")
    162174    .run();
    163175

  • tools/dimacs-to-lgf.cc

    r440 r561  
    9797        DoubleArcMap lower(digraph), capacity(digraph), cost(digraph);
    9898        DoubleNodeMap supply(digraph);
    99         readDimacsMin(is, digraph, lower, capacity, cost, supply, desc);
     99        readDimacsMin(is, digraph, lower, capacity, cost, supply, 0, desc);
    100100        DigraphWriter<Digraph>(digraph, os).
    101101          nodeMap("supply", supply).
    … …  
    112112        Node s, t;
    113113        DoubleArcMap capacity(digraph);
    114         readDimacsMax(is, digraph, capacity, s, t, desc);
     114        readDimacsMax(is, digraph, capacity, s, t, 0, desc);
    115115        DigraphWriter<Digraph>(digraph, os).
    116116          arcMap("capacity", capacity).
Note: See TracChangeset for help on using the changeset viewer.