lemon-main: comparison lemon/dimacs.h

equal deleted inserted replaced

-:1ba012539556
+:f5735f366c22
 #define LEMON_DIMACS_H
 #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.
 namespace lemon {
 DimacsDescriptor() : type(NONE) {}
 };
 ///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.
 DimacsDescriptor dimacsType(std::istream& is)
 {
 /// i.e. from a DIMACS file having a line starting with
 /// \code
 ///   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
+/// amount of the nodes are written to the \c supply node map
-/// lower bounds, capacities and costs of the arcs are written to
+/// (they are signed values). The lower bounds, capacities and costs
-/// \c lower, \c capacity and \c cost.
+/// 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.
 template <typename Digraph, typename LowerMap,
 typename CapacityMap, typename CostMap,
 Digraph &g,
 LowerMap& lower,
 CapacityMap& capacity,
 CostMap& cost,
 SupplyMap& supply,
+typename CapacityMap::Value infty = 0,
 DimacsDescriptor desc=DimacsDescriptor())
 {
 g.clear();
 std::vector<typename Digraph::Node> nodes;
 typename Digraph::Arc e;
 typename SupplyMap::Value sup;
 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
 getline(is, str);
 break;
 case 'n': // node definition line
 is >> i >> sup;
 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;
 }
 }
 }
 void _readDimacs(std::istream& is,
 Digraph &g,
 CapacityMap& capacity,
 typename Digraph::Node &s,
 typename Digraph::Node &t,
+typename CapacityMap::Value infty = 0,
 DimacsDescriptor desc=DimacsDescriptor()) {
 g.clear();
 s=t=INVALID;
 std::vector<typename Digraph::Node> nodes;
 typename Digraph::Arc e;
 std::string str;
 nodes.resize(desc.nodeNum + 1);
 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
 getline(is, str);
 break;
 getline(is, str);
 if (d == 's') s = nodes[i];
 if (d == 't') t = nodes[i];
 }
 break;
-case 'a': // arc (arc) definition line
+case 'a': // arc definition line
-if (desc.type==DimacsDescriptor::SP ||
+if (desc.type==DimacsDescriptor::SP) {
-desc.type==DimacsDescriptor::MAX) {
 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]);
 }
 break;
 /// i.e. from a DIMACS file having a line starting with
 /// \code
 ///   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
+/// capacities are written to the \c capacity arc map and \c s and
-/// set to the source and the target nodes.
+/// \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.
 template<typename Digraph, typename CapacityMap>
 void readDimacsMax(std::istream& is,
 Digraph &g,
 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.
 ///
 /// This function reads a shortest path instance from DIMACS format,
 /// i.e. from a DIMACS file having a line starting with
 /// \code
 ///   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
 /// the descriptor struct should be given by the \c dest parameter.
 template<typename Digraph, typename LengthMap>
 DimacsDescriptor desc=DimacsDescriptor()) {
 typename Digraph::Node t;
 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.
 template<typename Digraph, typename CapacityMap>
 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>
 typename enable_if<lemon::UndirectedTagIndicator<Graph>,void>::type
 _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t,
 case 'c': // comment line
 getline(is, str);
 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]);
 break;
 }

changeset 561	6e0525ec5355
parent 525	635a8375227d
child 584	33c6b6e755cd
child 1158	f37f0845cf32