RhodeCode

#include <iostream>

#include <string>

#include <vector>

#include <lemon/maps.h>

#include <lemon/error.h>

/// \ingroup dimacs_group

/// \file

/// \brief DIMACS file format reader.

  };

  ///Discover the type of a DIMACS file

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

  /// \code

  ///   p min

  /// \endcode

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

  ///

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

                     LowerMap& lower,

                     CapacityMap& capacity,

                     CostMap& cost,

                     SupplyMap& supply,

                     DimacsDescriptor desc=DimacsDescriptor())

  {

    g.clear();

    std::vector<typename Digraph::Node> nodes;

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

        is >> i >> sup;

        getline(is, str);

        supply.set(nodes[i], sup);

        break;

        is >> i >> j >> low >> cap >> co;

        getline(is, str);

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

        lower.set(e, low);

          capacity.set(e, cap);

        else

        cost.set(e, co);

        break;

      }

    }

                   Digraph &g,

                   CapacityMap& capacity,

                   typename Digraph::Node &s,

                   typename Digraph::Node &t,

                   DimacsDescriptor desc=DimacsDescriptor()) {

    g.clear();

    s=t=INVALID;

    std::vector<typename Digraph::Node> nodes;

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

          if (d == 's') s = nodes[i];

          if (d == 't') t = nodes[i];

        }

        break;

          is >> i >> j >> _cap;

          getline(is, str);

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

          capacity.set(e, _cap);

          is >> i >> j;

          getline(is, str);

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

        }

  /// \code

  ///   p max

  /// \endcode

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

  ///

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

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

  }

  /// DIMACS shortest path reader function.

  ///

  /// \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.

    typename Digraph::Node t;

    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);

    if(desc.type!=DimacsDescriptor::SP)

      throw FormatError("Problem type mismatch");

  }

  /// DIMACS capacitated digraph reader function.

  ///

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

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

  }

  template<typename Graph>

  typename enable_if<lemon::UndirectedTagIndicator<Graph>,void>::type

        getline(is, str);

        break;

      case 'n': // node definition line

        break;

        is >> i >> j;

        getline(is, str);

        _addArcEdge(g,nodes[i], nodes[j]);

        break;

}

template<class Value>

void solve_max(ArgParser &ap, std::istream &is, std::ostream &,

{

  bool report = !ap.given("q");

  Digraph g;

  Node s,t;

  Digraph::ArcMap<Value> cap(g);

  Timer ti;

  ti.restart();

  if(report) std::cerr << "Read the file: " << ti << '\n';

  ti.restart();

  Preflow<Digraph, Digraph::ArcMap<Value> > pre(g,cap,s,t);

  if(report) std::cerr << "Setup Preflow class: " << ti << '\n';

template<class Value>

void solve(ArgParser &ap, std::istream &is, std::ostream &os,

           DimacsDescriptor &desc)

{

  switch(desc.type)

    {

    case DimacsDescriptor::MIN:

      std::cerr <<

        "\n\n Sorry, the min. cost flow solver is not yet available.\n";

      break;

    case DimacsDescriptor::MAX:

      break;

    case DimacsDescriptor::SP:

      solve_sp<Value>(ap,is,os,desc);

      break;

    .optionGroup("datatype","double")

    .boolOption("ldouble","Use 'long double' for capacities, costs etc.")

    .optionGroup("datatype","ldouble")

    .onlyOneGroup("datatype")

    .run();

  std::ifstream input;

  std::ofstream output;

      {

        Digraph digraph;

        DoubleArcMap lower(digraph), capacity(digraph), cost(digraph);

        DoubleNodeMap supply(digraph);

        DigraphWriter<Digraph>(digraph, os).

          nodeMap("supply", supply).

          arcMap("lower", lower).

          arcMap("capacity", capacity).

      {

        Digraph digraph;

        Node s, t;

        DoubleArcMap capacity(digraph);

        DigraphWriter<Digraph>(digraph, os).

          arcMap("capacity", capacity).

          node("source", s).

          node("target", t).