lemon/dimacs.h
changeset 400 50d96f2166d7
child 401 9d1faab5e0f1
equal deleted inserted replaced
-1:000000000000 0:577ddc39e651
       
     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 readDimacs( 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 readDimacs(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 readDimacs(std::istream& is, Digraph &g, CapacityMap& capacity,
       
   185                   typename Digraph::Node &s) {
       
   186     readDimacs(is, g, capacity, s, s);
       
   187   }
       
   188 
       
   189   /// DIMACS capacitated digraph reader function.
       
   190   ///
       
   191   /// This function reads an arc capacitated digraph instance from
       
   192   /// DIMACS format. At the beginning \c g is cleared by \c g.clear()
       
   193   /// and the arc capacities are written to \c capacity.
       
   194   template<typename Digraph, typename CapacityMap>
       
   195   void readDimacs(std::istream& is, Digraph &g, CapacityMap& capacity) {
       
   196     typename Digraph::Node u;
       
   197     readDimacs(is, g, capacity, u, u);
       
   198   }
       
   199 
       
   200   /// DIMACS plain digraph reader function.
       
   201   ///
       
   202   /// This function reads a digraph without any designated nodes and
       
   203   /// maps from DIMACS format, i.e. from DIMACS files having a line
       
   204   /// starting with
       
   205   /// \code
       
   206   ///   p mat
       
   207   /// \endcode
       
   208   /// At the beginning \c g is cleared by \c g.clear().
       
   209   template<typename Digraph>
       
   210   void readDimacs(std::istream& is, Digraph &g) {
       
   211     typename Digraph::Node u;
       
   212     NullMap<typename Digraph::Arc, int> n;
       
   213     readDimacs(is, g, n, u, u);
       
   214   }
       
   215 
       
   216   /// DIMACS plain digraph writer function.
       
   217   ///
       
   218   /// This function writes a digraph without any designated nodes and
       
   219   /// maps into DIMACS format, i.e. into DIMACS file having a line
       
   220   /// starting with
       
   221   /// \code
       
   222   ///   p mat
       
   223   /// \endcode
       
   224   template<typename Digraph>
       
   225   void writeDimacs(std::ostream& os, const Digraph &g) {
       
   226     typedef typename Digraph::NodeIt NodeIt;
       
   227     typedef typename Digraph::ArcIt ArcIt;
       
   228 
       
   229     os << "c matching problem" << std::endl;
       
   230     os << "p mat " << g.nodeNum() << " " << g.arcNum() << std::endl;
       
   231 
       
   232     typename Digraph::template NodeMap<int> nodes(g);
       
   233     int i = 1;
       
   234     for(NodeIt v(g); v != INVALID; ++v) {
       
   235       nodes.set(v, i);
       
   236       ++i;
       
   237     }
       
   238     for(ArcIt e(g); e != INVALID; ++e) {
       
   239       os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)]
       
   240          << std::endl;
       
   241     }
       
   242   }
       
   243 
       
   244   /// @}
       
   245 
       
   246 } //namespace lemon
       
   247 
       
   248 #endif //LEMON_DIMACS_H