RhodeCode

*/

/**

@defgroup timecount Time Measuring and Counting

@ingroup misc

\brief Simple tools for measuring the performance of algorithms.

This group describes simple tools for measuring the performance

of algorithms.

*/

/**

@defgroup exceptions Exceptions

@ingroup utils

\brief Exceptions defined in LEMON.

This group describes the exceptions defined in LEMON.

*/

/**

@defgroup io_group Input-Output

\brief Graph Input-Output methods

This group describes the tools for importing and exporting graphs

and graph related data. Now it supports the \ref lgf-format

"LEMON Graph Format", the \c DIMACS format and the encapsulated

postscript (EPS) format.

*/

/**

@defgroup lemon_io LEMON Graph Format

@ingroup io_group

\brief Reading and writing LEMON Graph Format.

This group describes methods for reading and writing

\ref lgf-format "LEMON Graph Format".

*/

/**

@defgroup eps_io Postscript Exporting

@ingroup io_group

\brief General \c EPS drawer and graph exporter

This group describes general \c EPS drawing methods and special

graph exporting tools.

*/

/**

@defgroup nauty_group NAUTY Format

@ingroup io_group

\brief Read \e Nauty format

Tool to read graphs from \e Nauty format data.

*/

/**

@defgroup concept Concepts

\brief Skeleton classes and concept checking classes

This group describes the data/algorithm skeletons and concept checking

classes implemented in LEMON.

The purpose of the classes in this group is fourfold.

- These classes contain the documentations of the %concepts. In order

  to avoid document multiplications, an implementation of a concept

  simply refers to the corresponding concept class.

- These classes declare every functions, <tt>typedef</tt>s etc. an

  implementation of the %concepts should provide, however completely

  without implementations and real data structures behind the

  interface. On the other hand they should provide nothing else. All

  the algorithms working on a data structure meeting a certain concept

  should compile with these classes. (Though it will not run properly,

  of course.) In this way it is easily to check if an algorithm

  doesn't use any extra feature of a certain implementation.

- The concept descriptor classes also provide a <em>checker class</em>

  that makes it possible to check whether a certain implementation of a

  concept indeed provides all the required features.

- Finally, They can serve as a skeleton of a new implementation of a concept.

*/

/**

@defgroup graph_concepts Graph Structure Concepts

@ingroup concept

\brief Skeleton and concept checking classes for graph structures

This group describes the skeletons and concept checking classes of LEMON's

graph structures and helper classes used to implement these.

*/

/**

@defgroup map_concepts Map Concepts

@ingroup concept

\brief Skeleton and concept checking classes for maps

This group describes the skeletons and concept checking classes of maps.

*/

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

 *

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

 *

 * Copyright (C) 2003-2008

 * 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 <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

  {

    ///File type enum

    enum Type

      {

        NONE, MIN, MAX, SP, MAT

      };

    ///The file type

    Type type;

    int nodeNum;

    int edgeNum;

    int lineShift;

    /// Constructor. Sets the type to NONE.

    DimacsDescriptor() : type(NONE) {}

  };

  ///Discover the type of a DIMACS file

  ///It starts seeking the begining of the file for the problem type

  ///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.");

  }

  ///

  /// \code

  ///   p min

  /// \endcode

  /// At the beginning, \c g is cleared by \c g.clear(). The supply

  /// amount of the nodes are written to \c supply (signed). The

  /// lower bounds, capacities and costs of the arcs are written to

  /// \c lower, \c capacity and \c cost.

  ///

  /// 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,

                     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;

    while (is >> c) {

      switch (c) {

      case 'c': // comment line

        getline(is, str);

        break;

      case 'n': // node definition line

        is >> i >> sup;

    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();

    }

    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 (arc) definition line

        if (desc.type==DimacsDescriptor::SP ||

            desc.type==DimacsDescriptor::MAX) {

          is >> i >> j >> _cap;

          getline(is, str);

          e = g.addArc(nodes[i], nodes[j]);

          capacity.set(e, _cap);

        } else {

          is >> i >> j;

          getline(is, str);

          g.addArc(nodes[i], nodes[j]);

        }

        break;

      }

    }

  }

  ///

  /// \code

  ///   p max

  /// \endcode

  /// At the beginning, \c g is cleared by \c g.clear(). The arc

  /// capacities are written to \c capacity and \c s and \c t are

  /// set to the source and the target nodes.

  ///

  /// 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,

                     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,desc);

  }

  /// DIMACS shortest path reader function.

  ///

  /// This function reads a shortest path instance from DIMACS format,

  /// \code

  ///   p sp

  /// \endcode

  /// At the beginning, \c g is cleared by \c g.clear(). The arc

  /// 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,desc);

  }

  /// DIMACS capacitated digraph reader function.

  ///

  /// This function reads an arc capacitated digraph instance from

  /// DIMACS 'mat' or 'sp' format.

  /// At the beginning, \c g is cleared by \c g.clear()

  /// and the arc capacities/lengths are written to \c capacity.

  ///

  /// 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,

                     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, desc);

  }

  /// DIMACS plain digraph reader function.

  ///

  /// This function reads a digraph without any designated nodes and

  /// maps 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().

  ///