LEMON/LEMON-main Changeset - r561:6e0525ec5355

Repositories » LEMON » LEMON-main

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r561:6e0525ec5355

« 560:49a39b

562:538b3d »

r561:6e0525ec5355

Mon, 30 Mar 2009 17:46:37

[Not Reviewed]

0 comments (0 inline)

alpar (Alpar Juttner)
alpar@cs.elte.hu

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

0 3 0

default

3 files changed with 87 insertions and 26 deletions:

lemon/dimacs.h

tools/dimacs-solver.cc

tools/dimacs-to-lgf.cc

↑ Collapse diff ↑

lemon/dimacs.h

Show inline comments

@@ -23,7 +23,7 @@
 		#include <string>
 		#include <vector>
 		#include <limits>
 		#include <lemon/maps.h>
 		#include <lemon/error.h>
 		/// \ingroup dimacs_group
 		/// \file
@@ -56,5 +56,5 @@
 		  ///Discover the type of a DIMACS file
-		  ///It starts seeking the begining of the file for the problem type
+		  ///It starts seeking the beginning of the file for the problem type
 		  ///and size info. The found data is returned in a special struct
 		  ///that can be evaluated and passed to the appropriate reader
@@ -106,7 +106,15 @@
 		  /// \endcode
 		  /// At the beginning, \c g is cleared by \c g.clear(). The supply
 		  /// amount of the nodes are written to \c supply (signed). The
 		  /// lower bounds, capacities and costs of the arcs are written to
-		  /// \c lower, \c capacity and \c cost.
+		  /// amount of the nodes are written to the \c supply node map
 		  /// (they are signed values). The lower bounds, capacities and costs
 		  /// of the arcs are written to the \c lower, \c capacity and \c cost
 		  /// arc maps.
 		  ///
 		  /// If the capacity of an arc is less than the lower bound, it will
 		  /// be set to "infinite" instead. The actual value of "infinite" is
 		  /// contolled by the \c infty parameter. If it is 0 (the default value),
 		  /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
 		  /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
 		  /// a non-zero value, that value will be used as "infinite".
 		  ///
 		  /// If the file type was previously evaluated by dimacsType(), then
@@ -121,4 +129,5 @@
 		                     CostMap& cost,
 		                     SupplyMap& supply,
 		                     typename CapacityMap::Value infty = 0,
 		                     DimacsDescriptor desc=DimacsDescriptor())
