LEMON/LEMON-main Changeset - r387:24a2c6ee6cb0

Repositories » LEMON » LEMON-main

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r387:24a2c6ee6cb0

« 386:9d1faa

388:0a3ec0 »

r387:24a2c6ee6cb0

Fri, 28 Nov 2008 07:38:20

[Not Reviewed]

0 comments (0 inline)

alpar (Alpar Juttner)
alpar@cs.elte.hu

Refactoring of DIMACS tools

0 2 0

default

2 files changed with 258 insertions and 161 deletions:

lemon/dimacs.h

175

tools/dimacs-to-lgf.cc

102

↑ Collapse diff ↑

lemon/dimacs.h

Show inline comments

@@ -20,12 +20,13 @@
 		#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 {
@@ -37,59 +38,126 @@
 		  ///data
 		  ///\ingroup io_group
 		  /// \addtogroup dimacs_group
 		  /// @{
 		  /// DIMACS file type descriptor.
 		  struct DimacsDescriptor
+		  {
 		    ///File type enum
 		    enum Type
+		      {
 		        NONE, MIN, MAX, SP, MAT
 		      };
 		    ///The file type
 		    Type type;
 		    ///The number of nodes on the graph
 		    int nodeNum;
 		    ///The number of edges on the graph
 		    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
 		  ///and size info. The found date 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.");
+		  }
 		  /// DIMACS min cost flow reader function.
 		  ///
 		  /// This function reads a min cost flow instance from DIMACS format,
 		  /// i.e. from DIMACS files having a line starting with
 		  /// \code
 		  ///   p min
 		  /// \endcode
 		  /// At the beginning \c g is cleared by \c g.clear(). The supply
+		  /// 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 )
 		            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 n, m;
 		    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 'p': // problem definition line
 		        is >> problem >> n >> m;
 		        getline(is, str);
 		        if (problem != "min") return;
 		        nodes.resize(n + 1);
 		        for (int k = 1; k <= n; ++k) {
 		          nodes[k] = g.addNode();
 		          supply.set(nodes[k], 0);
+		        }
 		        break;
 		      case 'n': // node definition line
 		        is >> i >> sup;
 		        getline(is, str);
 		        supply.set(nodes[i], sup);
 		        break;
 		      case 'a': // arc (arc) definition line
@@ -104,61 +172,53 @@
 		        cost.set(e, co);
 		        break;
