alpar@906: /* -*- C++ -*- alpar@921: * src/lemon/dimacs.h - Part of LEMON, a generic C++ optimization library alpar@906: * alpar@1164: * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@906: * (Egervary Combinatorial Optimization Research Group, EGRES). alpar@906: * alpar@906: * Permission to use, modify and distribute this software is granted alpar@906: * provided that this copyright notice appears in all copies. For alpar@906: * precise terms see the accompanying LICENSE file. alpar@906: * alpar@906: * This software is provided "AS IS" with no warranty of any kind, alpar@906: * express or implied, and with no claim as to its suitability for any alpar@906: * purpose. alpar@906: * alpar@906: */ alpar@906: alpar@921: #ifndef LEMON_DIMACS_H alpar@921: #define LEMON_DIMACS_H marci@423: marci@423: #include marci@423: #include marci@423: #include alpar@921: #include marci@423: jacint@575: /// \ingroup misc klao@442: /// \file klao@442: /// \brief Dimacs file format reader. klao@427: alpar@921: namespace lemon { marci@423: marci@423: jacint@575: /// \addtogroup misc jacint@575: /// @{ jacint@575: jacint@575: /// Dimacs min cost flow reader function. jacint@575: jacint@575: /// This function reads a min cost flow instance from dimacs format, alpar@964: /// i.e. from dimacs files having a line starting with alpar@964: /// \code alpar@964: /// p "min" alpar@964: /// \endcode jacint@575: /// At the beginning \c g is cleared by \c g.clear(). The edge jacint@575: /// capacities are written to \c capacity, \c s and \c t are set to jacint@575: /// the source and the target nodes resp. and the cost of the edges jacint@575: /// are written to \c cost. marci@465: /// jacint@575: /// \author Marton Makai jacint@528: template jacint@528: void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, jacint@528: typename Graph::Node &s, typename Graph::Node &t, jacint@528: CostMap& cost) { jacint@528: g.clear(); alpar@987: typename CapacityMap::Value _cap; alpar@987: typename CostMap::Value _cost; jacint@528: char d; jacint@528: std::string problem; jacint@528: char c; jacint@528: int i, j; jacint@528: std::string str; jacint@528: int n, m; jacint@528: typename Graph::Edge e; jacint@528: std::vector nodes; jacint@528: while (is>>c) { jacint@528: switch (c) { jacint@528: case 'c': //comment jacint@528: getline(is, str); jacint@528: break; jacint@528: case 'p': //problem definition jacint@528: is >> problem >> n >> m; jacint@528: getline(is, str); jacint@528: nodes.resize(n+1); jacint@528: for (int k=1; k<=n; ++k) nodes[k]=g.addNode(); jacint@528: break; jacint@528: case 'n': //node definition jacint@528: if (problem=="sp") { //shortest path problem jacint@528: is >> i; jacint@528: getline(is, str); jacint@528: s=nodes[i]; jacint@528: } jacint@528: if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem jacint@528: is >> i >> d; jacint@528: getline(is, str); jacint@528: if (d=='s') s=nodes[i]; jacint@528: if (d=='t') t=nodes[i]; jacint@528: } jacint@528: break; jacint@528: case 'a': jacint@528: if ( problem == "max" || problem == "sp") { jacint@528: is >> i >> j >> _cap; jacint@528: getline(is, str); jacint@528: e=g.addEdge(nodes[i], nodes[j]); marci@784: //capacity.update(); jacint@528: capacity.set(e, _cap); jacint@575: } else { jacint@575: if ( problem == "min" ) { jacint@575: is >> i >> j >> _cap >> _cost; jacint@575: getline(is, str); jacint@575: e=g.addEdge(nodes[i], nodes[j]); marci@784: //capacity.update(); jacint@575: capacity.set(e, _cap); marci@784: //cost.update(); jacint@575: cost.set(e, _cost); jacint@575: } else { jacint@575: is >> i >> j; jacint@575: getline(is, str); jacint@575: g.addEdge(nodes[i], nodes[j]); jacint@575: } jacint@528: } jacint@528: break; jacint@528: } jacint@528: } jacint@528: } jacint@528: jacint@528: jacint@575: /// Dimacs max flow reader function. jacint@575: jacint@575: /// This function reads a max flow instance from dimacs format, alpar@964: /// i.e. from dimacs files having a line starting with alpar@964: /// \code alpar@964: /// p "max" alpar@964: /// \endcode alpar@964: ///At the beginning \c g is cleared by \c g.clear(). The jacint@575: /// edge capacities are written to \c capacity and \c s and \c t are jacint@575: /// set to the source and the target nodes. jacint@575: /// jacint@575: /// \author Marton Makai jacint@575: template jacint@575: void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, jacint@575: typename Graph::Node &s, typename Graph::Node &t) { jacint@575: NullMap n; jacint@575: readDimacs(is, g, capacity, s, t, n); jacint@575: } jacint@575: jacint@575: jacint@575: /// Dimacs shortest path reader function. jacint@575: jacint@575: /// This function reads a shortest path instance from dimacs format, alpar@964: /// i.e. from dimacs files having a line starting with alpar@964: /// \code alpar@964: /// p "sp" alpar@964: /// \endcode jacint@575: /// At the beginning \c g is cleared by \c g.clear(). The edge jacint@575: /// capacities are written to \c capacity and \c s is set to the jacint@575: /// source node. jacint@575: /// jacint@575: /// \author Marton Makai jacint@575: template jacint@575: void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, jacint@575: typename Graph::Node &s) { jacint@575: NullMap n; jacint@575: readDimacs(is, g, capacity, s, s, n); jacint@575: } jacint@575: jacint@575: jacint@575: /// Dimacs capacitated graph reader function. jacint@575: jacint@575: /// This function reads an edge capacitated graph instance from jacint@575: /// dimacs format. At the beginning \c g is cleared by \c g.clear() jacint@575: /// and the edge capacities are written to \c capacity. jacint@575: /// jacint@575: /// \author Marton Makai jacint@575: template jacint@575: void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) { jacint@575: typename Graph::Node u; jacint@575: NullMap n; jacint@575: readDimacs(is, g, capacity, u, u, n); jacint@575: } jacint@575: jacint@575: jacint@575: /// Dimacs plain graph reader function. jacint@575: jacint@575: /// This function reads a graph without any designated nodes and jacint@575: /// maps from dimacs format, i.e. from dimacs files having a line alpar@964: /// starting with alpar@964: /// \code alpar@964: /// p "mat" alpar@964: /// \endcode alpar@964: /// At the beginning \c g is cleared jacint@575: /// by \c g.clear(). jacint@575: /// jacint@575: /// \author Marton Makai jacint@575: template jacint@575: void readDimacs(std::istream& is, Graph &g) { jacint@575: typename Graph::Node u; jacint@575: NullMap n; jacint@575: readDimacs(is, g, n, u, u, n); jacint@575: } jacint@575: jacint@575: jacint@575: marci@423: jacint@528: /// write matching problem jacint@528: template jacint@528: void writeDimacs(std::ostream& os, const Graph &g) { jacint@528: typedef typename Graph::NodeIt NodeIt; jacint@528: typedef typename Graph::EdgeIt EdgeIt; jacint@528: jacint@528: typename Graph::template NodeMap nodes(g); jacint@528: jacint@528: os << "c matching problem" << std::endl; jacint@528: jacint@528: int i=1; marci@778: for(NodeIt v(g); v!=INVALID; ++v) { jacint@528: nodes.set(v, i); jacint@528: ++i; jacint@528: } jacint@528: jacint@528: os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl; jacint@528: marci@778: for(EdgeIt e(g); e!=INVALID; ++e) { alpar@986: os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)] << std::endl; jacint@528: } jacint@528: jacint@528: } jacint@528: jacint@575: /// @} jacint@528: alpar@921: } //namespace lemon marci@423: alpar@921: #endif //LEMON_DIMACS_H