/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Copyright (C) 2003-2009

 * 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