1.1 --- a/lemon/dimacs.h Sun Mar 29 22:19:14 2009 +0100
1.2 +++ b/lemon/dimacs.h Mon Mar 30 16:46:37 2009 +0100
1.3 @@ -22,9 +22,9 @@
1.4 #include <iostream>
1.5 #include <string>
1.6 #include <vector>
1.7 +#include <limits>
1.8 #include <lemon/maps.h>
1.9 #include <lemon/error.h>
1.10 -
1.11 /// \ingroup dimacs_group
1.12 /// \file
1.13 /// \brief DIMACS file format reader.
1.14 @@ -55,7 +55,7 @@
1.15
1.16 ///Discover the type of a DIMACS file
1.17
1.18 - ///It starts seeking the begining of the file for the problem type
1.19 + ///It starts seeking the beginning of the file for the problem type
1.20 ///and size info. The found data is returned in a special struct
1.21 ///that can be evaluated and passed to the appropriate reader
1.22 ///function.
1.23 @@ -105,9 +105,17 @@
1.24 /// p min
1.25 /// \endcode
1.26 /// At the beginning, \c g is cleared by \c g.clear(). The supply
1.27 - /// amount of the nodes are written to \c supply (signed). The
1.28 - /// lower bounds, capacities and costs of the arcs are written to
1.29 - /// \c lower, \c capacity and \c cost.
1.30 + /// amount of the nodes are written to the \c supply node map
1.31 + /// (they are signed values). The lower bounds, capacities and costs
1.32 + /// of the arcs are written to the \c lower, \c capacity and \c cost
1.33 + /// arc maps.
1.34 + ///
1.35 + /// If the capacity of an arc is less than the lower bound, it will
1.36 + /// be set to "infinite" instead. The actual value of "infinite" is
1.37 + /// contolled by the \c infty parameter. If it is 0 (the default value),
1.38 + /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
1.39 + /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
1.40 + /// a non-zero value, that value will be used as "infinite".
1.41 ///
1.42 /// If the file type was previously evaluated by dimacsType(), then
1.43 /// the descriptor struct should be given by the \c dest parameter.
1.44 @@ -120,6 +128,7 @@
1.45 CapacityMap& capacity,
1.46 CostMap& cost,
1.47 SupplyMap& supply,
1.48 + typename CapacityMap::Value infty = 0,
1.49 DimacsDescriptor desc=DimacsDescriptor())
1.50 {
1.51 g.clear();
1.52 @@ -142,6 +151,12 @@
1.53 typename CapacityMap::Value low;
1.54 typename CapacityMap::Value cap;
1.55 typename CostMap::Value co;
1.56 + typedef typename CapacityMap::Value Capacity;
1.57 + if(infty==0)
1.58 + infty = std::numeric_limits<Capacity>::has_infinity ?
1.59 + std::numeric_limits<Capacity>::infinity() :
1.60 + std::numeric_limits<Capacity>::max();
1.61 +
1.62 while (is >> c) {
1.63 switch (c) {
1.64 case 'c': // comment line
1.65 @@ -152,15 +167,15 @@
1.66 getline(is, str);
1.67 supply.set(nodes[i], sup);
1.68 break;
1.69 - case 'a': // arc (arc) definition line
1.70 + case 'a': // arc definition line
1.71 is >> i >> j >> low >> cap >> co;
1.72 getline(is, str);
1.73 e = g.addArc(nodes[i], nodes[j]);
1.74 lower.set(e, low);
1.75 - if (cap >= 0)
1.76 + if (cap >= low)
1.77 capacity.set(e, cap);
1.78 else
1.79 - capacity.set(e, -1);
1.80 + capacity.set(e, infty);
1.81 cost.set(e, co);
1.82 break;
1.83 }
1.84 @@ -173,6 +188,7 @@
1.85 CapacityMap& capacity,
1.86 typename Digraph::Node &s,
1.87 typename Digraph::Node &t,
1.88 + typename CapacityMap::Value infty = 0,
1.89 DimacsDescriptor desc=DimacsDescriptor()) {
1.90 g.clear();
1.91 s=t=INVALID;
1.92 @@ -186,7 +202,13 @@
1.93 for (int k = 1; k <= desc.nodeNum; ++k) {
1.94 nodes[k] = g.addNode();
1.95 }
1.96 + typedef typename CapacityMap::Value Capacity;
1.97
1.98 + if(infty==0)
1.99 + infty = std::numeric_limits<Capacity>::has_infinity ?
1.100 + std::numeric_limits<Capacity>::infinity() :
1.101 + std::numeric_limits<Capacity>::max();
1.102 +
1.103 while (is >> c) {
1.104 switch (c) {
1.105 case 'c': // comment line
1.106 @@ -205,14 +227,23 @@
1.107 if (d == 't') t = nodes[i];
1.108 }
1.109 break;
1.110 - case 'a': // arc (arc) definition line
1.111 - if (desc.type==DimacsDescriptor::SP ||
1.112 - desc.type==DimacsDescriptor::MAX) {
1.113 + case 'a': // arc definition line
1.114 + if (desc.type==DimacsDescriptor::SP) {
1.115 is >> i >> j >> _cap;
1.116 getline(is, str);
1.117 e = g.addArc(nodes[i], nodes[j]);
1.118 capacity.set(e, _cap);
1.119 - } else {
1.120 + }
1.121 + else if (desc.type==DimacsDescriptor::MAX) {
1.122 + is >> i >> j >> _cap;
1.123 + getline(is, str);
1.124 + e = g.addArc(nodes[i], nodes[j]);
1.125 + if (_cap >= 0)
1.126 + capacity.set(e, _cap);
1.127 + else
1.128 + capacity.set(e, infty);
1.129 + }
1.130 + else {
1.131 is >> i >> j;
1.132 getline(is, str);
1.133 g.addArc(nodes[i], nodes[j]);
1.134 @@ -230,8 +261,15 @@
1.135 /// p max
1.136 /// \endcode
1.137 /// At the beginning, \c g is cleared by \c g.clear(). The arc
1.138 - /// capacities are written to \c capacity and \c s and \c t are
1.139 - /// set to the source and the target nodes.
1.140 + /// capacities are written to the \c capacity arc map and \c s and
1.141 + /// \c t are set to the source and the target nodes.
1.142 + ///
1.143 + /// If the capacity of an arc is negative, it will
1.144 + /// be set to "infinite" instead. The actual value of "infinite" is
1.145 + /// contolled by the \c infty parameter. If it is 0 (the default value),
1.146 + /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
1.147 + /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
1.148 + /// a non-zero value, that value will be used as "infinite".
1.149 ///
1.150 /// If the file type was previously evaluated by dimacsType(), then
1.151 /// the descriptor struct should be given by the \c dest parameter.
1.152 @@ -241,11 +279,12 @@
1.153 CapacityMap& capacity,
1.154 typename Digraph::Node &s,
1.155 typename Digraph::Node &t,
1.156 + typename CapacityMap::Value infty = 0,
1.157 DimacsDescriptor desc=DimacsDescriptor()) {
1.158 if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
1.159 if(desc.type!=DimacsDescriptor::MAX)
1.160 throw FormatError("Problem type mismatch");
1.161 - _readDimacs(is,g,capacity,s,t,desc);
1.162 + _readDimacs(is,g,capacity,s,t,infty,desc);
1.163 }
1.164
1.165 /// DIMACS shortest path reader function.
1.166 @@ -256,7 +295,7 @@
1.167 /// p sp
1.168 /// \endcode
1.169 /// At the beginning, \c g is cleared by \c g.clear(). The arc
1.170 - /// lengths are written to \c length and \c s is set to the
1.171 + /// lengths are written to the \c length arc map and \c s is set to the
1.172 /// source node.
1.173 ///
1.174 /// If the file type was previously evaluated by dimacsType(), then
1.175 @@ -271,15 +310,24 @@
1.176 if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
1.177 if(desc.type!=DimacsDescriptor::SP)
1.178 throw FormatError("Problem type mismatch");
1.179 - _readDimacs(is, g, length, s, t,desc);
1.180 + _readDimacs(is, g, length, s, t, 0, desc);
1.181 }
1.182
1.183 /// DIMACS capacitated digraph reader function.
1.184 ///
1.185 /// This function reads an arc capacitated digraph instance from
1.186 - /// DIMACS 'mat' or 'sp' format.
1.187 + /// DIMACS 'max' or 'sp' format.
1.188 /// At the beginning, \c g is cleared by \c g.clear()
1.189 - /// and the arc capacities/lengths are written to \c capacity.
1.190 + /// and the arc capacities/lengths are written to the \c capacity
1.191 + /// arc map.
1.192 + ///
1.193 + /// In case of the 'max' format, if the capacity of an arc is negative,
1.194 + /// it will
1.195 + /// be set to "infinite" instead. The actual value of "infinite" is
1.196 + /// contolled by the \c infty parameter. If it is 0 (the default value),
1.197 + /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
1.198 + /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
1.199 + /// a non-zero value, that value will be used as "infinite".
1.200 ///
1.201 /// If the file type was previously evaluated by dimacsType(), then
1.202 /// the descriptor struct should be given by the \c dest parameter.
1.203 @@ -287,12 +335,13 @@
1.204 void readDimacsCap(std::istream& is,
1.205 Digraph &g,
1.206 CapacityMap& capacity,
1.207 + typename CapacityMap::Value infty = 0,
1.208 DimacsDescriptor desc=DimacsDescriptor()) {
1.209 typename Digraph::Node u,v;
1.210 if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
1.211 if(desc.type!=DimacsDescriptor::MAX || desc.type!=DimacsDescriptor::SP)
1.212 throw FormatError("Problem type mismatch");
1.213 - _readDimacs(is, g, capacity, u, v, desc);
1.214 + _readDimacs(is, g, capacity, u, v, infty, desc);
1.215 }
1.216
1.217 template<typename Graph>
1.218 @@ -347,7 +396,7 @@
1.219 break;
1.220 case 'n': // node definition line
1.221 break;
1.222 - case 'a': // arc (arc) definition line
1.223 + case 'a': // arc definition line
1.224 is >> i >> j;
1.225 getline(is, str);
1.226 _addArcEdge(g,nodes[i], nodes[j]);
2.1 --- a/tools/dimacs-solver.cc Sun Mar 29 22:19:14 2009 +0100
2.2 +++ b/tools/dimacs-solver.cc Mon Mar 30 16:46:37 2009 +0100
2.3 @@ -72,7 +72,7 @@
2.4
2.5 template<class Value>
2.6 void solve_max(ArgParser &ap, std::istream &is, std::ostream &,
2.7 - DimacsDescriptor &desc)
2.8 + Value infty, DimacsDescriptor &desc)
2.9 {
2.10 bool report = !ap.given("q");
2.11 Digraph g;
2.12 @@ -80,7 +80,7 @@
2.13 Digraph::ArcMap<Value> cap(g);
2.14 Timer ti;
2.15 ti.restart();
2.16 - readDimacsMax(is, g, cap, s, t, desc);
2.17 + readDimacsMax(is, g, cap, s, t, infty, desc);
2.18 if(report) std::cerr << "Read the file: " << ti << '\n';
2.19 ti.restart();
2.20 Preflow<Digraph, Digraph::ArcMap<Value> > pre(g,cap,s,t);
2.21 @@ -115,6 +115,17 @@
2.22 void solve(ArgParser &ap, std::istream &is, std::ostream &os,
2.23 DimacsDescriptor &desc)
2.24 {
2.25 + std::stringstream iss(ap["infcap"]);
2.26 + Value infty;
2.27 + iss >> infty;
2.28 + if(iss.fail())
2.29 + {
2.30 + std::cerr << "Cannot interpret '"
2.31 + << static_cast<std::string>(ap["infcap"]) << "' as infinite"
2.32 + << std::endl;
2.33 + exit(1);
2.34 + }
2.35 +
2.36 switch(desc.type)
2.37 {
2.38 case DimacsDescriptor::MIN:
2.39 @@ -122,7 +133,7 @@
2.40 "\n\n Sorry, the min. cost flow solver is not yet available.\n";
2.41 break;
2.42 case DimacsDescriptor::MAX:
2.43 - solve_max<Value>(ap,is,os,desc);
2.44 + solve_max<Value>(ap,is,os,infty,desc);
2.45 break;
2.46 case DimacsDescriptor::SP:
2.47 solve_sp<Value>(ap,is,os,desc);
2.48 @@ -159,6 +170,7 @@
2.49 .boolOption("ldouble","Use 'long double' for capacities, costs etc.")
2.50 .optionGroup("datatype","ldouble")
2.51 .onlyOneGroup("datatype")
2.52 + .stringOption("infcap","Value used for 'very high' capacities","0")
2.53 .run();
2.54
2.55 std::ifstream input;
3.1 --- a/tools/dimacs-to-lgf.cc Sun Mar 29 22:19:14 2009 +0100
3.2 +++ b/tools/dimacs-to-lgf.cc Mon Mar 30 16:46:37 2009 +0100
3.3 @@ -96,7 +96,7 @@
3.4 Digraph digraph;
3.5 DoubleArcMap lower(digraph), capacity(digraph), cost(digraph);
3.6 DoubleNodeMap supply(digraph);
3.7 - readDimacsMin(is, digraph, lower, capacity, cost, supply, desc);
3.8 + readDimacsMin(is, digraph, lower, capacity, cost, supply, 0, desc);
3.9 DigraphWriter<Digraph>(digraph, os).
3.10 nodeMap("supply", supply).
3.11 arcMap("lower", lower).
3.12 @@ -111,7 +111,7 @@
3.13 Digraph digraph;
3.14 Node s, t;
3.15 DoubleArcMap capacity(digraph);
3.16 - readDimacsMax(is, digraph, capacity, s, t, desc);
3.17 + readDimacsMax(is, digraph, capacity, s, t, 0, desc);
3.18 DigraphWriter<Digraph>(digraph, os).
3.19 arcMap("capacity", capacity).
3.20 node("source", s).