alpar@385: /* -*- mode: C++; indent-tabs-mode: nil; -*- alpar@385: * alpar@385: * This file is a part of LEMON, a generic C++ optimization library. alpar@385: * alpar@440: * Copyright (C) 2003-2009 alpar@385: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@385: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@385: * alpar@385: * Permission to use, modify and distribute this software is granted alpar@385: * provided that this copyright notice appears in all copies. For alpar@385: * precise terms see the accompanying LICENSE file. alpar@385: * alpar@385: * This software is provided "AS IS" with no warranty of any kind, alpar@385: * express or implied, and with no claim as to its suitability for any alpar@385: * purpose. alpar@385: * alpar@385: */ alpar@385: alpar@385: #ifndef LEMON_DIMACS_H alpar@385: #define LEMON_DIMACS_H alpar@385: alpar@385: #include alpar@385: #include alpar@385: #include alpar@561: #include alpar@385: #include alpar@387: #include alpar@385: /// \ingroup dimacs_group alpar@385: /// \file alpar@385: /// \brief DIMACS file format reader. alpar@385: alpar@385: namespace lemon { alpar@385: alpar@385: /// \addtogroup dimacs_group alpar@385: /// @{ alpar@385: alpar@387: /// DIMACS file type descriptor. alpar@387: struct DimacsDescriptor alpar@387: { kpeter@584: ///\brief DIMACS file type enum kpeter@584: /// kpeter@584: ///DIMACS file type enum. kpeter@584: enum Type { kpeter@584: NONE, ///< Undefined type. kpeter@584: MIN, ///< DIMACS file type for minimum cost flow problems. kpeter@584: MAX, ///< DIMACS file type for maximum flow problems. kpeter@584: SP, ///< DIMACS file type for shostest path problems. kpeter@584: MAT ///< DIMACS file type for plain graphs and matching problems. kpeter@584: }; alpar@387: ///The file type alpar@387: Type type; kpeter@388: ///The number of nodes in the graph alpar@387: int nodeNum; kpeter@388: ///The number of edges in the graph alpar@387: int edgeNum; alpar@387: int lineShift; kpeter@584: ///Constructor. It sets the type to \c NONE. alpar@387: DimacsDescriptor() : type(NONE) {} alpar@387: }; alpar@387: alpar@387: ///Discover the type of a DIMACS file alpar@387: kpeter@584: ///This function starts seeking the beginning of the given file for the kpeter@584: ///problem type and size info. kpeter@584: ///The found data is returned in a special struct that can be evaluated kpeter@584: ///and passed to the appropriate reader function. alpar@387: DimacsDescriptor dimacsType(std::istream& is) alpar@387: { alpar@387: DimacsDescriptor r; alpar@387: std::string problem,str; alpar@387: char c; alpar@387: r.lineShift=0; alpar@387: while (is >> c) alpar@387: switch(c) alpar@387: { alpar@387: case 'p': alpar@387: if(is >> problem >> r.nodeNum >> r.edgeNum) alpar@387: { alpar@387: getline(is, str); alpar@387: r.lineShift++; alpar@387: if(problem=="min") r.type=DimacsDescriptor::MIN; alpar@387: else if(problem=="max") r.type=DimacsDescriptor::MAX; alpar@387: else if(problem=="sp") r.type=DimacsDescriptor::SP; alpar@387: else if(problem=="mat") r.type=DimacsDescriptor::MAT; alpar@387: else throw FormatError("Unknown problem type"); alpar@387: return r; alpar@387: } alpar@387: else alpar@387: { alpar@387: throw FormatError("Missing or wrong problem type declaration."); alpar@387: } alpar@387: break; alpar@387: case 'c': alpar@387: getline(is, str); alpar@387: r.lineShift++; alpar@387: break; alpar@387: default: alpar@387: throw FormatError("Unknown DIMACS declaration."); alpar@387: } alpar@387: throw FormatError("Missing problem type declaration."); alpar@387: } alpar@387: alpar@387: kpeter@584: /// \brief DIMACS minimum cost flow reader function. alpar@385: /// kpeter@388: /// This function reads a minimum cost flow instance from DIMACS format, kpeter@388: /// i.e. from a DIMACS file having a line starting with alpar@385: /// \code alpar@385: /// p min alpar@385: /// \endcode alpar@387: /// At the beginning, \c g is cleared by \c g.clear(). The supply alpar@561: /// amount of the nodes are written to the \c supply node map alpar@561: /// (they are signed values). The lower bounds, capacities and costs alpar@561: /// of the arcs are written to the \c lower, \c capacity and \c cost alpar@561: /// arc maps. alpar@561: /// alpar@561: /// If the capacity of an arc is less than the lower bound, it will alpar@561: /// be set to "infinite" instead. The actual value of "infinite" is alpar@561: /// contolled by the \c infty parameter. If it is 0 (the default value), alpar@561: /// \c std::numeric_limits::infinity() will be used if available, alpar@561: /// \c std::numeric_limits::max() otherwise. If \c infty is set to alpar@561: /// a non-zero value, that value will be used as "infinite". alpar@387: /// alpar@387: /// If the file type was previously evaluated by dimacsType(), then alpar@387: /// the descriptor struct should be given by the \c dest parameter. alpar@385: template alpar@387: void readDimacsMin(std::istream& is, alpar@387: Digraph &g, alpar@387: LowerMap& lower, alpar@387: CapacityMap& capacity, alpar@387: CostMap& cost, alpar@387: SupplyMap& supply, alpar@561: typename CapacityMap::Value infty = 0, alpar@387: DimacsDescriptor desc=DimacsDescriptor()) alpar@385: { alpar@385: g.clear(); alpar@385: std::vector nodes; alpar@385: typename Digraph::Arc e; alpar@385: std::string problem, str; alpar@385: char c; alpar@385: int i, j; alpar@387: if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); alpar@387: if(desc.type!=DimacsDescriptor::MIN) alpar@387: throw FormatError("Problem type mismatch"); alpar@387: alpar@387: nodes.resize(desc.nodeNum + 1); alpar@387: for (int k = 1; k <= desc.nodeNum; ++k) { alpar@387: nodes[k] = g.addNode(); alpar@387: supply.set(nodes[k], 0); alpar@387: } alpar@387: alpar@385: typename SupplyMap::Value sup; alpar@385: typename CapacityMap::Value low; alpar@385: typename CapacityMap::Value cap; alpar@385: typename CostMap::Value co; alpar@561: typedef typename CapacityMap::Value Capacity; alpar@561: if(infty==0) alpar@561: infty = std::numeric_limits::has_infinity ? alpar@561: std::numeric_limits::infinity() : alpar@561: std::numeric_limits::max(); alpar@561: alpar@385: while (is >> c) { alpar@385: switch (c) { alpar@385: case 'c': // comment line alpar@385: getline(is, str); alpar@385: break; alpar@385: case 'n': // node definition line alpar@385: is >> i >> sup; alpar@385: getline(is, str); alpar@385: supply.set(nodes[i], sup); alpar@385: break; alpar@561: case 'a': // arc definition line alpar@385: is >> i >> j >> low >> cap >> co; alpar@385: getline(is, str); alpar@385: e = g.addArc(nodes[i], nodes[j]); alpar@385: lower.set(e, low); alpar@561: if (cap >= low) alpar@385: capacity.set(e, cap); alpar@385: else alpar@561: capacity.set(e, infty); alpar@385: cost.set(e, co); alpar@385: break; alpar@385: } alpar@385: } alpar@385: } alpar@385: alpar@385: template alpar@387: void _readDimacs(std::istream& is, alpar@387: Digraph &g, alpar@387: CapacityMap& capacity, alpar@387: typename Digraph::Node &s, alpar@387: typename Digraph::Node &t, alpar@561: typename CapacityMap::Value infty = 0, alpar@387: DimacsDescriptor desc=DimacsDescriptor()) { alpar@385: g.clear(); alpar@387: s=t=INVALID; alpar@385: std::vector nodes; alpar@385: typename Digraph::Arc e; alpar@385: char c, d; alpar@385: int i, j; alpar@385: typename CapacityMap::Value _cap; alpar@385: std::string str; alpar@387: nodes.resize(desc.nodeNum + 1); alpar@387: for (int k = 1; k <= desc.nodeNum; ++k) { alpar@387: nodes[k] = g.addNode(); alpar@387: } alpar@561: typedef typename CapacityMap::Value Capacity; alpar@387: alpar@561: if(infty==0) alpar@561: infty = std::numeric_limits::has_infinity ? alpar@561: std::numeric_limits::infinity() : alpar@561: std::numeric_limits::max(); alpar@561: alpar@385: while (is >> c) { alpar@385: switch (c) { alpar@385: case 'c': // comment line alpar@385: getline(is, str); alpar@385: break; alpar@385: case 'n': // node definition line alpar@387: if (desc.type==DimacsDescriptor::SP) { // shortest path problem alpar@385: is >> i; alpar@385: getline(is, str); alpar@385: s = nodes[i]; alpar@385: } alpar@387: if (desc.type==DimacsDescriptor::MAX) { // max flow problem alpar@385: is >> i >> d; alpar@385: getline(is, str); alpar@385: if (d == 's') s = nodes[i]; alpar@385: if (d == 't') t = nodes[i]; alpar@385: } alpar@385: break; alpar@561: case 'a': // arc definition line alpar@561: if (desc.type==DimacsDescriptor::SP) { alpar@385: is >> i >> j >> _cap; alpar@385: getline(is, str); alpar@385: e = g.addArc(nodes[i], nodes[j]); alpar@385: capacity.set(e, _cap); alpar@561: } alpar@561: else if (desc.type==DimacsDescriptor::MAX) { alpar@561: is >> i >> j >> _cap; alpar@561: getline(is, str); alpar@561: e = g.addArc(nodes[i], nodes[j]); alpar@561: if (_cap >= 0) alpar@561: capacity.set(e, _cap); alpar@561: else alpar@561: capacity.set(e, infty); alpar@561: } alpar@561: else { alpar@385: is >> i >> j; alpar@385: getline(is, str); alpar@385: g.addArc(nodes[i], nodes[j]); alpar@385: } alpar@385: break; alpar@385: } alpar@385: } alpar@385: } alpar@385: kpeter@584: /// \brief DIMACS maximum flow reader function. alpar@387: /// kpeter@388: /// This function reads a maximum flow instance from DIMACS format, kpeter@388: /// i.e. from a DIMACS file having a line starting with alpar@387: /// \code alpar@387: /// p max alpar@387: /// \endcode alpar@387: /// At the beginning, \c g is cleared by \c g.clear(). The arc alpar@561: /// capacities are written to the \c capacity arc map and \c s and alpar@561: /// \c t are set to the source and the target nodes. alpar@561: /// alpar@561: /// If the capacity of an arc is negative, it will alpar@561: /// be set to "infinite" instead. The actual value of "infinite" is alpar@561: /// contolled by the \c infty parameter. If it is 0 (the default value), alpar@561: /// \c std::numeric_limits::infinity() will be used if available, alpar@561: /// \c std::numeric_limits::max() otherwise. If \c infty is set to alpar@561: /// a non-zero value, that value will be used as "infinite". alpar@387: /// alpar@387: /// If the file type was previously evaluated by dimacsType(), then alpar@387: /// the descriptor struct should be given by the \c dest parameter. alpar@387: template alpar@387: void readDimacsMax(std::istream& is, alpar@387: Digraph &g, alpar@387: CapacityMap& capacity, alpar@387: typename Digraph::Node &s, alpar@387: typename Digraph::Node &t, alpar@561: typename CapacityMap::Value infty = 0, alpar@387: DimacsDescriptor desc=DimacsDescriptor()) { alpar@387: if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); alpar@387: if(desc.type!=DimacsDescriptor::MAX) alpar@387: throw FormatError("Problem type mismatch"); alpar@561: _readDimacs(is,g,capacity,s,t,infty,desc); alpar@387: } alpar@387: kpeter@584: /// \brief DIMACS shortest path reader function. alpar@385: /// alpar@385: /// This function reads a shortest path instance from DIMACS format, kpeter@388: /// i.e. from a DIMACS file having a line starting with alpar@385: /// \code alpar@385: /// p sp alpar@385: /// \endcode alpar@387: /// At the beginning, \c g is cleared by \c g.clear(). The arc alpar@561: /// lengths are written to the \c length arc map and \c s is set to the alpar@385: /// source node. alpar@387: /// alpar@387: /// If the file type was previously evaluated by dimacsType(), then alpar@387: /// the descriptor struct should be given by the \c dest parameter. alpar@387: template alpar@387: void readDimacsSp(std::istream& is, alpar@387: Digraph &g, alpar@387: LengthMap& length, alpar@387: typename Digraph::Node &s, alpar@387: DimacsDescriptor desc=DimacsDescriptor()) { alpar@386: typename Digraph::Node t; alpar@387: if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); alpar@387: if(desc.type!=DimacsDescriptor::SP) alpar@387: throw FormatError("Problem type mismatch"); alpar@561: _readDimacs(is, g, length, s, t, 0, desc); alpar@385: } alpar@385: kpeter@584: /// \brief DIMACS capacitated digraph reader function. alpar@385: /// alpar@385: /// This function reads an arc capacitated digraph instance from alpar@561: /// DIMACS 'max' or 'sp' format. alpar@387: /// At the beginning, \c g is cleared by \c g.clear() alpar@561: /// and the arc capacities/lengths are written to the \c capacity alpar@561: /// arc map. alpar@561: /// alpar@561: /// In case of the 'max' format, if the capacity of an arc is negative, alpar@561: /// it will alpar@561: /// be set to "infinite" instead. The actual value of "infinite" is alpar@561: /// contolled by the \c infty parameter. If it is 0 (the default value), alpar@561: /// \c std::numeric_limits::infinity() will be used if available, alpar@561: /// \c std::numeric_limits::max() otherwise. If \c infty is set to alpar@561: /// a non-zero value, that value will be used as "infinite". alpar@387: /// alpar@387: /// If the file type was previously evaluated by dimacsType(), then alpar@387: /// the descriptor struct should be given by the \c dest parameter. alpar@385: template alpar@387: void readDimacsCap(std::istream& is, alpar@387: Digraph &g, alpar@387: CapacityMap& capacity, alpar@561: typename CapacityMap::Value infty = 0, alpar@387: DimacsDescriptor desc=DimacsDescriptor()) { alpar@386: typename Digraph::Node u,v; alpar@387: if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); alpar@387: if(desc.type!=DimacsDescriptor::MAX || desc.type!=DimacsDescriptor::SP) alpar@387: throw FormatError("Problem type mismatch"); alpar@561: _readDimacs(is, g, capacity, u, v, infty, desc); alpar@385: } alpar@385: alpar@525: template alpar@525: typename enable_if,void>::type alpar@525: _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t, alpar@525: dummy<0> = 0) alpar@525: { alpar@525: g.addEdge(s,t); alpar@525: } alpar@525: template alpar@525: typename disable_if,void>::type alpar@525: _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t, alpar@525: dummy<1> = 1) alpar@525: { alpar@525: g.addArc(s,t); alpar@525: } alpar@525: kpeter@584: /// \brief DIMACS plain (di)graph reader function. alpar@385: /// kpeter@584: /// This function reads a plain (di)graph without any designated nodes kpeter@584: /// and maps (e.g. a matching instance) from DIMACS format, i.e. from kpeter@584: /// DIMACS files having a line starting with alpar@385: /// \code alpar@385: /// p mat alpar@385: /// \endcode alpar@387: /// At the beginning, \c g is cleared by \c g.clear(). alpar@387: /// alpar@387: /// If the file type was previously evaluated by dimacsType(), then alpar@387: /// the descriptor struct should be given by the \c dest parameter. alpar@525: template alpar@525: void readDimacsMat(std::istream& is, Graph &g, alpar@525: DimacsDescriptor desc=DimacsDescriptor()) alpar@525: { alpar@387: if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); alpar@387: if(desc.type!=DimacsDescriptor::MAT) alpar@387: throw FormatError("Problem type mismatch"); alpar@525: alpar@525: g.clear(); alpar@525: std::vector nodes; alpar@525: char c; alpar@525: int i, j; alpar@525: std::string str; alpar@525: nodes.resize(desc.nodeNum + 1); alpar@525: for (int k = 1; k <= desc.nodeNum; ++k) { alpar@525: nodes[k] = g.addNode(); alpar@525: } alpar@525: alpar@525: while (is >> c) { alpar@525: switch (c) { alpar@525: case 'c': // comment line alpar@525: getline(is, str); alpar@525: break; alpar@525: case 'n': // node definition line alpar@525: break; alpar@561: case 'a': // arc definition line alpar@525: is >> i >> j; alpar@525: getline(is, str); alpar@525: _addArcEdge(g,nodes[i], nodes[j]); alpar@525: break; alpar@525: } alpar@525: } alpar@385: } alpar@385: alpar@385: /// DIMACS plain digraph writer function. alpar@385: /// alpar@385: /// This function writes a digraph without any designated nodes and alpar@385: /// maps into DIMACS format, i.e. into DIMACS file having a line alpar@385: /// starting with alpar@385: /// \code alpar@385: /// p mat alpar@385: /// \endcode alpar@387: /// If \c comment is not empty, then it will be printed in the first line alpar@387: /// prefixed by 'c'. alpar@385: template alpar@387: void writeDimacsMat(std::ostream& os, const Digraph &g, alpar@387: std::string comment="") { alpar@385: typedef typename Digraph::NodeIt NodeIt; alpar@385: typedef typename Digraph::ArcIt ArcIt; alpar@385: alpar@440: if(!comment.empty()) alpar@387: os << "c " << comment << std::endl; alpar@385: os << "p mat " << g.nodeNum() << " " << g.arcNum() << std::endl; alpar@385: alpar@385: typename Digraph::template NodeMap nodes(g); alpar@385: int i = 1; alpar@385: for(NodeIt v(g); v != INVALID; ++v) { alpar@385: nodes.set(v, i); alpar@385: ++i; alpar@385: } alpar@385: for(ArcIt e(g); e != INVALID; ++e) { alpar@385: os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)] alpar@385: << std::endl; alpar@385: } alpar@385: } alpar@385: alpar@385: /// @} alpar@385: alpar@385: } //namespace lemon alpar@385: alpar@385: #endif //LEMON_DIMACS_H