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 <iostream>
marci@423: #include <string>
marci@423: #include <vector>
alpar@921: #include <lemon/maps.h>
deba@1190: #include <lemon/invalid.h>
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<typename Graph, typename CapacityMap, typename CostMap>
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<typename Graph::Node> 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<typename Graph, typename CapacityMap>
jacint@575: void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
jacint@575: typename Graph::Node &s, typename Graph::Node &t) {
jacint@575: NullMap<typename Graph::Edge, int> 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<typename Graph, typename CapacityMap>
jacint@575: void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
jacint@575: typename Graph::Node &s) {
jacint@575: NullMap<typename Graph::Edge, int> 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<typename Graph, typename CapacityMap>
jacint@575: void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
jacint@575: typename Graph::Node u;
jacint@575: NullMap<typename Graph::Edge, int> 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<typename Graph>
jacint@575: void readDimacs(std::istream& is, Graph &g) {
jacint@575: typename Graph::Node u;
jacint@575: NullMap<typename Graph::Edge, int> 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<typename Graph>
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<int> 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