+		  {
@@ -143,4 +152,10 @@
 		    typename CapacityMap::Value cap;
 		    typename CostMap::Value co;
 		    typedef typename CapacityMap::Value Capacity;
 		    if(infty==0)
 		      infty = std::numeric_limits<Capacity>::has_infinity ?
 		        std::numeric_limits<Capacity>::infinity() :
 		        std::numeric_limits<Capacity>::max();
 		    while (is >> c) {
 		      switch (c) {
@@ -153,13 +168,13 @@
 		        supply.set(nodes[i], sup);
 		        break;
-		      case 'a': // arc (arc) definition line
 		      case 'a': // arc definition line
 		        is >> i >> j >> low >> cap >> co;
 		        getline(is, str);
 		        e = g.addArc(nodes[i], nodes[j]);
 		        lower.set(e, low);
-		        if (cap >= 0)
+		        if (cap >= low)
 		          capacity.set(e, cap);
 		        else
-		          capacity.set(e, -1);
+		          capacity.set(e, infty);
 		        cost.set(e, co);
 		        break;
@@ -174,4 +189,5 @@
 		                   typename Digraph::Node &s,
 		                   typename Digraph::Node &t,
 		                   typename CapacityMap::Value infty = 0,
 		                   DimacsDescriptor desc=DimacsDescriptor()) {
 		    g.clear();
@@ -187,5 +203,11 @@
 		      nodes[k] = g.addNode();
+		    }
 		    typedef typename CapacityMap::Value Capacity;
 		    if(infty==0)
 		      infty = std::numeric_limits<Capacity>::has_infinity ?
 		        std::numeric_limits<Capacity>::infinity() :
 		        std::numeric_limits<Capacity>::max();
 		    while (is >> c) {
 		      switch (c) {
@@ -206,12 +228,21 @@
+		        }
 		        break;
 		      case 'a': // arc (arc) definition line
 		        if (desc.type==DimacsDescriptor::SP ||
-		            desc.type==DimacsDescriptor::MAX) {
+		      case 'a': // arc definition line
 		        if (desc.type==DimacsDescriptor::SP) {
 		          is >> i >> j >> _cap;
 		          getline(is, str);
 		          e = g.addArc(nodes[i], nodes[j]);
 		          capacity.set(e, _cap);
-		        } else {
+		        }
 		        else if (desc.type==DimacsDescriptor::MAX) {
 		          is >> i >> j >> _cap;
 		          getline(is, str);
 		          e = g.addArc(nodes[i], nodes[j]);
 		          if (_cap >= 0)
 		            capacity.set(e, _cap);
 		          else
 		            capacity.set(e, infty);
+		        }
 		        else {
 		          is >> i >> j;
 		          getline(is, str);
@@ -231,6 +262,13 @@
 		  /// \endcode
 		  /// At the beginning, \c g is cleared by \c g.clear(). The arc
 		  /// capacities are written to \c capacity and \c s and \c t are
 		  /// set to the source and the target nodes.
 		  /// capacities are written to the \c capacity arc map and \c s and
 		  /// \c t are set to the source and the target nodes.
 		  ///
 		  /// If the capacity of an arc is negative, it will
 		  /// be set to "infinite" instead. The actual value of "infinite" is
 		  /// contolled by the \c infty parameter. If it is 0 (the default value),
 		  /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
 		  /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
 		  /// a non-zero value, that value will be used as "infinite".
 		  ///
 		  /// If the file type was previously evaluated by dimacsType(), then
@@ -242,9 +280,10 @@
 		                     typename Digraph::Node &s,
 		                     typename Digraph::Node &t,
 		                     typename CapacityMap::Value infty = 0,
 		                     DimacsDescriptor desc=DimacsDescriptor()) {
 		    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
 		    if(desc.type!=DimacsDescriptor::MAX)
 		      throw FormatError("Problem type mismatch");
 		    _readDimacs(is,g,capacity,s,t,desc);
+		    _readDimacs(is,g,capacity,s,t,infty,desc);
+		  }
@@ -257,5 +296,5 @@
 		  /// \endcode
 		  /// At the beginning, \c g is cleared by \c g.clear(). The arc
 		  /// lengths are written to \c length and \c s is set to the
+		  /// lengths are written to the \c length arc map and \c s is set to the
 		  /// source node.
 		  ///
@@ -272,5 +311,5 @@
 		    if(desc.type!=DimacsDescriptor::SP)
 		      throw FormatError("Problem type mismatch");
 		    _readDimacs(is, g, length, s, t,desc);
+		    _readDimacs(is, g, length, s, t, 0, desc);
+		  }
@@ -278,7 +317,16 @@
 		  ///
 		  /// This function reads an arc capacitated digraph instance from
-		  /// DIMACS 'mat' or 'sp' format.
+		  /// DIMACS 'max' or 'sp' format.
 		  /// At the beginning, \c g is cleared by \c g.clear()
-		  /// and the arc capacities/lengths are written to \c capacity.
+		  /// and the arc capacities/lengths are written to the \c capacity
 		  /// arc map.
 		  ///
 		  /// In case of the 'max' format, if the capacity of an arc is negative,
 		  /// it will
 		  /// be set to "infinite" instead. The actual value of "infinite" is
 		  /// contolled by the \c infty parameter. If it is 0 (the default value),
 		  /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
 		  /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
 		  /// a non-zero value, that value will be used as "infinite".
 		  ///
 		  /// If the file type was previously evaluated by dimacsType(), then
@@ -288,4 +336,5 @@
 		                     Digraph &g,
 		                     CapacityMap& capacity,
 		                     typename CapacityMap::Value infty = 0,
 		                     DimacsDescriptor desc=DimacsDescriptor()) {
 		    typename Digraph::Node u,v;
@@ -293,5 +342,5 @@
 		    if(desc.type!=DimacsDescriptor::MAX || desc.type!=DimacsDescriptor::SP)
 		      throw FormatError("Problem type mismatch");
 		    _readDimacs(is, g, capacity, u, v, desc);
+		    _readDimacs(is, g, capacity, u, v, infty, desc);
+		  }
@@ -348,5 +397,5 @@
 		      case 'n': // node definition line
 		        break;
-		      case 'a': // arc (arc) definition line
 		      case 'a': // arc definition line
 		        is >> i >> j;
 		        getline(is, str);

tools/dimacs-solver.cc

Show inline comments

@@ -73,5 +73,5 @@
 		template<class Value>
 		void solve_max(ArgParser &ap, std::istream &is, std::ostream &,
 		              DimacsDescriptor &desc)
+		               Value infty, DimacsDescriptor &desc)
+		{
 		  bool report = !ap.given("q");
@@ -81,5 +81,5 @@
 		  Timer ti;
 		  ti.restart();
 		  readDimacsMax(is, g, cap, s, t, desc);
+		  readDimacsMax(is, g, cap, s, t, infty, desc);
 		  if(report) std::cerr << "Read the file: " << ti << '\n';
 		  ti.restart();
@@ -116,4 +116,15 @@
 		           DimacsDescriptor &desc)
+		{
 		  std::stringstream iss(ap["infcap"]);
 		  Value infty;
 		  iss >> infty;
 		  if(iss.fail())
+		    {
 		      std::cerr << "Cannot interpret '"
 		                << static_cast<std::string>(ap["infcap"]) << "' as infinite"
 		                << std::endl;
 		      exit(1);
+		    }
 		  switch(desc.type)
+		    {
@@ -123,5 +134,5 @@
 		      break;
 		    case DimacsDescriptor::MAX:
 		      solve_max<Value>(ap,is,os,desc);
+		      solve_max<Value>(ap,is,os,infty,desc);
 		      break;
 		    case DimacsDescriptor::SP:
@@ -160,4 +171,5 @@
 		    .optionGroup("datatype","ldouble")
 		    .onlyOneGroup("datatype")
 		    .stringOption("infcap","Value used for 'very high' capacities","0")
 		    .run();

tools/dimacs-to-lgf.cc

Show inline comments

@@ -97,5 +97,5 @@
 		        DoubleArcMap lower(digraph), capacity(digraph), cost(digraph);
 		        DoubleNodeMap supply(digraph);
 		        readDimacsMin(is, digraph, lower, capacity, cost, supply, desc);
+		        readDimacsMin(is, digraph, lower, capacity, cost, supply, 0, desc);
 		        DigraphWriter<Digraph>(digraph, os).
 		          nodeMap("supply", supply).
@@ -112,5 +112,5 @@
 		        Node s, t;
 		        DoubleArcMap capacity(digraph);
 		        readDimacsMax(is, digraph, capacity, s, t, desc);
+		        readDimacsMax(is, digraph, capacity, s, t, 0, desc);
 		        DigraphWriter<Digraph>(digraph, os).
 		          arcMap("capacity", capacity).

0 comments (0 inline)

RhodeCode

Login to your account