lemon/dimacs.h
author Alpar Juttner <alpar@cs.elte.hu>
Thu, 27 Nov 2008 22:05:35 +0000
changeset 401 9d1faab5e0f1
parent 400 50d96f2166d7
child 402 24a2c6ee6cb0
permissions -rw-r--r--
Give different names to the different DIMACS readers
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_DIMACS_H
    20 #define LEMON_DIMACS_H
    21 
    22 #include <iostream>
    23 #include <string>
    24 #include <vector>
    25 #include <lemon/maps.h>
    26 
    27 /// \ingroup dimacs_group
    28 /// \file
    29 /// \brief DIMACS file format reader.
    30 
    31 namespace lemon {
    32 
    33   ///@defgroup dimacs_group DIMACS format
    34   ///\brief Read and write files in DIMACS format
    35   ///
    36   ///Tools to read a digraph from or write it to a file in DIMACS format
    37   ///data
    38   ///\ingroup io_group
    39 
    40   /// \addtogroup dimacs_group
    41   /// @{
    42 
    43   /// DIMACS min cost flow reader function.
    44   ///
    45   /// This function reads a min cost flow instance from DIMACS format,
    46   /// i.e. from DIMACS files having a line starting with
    47   /// \code
    48   ///   p min
    49   /// \endcode
    50   /// At the beginning \c g is cleared by \c g.clear(). The supply
    51   /// amount of the nodes are written to \c supply (signed). The
    52   /// lower bounds, capacities and costs of the arcs are written to
    53   /// \c lower, \c capacity and \c cost.
    54   template <typename Digraph, typename LowerMap,
    55     typename CapacityMap, typename CostMap,
    56     typename SupplyMap>
    57   void readDimacsMin( std::istream& is,
    58                    Digraph &g,
    59                    LowerMap& lower,
    60                    CapacityMap& capacity,
    61                    CostMap& cost,
    62                    SupplyMap& supply )
    63   {
    64     g.clear();
    65     std::vector<typename Digraph::Node> nodes;
    66     typename Digraph::Arc e;
    67     std::string problem, str;
    68     char c;
    69     int n, m;
    70     int i, j;
    71     typename SupplyMap::Value sup;
    72     typename CapacityMap::Value low;
    73     typename CapacityMap::Value cap;
    74     typename CostMap::Value co;
    75     while (is >> c) {
    76       switch (c) {
    77       case 'c': // comment line
    78         getline(is, str);
    79         break;
    80       case 'p': // problem definition line
    81         is >> problem >> n >> m;
    82         getline(is, str);
    83         if (problem != "min") return;
    84         nodes.resize(n + 1);
    85         for (int k = 1; k <= n; ++k) {
    86           nodes[k] = g.addNode();
    87           supply.set(nodes[k], 0);
    88         }
    89         break;
    90       case 'n': // node definition line
    91         is >> i >> sup;
    92         getline(is, str);
    93         supply.set(nodes[i], sup);
    94         break;
    95       case 'a': // arc (arc) definition line
    96         is >> i >> j >> low >> cap >> co;
    97         getline(is, str);
    98         e = g.addArc(nodes[i], nodes[j]);
    99         lower.set(e, low);
   100         if (cap >= 0)
   101           capacity.set(e, cap);
   102         else
   103           capacity.set(e, -1);
   104         cost.set(e, co);
   105         break;
   106       }
   107     }
   108   }
   109 
   110   /// DIMACS max flow reader function.
   111   ///
   112   /// This function reads a max flow instance from DIMACS format,
   113   /// i.e. from DIMACS files having a line starting with
   114   /// \code
   115   ///   p max
   116   /// \endcode
   117   /// At the beginning \c g is cleared by \c g.clear(). The arc
   118   /// capacities are written to \c capacity and \c s and \c t are
   119   /// set to the source and the target nodes.
   120   template<typename Digraph, typename CapacityMap>
   121   void readDimacsMax(std::istream& is, Digraph &g, CapacityMap& capacity,
   122                   typename Digraph::Node &s, typename Digraph::Node &t) {
   123     g.clear();
   124     std::vector<typename Digraph::Node> nodes;
   125     typename Digraph::Arc e;
   126     std::string problem;
   127     char c, d;
   128     int n, m;
   129     int i, j;
   130     typename CapacityMap::Value _cap;
   131     std::string str;
   132     while (is >> c) {
   133       switch (c) {
   134       case 'c': // comment line
   135         getline(is, str);
   136         break;
   137       case 'p': // problem definition line
   138         is >> problem >> n >> m;
   139         getline(is, str);
   140         nodes.resize(n + 1);
   141         for (int k = 1; k <= n; ++k)
   142           nodes[k] = g.addNode();
   143         break;
   144       case 'n': // node definition line
   145         if (problem == "sp") { // shortest path problem
   146           is >> i;
   147           getline(is, str);
   148           s = nodes[i];
   149         }
   150         if (problem == "max") { // max flow problem
   151           is >> i >> d;
   152           getline(is, str);
   153           if (d == 's') s = nodes[i];
   154           if (d == 't') t = nodes[i];
   155         }
   156         break;
   157       case 'a': // arc (arc) definition line
   158         if (problem == "max" || problem == "sp") {
   159           is >> i >> j >> _cap;
   160           getline(is, str);
   161           e = g.addArc(nodes[i], nodes[j]);
   162           capacity.set(e, _cap);
   163         } else {
   164           is >> i >> j;
   165           getline(is, str);
   166           g.addArc(nodes[i], nodes[j]);
   167         }
   168         break;
   169       }
   170     }
   171   }
   172 
   173   /// DIMACS shortest path reader function.
   174   ///
   175   /// This function reads a shortest path instance from DIMACS format,
   176   /// i.e. from DIMACS files having a line starting with
   177   /// \code
   178   ///   p sp
   179   /// \endcode
   180   /// At the beginning \c g is cleared by \c g.clear(). The arc
   181   /// capacities are written to \c capacity and \c s is set to the
   182   /// source node.
   183   template<typename Digraph, typename CapacityMap>
   184   void readDimacsSp(std::istream& is, Digraph &g, CapacityMap& capacity,
   185                   typename Digraph::Node &s) {
   186     typename Digraph::Node t;
   187     readDimacsMax(is, g, capacity, s, t);
   188   }
   189 
   190   /// DIMACS capacitated digraph reader function.
   191   ///
   192   /// This function reads an arc capacitated digraph instance from
   193   /// DIMACS format. At the beginning \c g is cleared by \c g.clear()
   194   /// and the arc capacities are written to \c capacity.
   195   template<typename Digraph, typename CapacityMap>
   196   void readDimacsMax(std::istream& is, Digraph &g, CapacityMap& capacity) {
   197     typename Digraph::Node u,v;
   198     readDimacsMax(is, g, capacity, u, v);
   199   }
   200 
   201   /// DIMACS plain digraph reader function.
   202   ///
   203   /// This function reads a digraph without any designated nodes and
   204   /// maps from DIMACS format, i.e. from DIMACS files having a line
   205   /// starting with
   206   /// \code
   207   ///   p mat
   208   /// \endcode
   209   /// At the beginning \c g is cleared by \c g.clear().
   210   template<typename Digraph>
   211   void readDimacsMat(std::istream& is, Digraph &g) {
   212     typename Digraph::Node u,v;
   213     NullMap<typename Digraph::Arc, int> n;
   214     readDimacsMax(is, g, n, u, v);
   215   }
   216 
   217   /// DIMACS plain digraph writer function.
   218   ///
   219   /// This function writes a digraph without any designated nodes and
   220   /// maps into DIMACS format, i.e. into DIMACS file having a line
   221   /// starting with
   222   /// \code
   223   ///   p mat
   224   /// \endcode
   225   template<typename Digraph>
   226   void writeDimacsMat(std::ostream& os, const Digraph &g) {
   227     typedef typename Digraph::NodeIt NodeIt;
   228     typedef typename Digraph::ArcIt ArcIt;
   229 
   230     os << "c matching problem" << std::endl;
   231     os << "p mat " << g.nodeNum() << " " << g.arcNum() << std::endl;
   232 
   233     typename Digraph::template NodeMap<int> nodes(g);
   234     int i = 1;
   235     for(NodeIt v(g); v != INVALID; ++v) {
   236       nodes.set(v, i);
   237       ++i;
   238     }
   239     for(ArcIt e(g); e != INVALID; ++e) {
   240       os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)]
   241          << std::endl;
   242     }
   243   }
   244 
   245   /// @}
   246 
   247 } //namespace lemon
   248 
   249 #endif //LEMON_DIMACS_H