RhodeCode

/* -*- mode: C++; indent-tabs-mode: nil; -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library.
 *
 * Copyright (C) 2003-2010
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

#ifndef LEMON_DIMACS_H
#define LEMON_DIMACS_H

#include <iostream>
#include <string>
#include <vector>
#include <limits>
#include <lemon/maps.h>
#include <lemon/error.h>
/// \ingroup dimacs_group
/// \file
/// \brief DIMACS file format reader.

namespace lemon {

  /// \addtogroup dimacs_group
  /// @{

  /// DIMACS file type descriptor.
  struct DimacsDescriptor
  {
    ///\brief DIMACS file type enum
    ///
    ///DIMACS file type enum.
    enum Type {
      NONE,  ///< Undefined type.
      MIN,   ///< DIMACS file type for minimum cost flow problems.
      MAX,   ///< DIMACS file type for maximum flow problems.
      SP,    ///< DIMACS file type for shostest path problems.
      MAT    ///< DIMACS file type for plain graphs and matching problems.
    };
    ///The file type
    Type type;
    ///The number of nodes in the graph
    int nodeNum;
    ///The number of edges in the graph
    int edgeNum;
    int lineShift;
    ///Constructor. It sets the type to \c NONE.
    DimacsDescriptor() : type(NONE) {}
  };

  ///Discover the type of a DIMACS file

  ///This function starts seeking the beginning of the given file for the
  ///problem type and size info.
  ///The found data is returned in a special struct that can be evaluated
  ///and passed to the appropriate reader function.
  DimacsDescriptor dimacsType(std::istream& is)
  {
    DimacsDescriptor r;
    std::string problem,str;
    char c;
    r.lineShift=0;
    while (is >> c)
      switch(c)
        {
        case 'p':
          if(is >> problem >> r.nodeNum >> r.edgeNum)
            {
              getline(is, str);
              r.lineShift++;
              if(problem=="min") r.type=DimacsDescriptor::MIN;
              else if(problem=="max") r.type=DimacsDescriptor::MAX;
              else if(problem=="sp") r.type=DimacsDescriptor::SP;
              else if(problem=="mat") r.type=DimacsDescriptor::MAT;
              else throw FormatError("Unknown problem type");
              return r;
            }
          else
            {
              throw FormatError("Missing or wrong problem type declaration.");
            }
          break;
        case 'c':
          getline(is, str);
          r.lineShift++;
          break;
        default:
          throw FormatError("Unknown DIMACS declaration.");
        }
    throw FormatError("Missing problem type declaration.");
  }


  /// \brief DIMACS minimum cost flow reader function.
  ///
  /// This function reads a minimum cost flow instance from DIMACS format,
  /// i.e. from a DIMACS file having a line starting with
  /// \code
  ///   p min
  /// \endcode
  /// At the beginning, \c g is cleared by \c g.clear(). The supply
  /// amount of the nodes are written to the \c supply node map
  /// (they are signed values). The lower bounds, capacities and costs
  /// of the arcs are written to the \c lower, \c capacity and \c cost
  /// arc maps.
  ///
  /// If the capacity of an arc is less than the lower bound, it will
  /// be set to "infinite" instead. The actual value of "infinite" is
  /// contolled by the \c infty parameter. If it is 0 (the default value),
  /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
  /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
  /// a non-zero value, that value will be used as "infinite".
  ///
  /// If the file type was previously evaluated by dimacsType(), then
  /// the descriptor struct should be given by the \c dest parameter.
  template <typename Digraph, typename LowerMap,
            typename CapacityMap, typename CostMap,
            typename SupplyMap>
  void readDimacsMin(std::istream& is,
                     Digraph &g,
                     LowerMap& lower,
                     CapacityMap& capacity,
                     CostMap& cost,
                     SupplyMap& supply,
                     typename CapacityMap::Value infty = 0,
                     DimacsDescriptor desc=DimacsDescriptor())
  {
    g.clear();
    std::vector<typename Digraph::Node> nodes;
    typename Digraph::Arc e;
    std::string problem, str;
    char c;
    int i, j;
    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
    if(desc.type!=DimacsDescriptor::MIN)
      throw FormatError("Problem type mismatch");

    nodes.resize(desc.nodeNum + 1);
    for (int k = 1; k <= desc.nodeNum; ++k) {
      nodes[k] = g.addNode();
      supply.set(nodes[k], 0);
    }

    typename SupplyMap::Value sup;
    typename CapacityMap::Value low;
    typename CapacityMap::Value cap;
    typename CostMap::Value co;
    typedef typename CapacityMap::Value Capacity;
    if(infty==0)
      infty = std::numeric_limits<Capacity>::has_infinity ?
        std::numeric_limits<Capacity>::infinity() :
        std::numeric_limits<Capacity>::max();

    while (is >> c) {
      switch (c) {
      case 'c': // comment line
        getline(is, str);
        break;
      case 'n': // node definition line
        is >> i >> sup;
        getline(is, str);
        supply.set(nodes[i], sup);
        break;
      case 'a': // arc definition line
        is >> i >> j >> low >> cap >> co;
        getline(is, str);
        e = g.addArc(nodes[i], nodes[j]);
        lower.set(e, low);
        if (cap >= low)
          capacity.set(e, cap);
        else
          capacity.set(e, infty);
        cost.set(e, co);
        break;
      }
    }
  }

  template<typename Digraph, typename CapacityMap>
  void _readDimacs(std::istream& is,
                   Digraph &g,
                   CapacityMap& capacity,
                   typename Digraph::Node &s,
                   typename Digraph::Node &t,
                   typename CapacityMap::Value infty = 0,
                   DimacsDescriptor desc=DimacsDescriptor()) {
    g.clear();
    s=t=INVALID;
    std::vector<typename Digraph::Node> nodes;
    typename Digraph::Arc e;
    char c, d;
    int i, j;
    typename CapacityMap::Value _cap;
    std::string str;
    nodes.resize(desc.nodeNum + 1);
    for (int k = 1; k <= desc.nodeNum; ++k) {
      nodes[k] = g.addNode();
    }
    typedef typename CapacityMap::Value Capacity;

    if(infty==0)
      infty = std::numeric_limits<Capacity>::has_infinity ?
        std::numeric_limits<Capacity>::infinity() :
        std::numeric_limits<Capacity>::max();

    while (is >> c) {
      switch (c) {
      case 'c': // comment line
        getline(is, str);
        break;
      case 'n': // node definition line
        if (desc.type==DimacsDescriptor::SP) { // shortest path problem
          is >> i;
          getline(is, str);
          s = nodes[i];
        }
        if (desc.type==DimacsDescriptor::MAX) { // max flow problem
          is >> i >> d;
          getline(is, str);
          if (d == 's') s = nodes[i];
          if (d == 't') t = nodes[i];
        }
        break;
      case 'a': // arc definition line
        if (desc.type==DimacsDescriptor::SP) {
          is >> i >> j >> _cap;
          getline(is, str);
          e = g.addArc(nodes[i], nodes[j]);
          capacity.set(e, _cap);
        }
        else if (desc.type==DimacsDescriptor::MAX) {
          is >> i >> j >> _cap;
          getline(is, str);
          e = g.addArc(nodes[i], nodes[j]);
          if (_cap >= 0)
            capacity.set(e, _cap);
          else
            capacity.set(e, infty);
        }
        else {
          is >> i >> j;
          getline(is, str);
          g.addArc(nodes[i], nodes[j]);
        }
        break;
      }
    }
  }

  /// \brief DIMACS maximum flow reader function.
  ///
  /// This function reads a maximum flow instance from DIMACS format,
  /// i.e. from a DIMACS file having a line starting with
  /// \code
  ///   p max
  /// \endcode
  /// At the beginning, \c g is cleared by \c g.clear(). The arc
  /// capacities are written to the \c capacity arc map and \c s and
  /// \c t are set to the source and the target nodes.
  ///
  /// If the capacity of an arc is negative, it will
  /// be set to "infinite" instead. The actual value of "infinite" is
  /// contolled by the \c infty parameter. If it is 0 (the default value),
  /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
  /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
  /// a non-zero value, that value will be used as "infinite".
  ///
  /// If the file type was previously evaluated by dimacsType(), then
  /// the descriptor struct should be given by the \c dest parameter.
  template<typename Digraph, typename CapacityMap>
  void readDimacsMax(std::istream& is,
                     Digraph &g,
                     CapacityMap& capacity,
                     typename Digraph::Node &s,
                     typename Digraph::Node &t,
                     typename CapacityMap::Value infty = 0,
                     DimacsDescriptor desc=DimacsDescriptor()) {
    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
    if(desc.type!=DimacsDescriptor::MAX)
      throw FormatError("Problem type mismatch");
    _readDimacs(is,g,capacity,s,t,infty,desc);
  }

  /// \brief DIMACS shortest path reader function.
  ///
  /// This function reads a shortest path instance from DIMACS format,
  /// i.e. from a DIMACS file having a line starting with
  /// \code
  ///   p sp
  /// \endcode
  /// At the beginning, \c g is cleared by \c g.clear(). The arc
  /// lengths are written to the \c length arc map and \c s is set to the
  /// source node.
  ///
  /// If the file type was previously evaluated by dimacsType(), then
  /// the descriptor struct should be given by the \c dest parameter.
  template<typename Digraph, typename LengthMap>
  void readDimacsSp(std::istream& is,
                    Digraph &g,
                    LengthMap& length,
                    typename Digraph::Node &s,
                    DimacsDescriptor desc=DimacsDescriptor()) {
    typename Digraph::Node t;
    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
    if(desc.type!=DimacsDescriptor::SP)
      throw FormatError("Problem type mismatch");
    _readDimacs(is, g, length, s, t, 0, desc);
  }

  /// \brief DIMACS capacitated digraph reader function.
  ///
  /// This function reads an arc capacitated digraph instance from
  /// DIMACS 'max' or 'sp' format.
  /// At the beginning, \c g is cleared by \c g.clear()
  /// and the arc capacities/lengths are written to the \c capacity
  /// arc map.
  ///
  /// In case of the 'max' format, if the capacity of an arc is negative,
  /// it will
  /// be set to "infinite" instead. The actual value of "infinite" is
  /// contolled by the \c infty parameter. If it is 0 (the default value),
  /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
  /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to
  /// a non-zero value, that value will be used as "infinite".
  ///
  /// If the file type was previously evaluated by dimacsType(), then
  /// the descriptor struct should be given by the \c dest parameter.
  template<typename Digraph, typename CapacityMap>
  void readDimacsCap(std::istream& is,
                     Digraph &g,
                     CapacityMap& capacity,
                     typename CapacityMap::Value infty = 0,
                     DimacsDescriptor desc=DimacsDescriptor()) {
    typename Digraph::Node u,v;
    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
    if(desc.type!=DimacsDescriptor::MAX || desc.type!=DimacsDescriptor::SP)
      throw FormatError("Problem type mismatch");
    _readDimacs(is, g, capacity, u, v, infty, desc);
  }

  template<typename Graph>
  typename enable_if<lemon::UndirectedTagIndicator<Graph>,void>::type
  _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t,
              dummy<0> = 0)
  {
    g.addEdge(s,t);
  }
  template<typename Graph>
  typename disable_if<lemon::UndirectedTagIndicator<Graph>,void>::type
  _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t,
              dummy<1> = 1)
  {
    g.addArc(s,t);
  }

  /// \brief DIMACS plain (di)graph reader function.
  ///
  /// This function reads a plain (di)graph without any designated nodes
  /// and maps (e.g. a matching instance) from DIMACS format, i.e. from
  /// DIMACS files having a line starting with
  /// \code
  ///   p mat
  /// \endcode
  /// At the beginning, \c g is cleared by \c g.clear().
  ///
  /// If the file type was previously evaluated by dimacsType(), then
  /// the descriptor struct should be given by the \c dest parameter.
  template<typename Graph>
  void readDimacsMat(std::istream& is, Graph &g,
                     DimacsDescriptor desc=DimacsDescriptor())
  {
    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
    if(desc.type!=DimacsDescriptor::MAT)
      throw FormatError("Problem type mismatch");

    g.clear();
    std::vector<typename Graph::Node> nodes;
    char c;
    int i, j;
    std::string str;
    nodes.resize(desc.nodeNum + 1);
    for (int k = 1; k <= desc.nodeNum; ++k) {
      nodes[k] = g.addNode();
    }

    while (is >> c) {
      switch (c) {
      case 'c': // comment line
        getline(is, str);
        break;
      case 'n': // node definition line
        break;
      case 'a': // arc definition line
        is >> i >> j;
        getline(is, str);
        _addArcEdge(g,nodes[i], nodes[j]);
        break;
      }
    }
  }

  /// DIMACS plain digraph writer function.
  ///
  /// This function writes a digraph without any designated nodes and
  /// maps into DIMACS format, i.e. into DIMACS file having a line
  /// starting with
  /// \code
  ///   p mat
  /// \endcode
  /// If \c comment is not empty, then it will be printed in the first line
  /// prefixed by 'c'.
  template<typename Digraph>
  void writeDimacsMat(std::ostream& os, const Digraph &g,
                      std::string comment="") {
    typedef typename Digraph::NodeIt NodeIt;
    typedef typename Digraph::ArcIt ArcIt;

    if(!comment.empty())
      os << "c " << comment << std::endl;
    os << "p mat " << g.nodeNum() << " " << g.arcNum() << std::endl;

    typename Digraph::template NodeMap<int> nodes(g);
    int i = 1;
    for(NodeIt v(g); v != INVALID; ++v) {
      nodes.set(v, i);
      ++i;
    }
    for(ArcIt e(g); e != INVALID; ++e) {
      os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)]
         << std::endl;
    }
  }

  /// @}

} //namespace lemon

#endif //LEMON_DIMACS_H