+		      }
+		    }
+		  }
 		  /// DIMACS max flow reader function.
 		  ///
 		  /// This function reads a max flow instance from DIMACS format,
 		  /// i.e. from DIMACS files 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 \c capacity and \c s and \c t are
 		  /// set to the source and the target nodes.
 		  template<typename Digraph, typename CapacityMap>
 		  void readDimacsMax(std::istream& is, Digraph &g, CapacityMap& capacity,
 		                  typename Digraph::Node &s, typename Digraph::Node &t) {
 		  void _readDimacs(std::istream& is,
 		                   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;
 		    typename Digraph::Arc e;
 		    std::string problem;
 		    char c, d;
 		    int n, m;
 		    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 'p': // problem definition line
 		        is >> problem >> n >> m;
 		        getline(is, str);
 		        nodes.resize(n + 1);
 		        for (int k = 1; k <= n; ++k)
 		          nodes[k] = g.addNode();
 		        break;
 		      case 'n': // node definition line
-		        if (problem == "sp") { // shortest path problem
+		        if (desc.type==DimacsDescriptor::SP) { // shortest path problem
 		          is >> i;
 		          getline(is, str);
 		          s = nodes[i];
+		        }
-		        if (problem == "max") { // max flow problem
+		        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 (problem == "max" || problem == "sp") {
+		        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;
@@ -167,70 +227,126 @@
+		        }
 		        break;
+		      }
+		    }
+		  }
 		  /// DIMACS max flow reader function.
 		  ///
 		  /// This function reads a max flow instance from DIMACS format,
 		  /// i.e. from DIMACS files 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 \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,
 		  /// i.e. from DIMACS files having a line starting with
 		  /// \code
 		  ///   p sp
 		  /// \endcode
 		  /// At the beginning \c g is cleared by \c g.clear(). The arc
 		  /// capacities are written to \c capacity and \c s is set to the
 		  /// At the beginning, \c g is cleared by \c g.clear(). The arc
 		  /// lengths are written to \c lenght and \c s is set to the
 		  /// source node.
 		  template<typename Digraph, typename CapacityMap>
 		  void readDimacsSp(std::istream& is, Digraph &g, CapacityMap& capacity,
-		                  typename Digraph::Node &s) {
+		  ///
 		  /// 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;
-		    readDimacsMax(is, g, capacity, s, 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 format. At the beginning \c g is cleared by \c g.clear()
 		  /// and the arc capacities are written to \c capacity.
 		  /// 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 readDimacsMax(std::istream& is, Digraph &g, CapacityMap& capacity) {
+		  void readDimacsCap(std::istream& is,
 		                     Digraph &g,
 		                     CapacityMap& capacity,
 		                     DimacsDescriptor desc=DimacsDescriptor()) {
 		    typename Digraph::Node u,v;
-		    readDimacsMax(is, g, capacity, 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().
+		  /// 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>
-		  void readDimacsMat(std::istream& is, Digraph &g) {
+		  void readDimacsMat(std::istream& is, Digraph &g,
 		                     DimacsDescriptor desc=DimacsDescriptor()) {
 		    typename Digraph::Node u,v;
 		    NullMap<typename Digraph::Arc, int> n;
-		    readDimacsMax(is, g, n, u, v);
+		    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
 		    if(desc.type!=DimacsDescriptor::MAT)
 		      throw FormatError("Problem type mismatch");
 		    _readDimacs(is, g, n, u, v, desc);
+		  }
 		  /// 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) {
+		  void writeDimacsMat(std::ostream& os, const Digraph &g,
 		                      std::string comment="") {
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::ArcIt ArcIt;
-		    os << "c matching problem" << std::endl;
+		    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);

tools/dimacs-to-lgf.cc

Show inline comments

@@ -36,12 +36,13 @@
 		#include <lemon/smart_graph.h>
 		#include <lemon/dimacs.h>
 		#include <lemon/lgf_writer.h>
 		#include <lemon/arg_parser.h>
 		#include <lemon/error.h>
 		using namespace std;
 		using namespace lemon;
 		int main(int argc, const char *argv[]) {
@@ -53,116 +54,96 @@
 		  typedef Digraph::NodeIt NodeIt;
 		  typedef Digraph::ArcMap<double> DoubleArcMap;
 		  typedef Digraph::NodeMap<double> DoubleNodeMap;
 		  std::string inputName;
 		  std::string outputName;
 		  std::string typeName;
 		  bool mincostflow;
 		  bool maxflow;
 		  bool shortestpath;
 		  bool capacitated;
 		  bool plain;
 		  bool version;
 		  ArgParser ap(argc, argv);
 		  ap.refOption("-input",
 		               "use FILE as input instead of standard input",
 		               inputName).synonym("i", "-input")
 		    .refOption("-output",
 		               "use FILE as output instead of standard output",
 		               outputName).synonym("o", "-output")
 		    .refOption("-mincostflow",
 		               "set the type of the digraph to \"mincostflow\" digraph",
 		               mincostflow)
 		    .optionGroup("type", "-mincostflow").synonym("mcf", "-mincostflow")
 		    .refOption("-maxflow",
 		               "set the type of the digraph to \"maxflow\" digraph",
 		               maxflow)
 		    .optionGroup("type", "-maxflow").synonym("mf", "-maxflow")
 		    .refOption("-shortestpath",
 		               "set the type of the digraph to \"shortestpath\" digraph",
 		               shortestpath)
 		    .optionGroup("type", "-shortestpath").synonym("sp", "-shortestpath")
 		    .refOption("-capacitated",
 		               "set the type of the digraph to \"capacitated\" digraph",
 		               capacitated)
 		    .optionGroup("type", "-capacitated").synonym("cap", "-capacitated")
 		    .refOption("-plain",
 		               "set the type of the digraph to \"plain\" digraph",
 		               plain)
 		    .optionGroup("type", "-plain").synonym("pl", "-plain")
 		    .onlyOneGroup("type")
 		    .mandatoryGroup("type")
 		    .refOption("-version", "show version information", version)
 		    .synonym("v", "-version")
 		  ap.other("[INFILE [OUTFILE]]",
 		           "If either the INFILE or OUTFILE file is missing the standard\n"
 		           "     input/output will be used instead.")
 		    .run();
 		  ifstream input;
 		  if (!inputName.empty()) {
 		    input.open(inputName.c_str());
 		    if (!input) {
 		      cerr << "File open error" << endl;
-		      return -1;
+		  ofstream output;
 		  switch(ap.files().size())
+		    {
 		    case 2:
 		      output.open(ap.files()[1].c_str());
 		      if (!output) {
 		        throw IoError("Cannot open the file for writing", ap.files()[1]);
+		      }
 		    case 1:
 		      input.open(ap.files()[0].c_str());
 		      if (!input) {
 		        throw IoError("File cannot be found", ap.files()[0]);
+		      }
 		    case 0:
 		      break;
 		    default:
 		      cerr << ap.commandName() << ": too many arguments\n";
 		      return 1;
+		  }
 		  istream& is = (ap.files().size()<1 ? cin : input);
 		  ostream& os = (ap.files().size()<2 ? cout : output);
 		  DimacsDescriptor desc = dimacsType(is);
 		  switch(desc.type)
+		    {
 		    case DimacsDescriptor::MIN:
+		      {
 		        Digraph digraph;
 		        DoubleArcMap lower(digraph), capacity(digraph), cost(digraph);
 		        DoubleNodeMap supply(digraph);
 		        readDimacsMin(is, digraph, lower, capacity, cost, supply, desc);
 		        DigraphWriter<Digraph>(digraph, os).
 		          nodeMap("supply", supply).
 		          arcMap("lower", lower).
 		          arcMap("capacity", capacity).
 		          arcMap("cost", cost).
 		          attribute("problem","min").
 		          run();
+		      }
 		      break;
 		    case DimacsDescriptor::MAX:
+		      {
 		        Digraph digraph;
 		        Node s, t;
 		        DoubleArcMap capacity(digraph);
 		        readDimacsMax(is, digraph, capacity, s, t, desc);
 		        DigraphWriter<Digraph>(digraph, os).
 		          arcMap("capacity", capacity).
 		          node("source", s).
 		          node("target", t).
 		          attribute("problem","max").
 		          run();
+		      }
 		      break;
 		    case DimacsDescriptor::SP:
+		      {
 		        Digraph digraph;
 		        Node s;
 		        DoubleArcMap capacity(digraph);
 		        readDimacsSp(is, digraph, capacity, s, desc);
 		        DigraphWriter<Digraph>(digraph, os).
 		          arcMap("capacity", capacity).
 		          node("source", s).
 		          attribute("problem","sp").
 		          run();
+		      }
 		      break;
 		    case DimacsDescriptor::MAT:
+		      {
 		        Digraph digraph;
 		        readDimacsMat(is, digraph,desc);
 		        DigraphWriter<Digraph>(digraph, os).
 		          attribute("problem","mat").
 		          run();
+		      }
 		      break;
 		    default:
 		      break;
+		    }
+		  }
 		  istream& is = (inputName.empty() ? cin : input);
 		  ofstream output;
 		  if (!outputName.empty()) {
 		    output.open(outputName.c_str());
 		    if (!output) {
 		      cerr << "File open error" << endl;
 		      return -1;
+		    }
+		  }
 		  ostream& os = (outputName.empty() ? cout : output);
 		  if (mincostflow) {
 		    Digraph digraph;
 		    DoubleArcMap lower(digraph), capacity(digraph), cost(digraph);
 		    DoubleNodeMap supply(digraph);
 		    readDimacsMin(is, digraph, lower, capacity, cost, supply);
 		    DigraphWriter<Digraph>(digraph, os).
 		      nodeMap("supply", supply).
 		      arcMap("lower", lower).
 		      arcMap("capacity", capacity).
 		      arcMap("cost", cost).
 		      run();
 		  } else if (maxflow) {
 		    Digraph digraph;
 		    Node s, t;
 		    DoubleArcMap capacity(digraph);
 		    readDimacsMax(is, digraph, capacity, s, t);
 		    DigraphWriter<Digraph>(digraph, os).
 		      arcMap("capacity", capacity).
 		      node("source", s).
 		      node("target", t).
 		      run();
 		  } else if (shortestpath) {
 		    Digraph digraph;
 		    Node s;
 		    DoubleArcMap capacity(digraph);
 		    readDimacsSp(is, digraph, capacity, s);
 		    DigraphWriter<Digraph>(digraph, os).
 		      arcMap("capacity", capacity).
 		      node("source", s).
 		      run();
 		  } else if (capacitated) {
 		    Digraph digraph;
 		    DoubleArcMap capacity(digraph);
 		    readDimacsMax(is, digraph, capacity);
 		    DigraphWriter<Digraph>(digraph, os).
 		      arcMap("capacity", capacity).
 		      run();
 		  } else if (plain) {
 		    Digraph digraph;
 		    readDimacsMat(is, digraph);
 		    DigraphWriter<Digraph>(digraph, os).run();
 		  } else {
 		    cerr << "Invalid type error" << endl;
 		    return -1;
+		  }
 		  return 0;
+		}

0 comments (0 inline)

RhodeCode

Login to your account