# HG changeset patch
# User Alpar Juttner <alpar@cs.elte.hu>
# Date 1238427997 -3600
# Node ID 6e0525ec5355243555def854496159f61034a1ae
# Parent 49a39bae067c4eca487e09c782ab3edba172b030
Accept negative values as unbounded capacity in dimacs readers (#243)
and some doc improvements.
diff -r 49a39bae067c -r 6e0525ec5355 lemon/dimacs.h
--- a/lemon/dimacs.h Sun Mar 29 22:19:14 2009 +0100
+++ b/lemon/dimacs.h Mon Mar 30 16:46:37 2009 +0100
@@ -22,9 +22,9 @@
#include <iostream>
#include <string>
#include <vector>
+#include <limits>
#include <lemon/maps.h>
#include <lemon/error.h>
-
/// \ingroup dimacs_group
/// \file
/// \brief DIMACS file format reader.
@@ -55,7 +55,7 @@
///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
///function.
@@ -105,9 +105,17 @@
/// p min
/// \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
/// the descriptor struct should be given by the \c dest parameter.
@@ -120,6 +128,7 @@
CapacityMap& capacity,
CostMap& cost,
SupplyMap& supply,
+ typename CapacityMap::Value infty = 0,
DimacsDescriptor desc=DimacsDescriptor())
{
g.clear();
@@ -142,6 +151,12 @@
typename CapacityMap::Value low;
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) {
case 'c': // comment line
@@ -152,15 +167,15 @@
getline(is, str);
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;
}
@@ -173,6 +188,7 @@
CapacityMap& capacity,
typename Digraph::Node &s,
typename Digraph::Node &t,
+ typename CapacityMap::Value infty = 0,
DimacsDescriptor desc=DimacsDescriptor()) {
g.clear();
s=t=INVALID;
@@ -186,7 +202,13 @@
for (int k = 1; k <= desc.nodeNum; ++k) {
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) {
case 'c': // comment line
@@ -205,14 +227,23 @@
if (d == 't') t = nodes[i];
}
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);
g.addArc(nodes[i], nodes[j]);
@@ -230,8 +261,15 @@
/// p max
/// \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
/// the descriptor struct should be given by the \c dest parameter.
@@ -241,11 +279,12 @@
CapacityMap& capacity,
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);
}
/// DIMACS shortest path reader function.
@@ -256,7 +295,7 @@
/// p sp
/// \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.
///
/// If the file type was previously evaluated by dimacsType(), then
@@ -271,15 +310,24 @@
if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
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);
}
/// DIMACS capacitated digraph reader function.
///
/// 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
/// the descriptor struct should be given by the \c dest parameter.
@@ -287,12 +335,13 @@
void readDimacsCap(std::istream& is,
Digraph &g,
CapacityMap& capacity,
+ typename CapacityMap::Value infty = 0,
DimacsDescriptor desc=DimacsDescriptor()) {
typename Digraph::Node u,v;
if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
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);
}
template<typename Graph>
@@ -347,7 +396,7 @@
break;
case 'n': // node definition line
break;
- case 'a': // arc (arc) definition line
+ case 'a': // arc definition line
is >> i >> j;
getline(is, str);
_addArcEdge(g,nodes[i], nodes[j]);
diff -r 49a39bae067c -r 6e0525ec5355 tools/dimacs-solver.cc
--- a/tools/dimacs-solver.cc Sun Mar 29 22:19:14 2009 +0100
+++ b/tools/dimacs-solver.cc Mon Mar 30 16:46:37 2009 +0100
@@ -72,7 +72,7 @@
template<class Value>
void solve_max(ArgParser &ap, std::istream &is, std::ostream &,
- DimacsDescriptor &desc)
+ Value infty, DimacsDescriptor &desc)
{
bool report = !ap.given("q");
Digraph g;
@@ -80,7 +80,7 @@
Digraph::ArcMap<Value> cap(g);
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();
Preflow<Digraph, Digraph::ArcMap<Value> > pre(g,cap,s,t);
@@ -115,6 +115,17 @@
void solve(ArgParser &ap, std::istream &is, std::ostream &os,
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)
{
case DimacsDescriptor::MIN:
@@ -122,7 +133,7 @@
"\n\n Sorry, the min. cost flow solver is not yet available.\n";
break;
case DimacsDescriptor::MAX:
- solve_max<Value>(ap,is,os,desc);
+ solve_max<Value>(ap,is,os,infty,desc);
break;
case DimacsDescriptor::SP:
solve_sp<Value>(ap,is,os,desc);
@@ -159,6 +170,7 @@
.boolOption("ldouble","Use 'long double' for capacities, costs etc.")
.optionGroup("datatype","ldouble")
.onlyOneGroup("datatype")
+ .stringOption("infcap","Value used for 'very high' capacities","0")
.run();
std::ifstream input;
diff -r 49a39bae067c -r 6e0525ec5355 tools/dimacs-to-lgf.cc
--- a/tools/dimacs-to-lgf.cc Sun Mar 29 22:19:14 2009 +0100
+++ b/tools/dimacs-to-lgf.cc Mon Mar 30 16:46:37 2009 +0100
@@ -96,7 +96,7 @@
Digraph digraph;
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).
arcMap("lower", lower).
@@ -111,7 +111,7 @@
Digraph digraph;
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).
node("source", s).