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@385: * Copyright (C) 2003-2008 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@385: #include alpar@385: 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: ///@defgroup dimacs_group DIMACS format alpar@385: ///\brief Read and write files in DIMACS format alpar@385: /// alpar@385: ///Tools to read a digraph from or write it to a file in DIMACS format alpar@385: ///data alpar@385: ///\ingroup io_group alpar@385: alpar@385: /// \addtogroup dimacs_group alpar@385: /// @{ alpar@385: alpar@385: /// DIMACS min cost flow reader function. alpar@385: /// alpar@385: /// This function reads a min cost flow instance from DIMACS format, alpar@385: /// i.e. from DIMACS files having a line starting with alpar@385: /// \code alpar@385: /// p min alpar@385: /// \endcode alpar@385: /// At the beginning \c g is cleared by \c g.clear(). The supply alpar@385: /// amount of the nodes are written to \c supply (signed). The alpar@385: /// lower bounds, capacities and costs of the arcs are written to alpar@385: /// \c lower, \c capacity and \c cost. alpar@385: template alpar@386: void readDimacsMin( std::istream& is, alpar@385: Digraph &g, alpar@385: LowerMap& lower, alpar@385: CapacityMap& capacity, alpar@385: CostMap& cost, alpar@385: SupplyMap& supply ) 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 n, m; alpar@385: int i, j; 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@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 'p': // problem definition line alpar@385: is >> problem >> n >> m; alpar@385: getline(is, str); alpar@385: if (problem != "min") return; alpar@385: nodes.resize(n + 1); alpar@385: for (int k = 1; k <= n; ++k) { alpar@385: nodes[k] = g.addNode(); alpar@385: supply.set(nodes[k], 0); alpar@385: } 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@385: case 'a': // arc (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@385: if (cap >= 0) alpar@385: capacity.set(e, cap); alpar@385: else alpar@385: capacity.set(e, -1); alpar@385: cost.set(e, co); alpar@385: break; alpar@385: } alpar@385: } alpar@385: } alpar@385: alpar@385: /// DIMACS max flow reader function. alpar@385: /// alpar@385: /// This function reads a max flow instance from DIMACS format, alpar@385: /// i.e. from DIMACS files having a line starting with alpar@385: /// \code alpar@385: /// p max alpar@385: /// \endcode alpar@385: /// At the beginning \c g is cleared by \c g.clear(). The arc alpar@385: /// capacities are written to \c capacity and \c s and \c t are alpar@385: /// set to the source and the target nodes. alpar@385: template alpar@386: void readDimacsMax(std::istream& is, Digraph &g, CapacityMap& capacity, alpar@385: typename Digraph::Node &s, typename Digraph::Node &t) { alpar@385: g.clear(); alpar@385: std::vector nodes; alpar@385: typename Digraph::Arc e; alpar@385: std::string problem; alpar@385: char c, d; alpar@385: int n, m; alpar@385: int i, j; alpar@385: typename CapacityMap::Value _cap; alpar@385: std::string str; 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 'p': // problem definition line alpar@385: is >> problem >> n >> m; alpar@385: getline(is, str); alpar@385: nodes.resize(n + 1); alpar@385: for (int k = 1; k <= n; ++k) alpar@385: nodes[k] = g.addNode(); alpar@385: break; alpar@385: case 'n': // node definition line alpar@385: if (problem == "sp") { // shortest path problem alpar@385: is >> i; alpar@385: getline(is, str); alpar@385: s = nodes[i]; alpar@385: } alpar@385: if (problem == "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@385: case 'a': // arc (arc) definition line alpar@385: if (problem == "max" || problem == "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@385: } 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: alpar@385: /// DIMACS shortest path reader function. alpar@385: /// alpar@385: /// This function reads a shortest path instance from DIMACS format, alpar@385: /// i.e. from DIMACS files having a line starting with alpar@385: /// \code alpar@385: /// p sp alpar@385: /// \endcode alpar@385: /// At the beginning \c g is cleared by \c g.clear(). The arc alpar@385: /// capacities are written to \c capacity and \c s is set to the alpar@385: /// source node. alpar@385: template alpar@386: void readDimacsSp(std::istream& is, Digraph &g, CapacityMap& capacity, alpar@385: typename Digraph::Node &s) { alpar@386: typename Digraph::Node t; alpar@386: readDimacsMax(is, g, capacity, s, t); alpar@385: } alpar@385: alpar@385: /// DIMACS capacitated digraph reader function. alpar@385: /// alpar@385: /// This function reads an arc capacitated digraph instance from alpar@385: /// DIMACS format. At the beginning \c g is cleared by \c g.clear() alpar@385: /// and the arc capacities are written to \c capacity. alpar@385: template alpar@386: void readDimacsMax(std::istream& is, Digraph &g, CapacityMap& capacity) { alpar@386: typename Digraph::Node u,v; alpar@386: readDimacsMax(is, g, capacity, u, v); alpar@385: } alpar@385: alpar@385: /// DIMACS plain digraph reader function. alpar@385: /// alpar@385: /// This function reads a digraph without any designated nodes and alpar@385: /// maps from DIMACS format, i.e. from DIMACS files having a line alpar@385: /// starting with alpar@385: /// \code alpar@385: /// p mat alpar@385: /// \endcode alpar@385: /// At the beginning \c g is cleared by \c g.clear(). alpar@385: template alpar@386: void readDimacsMat(std::istream& is, Digraph &g) { alpar@386: typename Digraph::Node u,v; alpar@385: NullMap n; alpar@386: readDimacsMax(is, g, n, u, v); 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@385: template alpar@386: void writeDimacsMat(std::ostream& os, const Digraph &g) { alpar@385: typedef typename Digraph::NodeIt NodeIt; alpar@385: typedef typename Digraph::ArcIt ArcIt; alpar@385: alpar@385: os << "c matching problem" << 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