Port DIMACS tools from svn -r3516
authorAlpar Juttner <alpar@cs.elte.hu>
Thu, 27 Nov 2008 22:04:46 +0000
changeset 38550d96f2166d7
parent 384 fc6954b4fce4
child 386 9d1faab5e0f1
Port DIMACS tools from svn -r3516

Namely,
- apply migrate script
- apply unify sources
- break long lines
- Fixes the compilation
- dim_to_lgf -> dimacs-to-lgf
- better .hgignore
- shorten the doc of dimacs-to-lgf
.hgignore
lemon/Makefile.am
lemon/dimacs.h
tools/Makefile.am
tools/dimacs-to-lgf.cc
     1.1 --- a/.hgignore	Fri Nov 21 10:49:39 2008 +0000
     1.2 +++ b/.hgignore	Thu Nov 27 22:04:46 2008 +0000
     1.3 @@ -36,6 +36,7 @@
     1.4  ^build-aux/.*
     1.5  ^objs.*/.*
     1.6  ^test/[a-z_]*$
     1.7 +^tools/[a-z-_]*$
     1.8  ^demo/.*_demo$
     1.9  ^build/.*
    1.10  ^doc/gen-images/.*
     2.1 --- a/lemon/Makefile.am	Fri Nov 21 10:49:39 2008 +0000
     2.2 +++ b/lemon/Makefile.am	Thu Nov 27 22:04:46 2008 +0000
     2.3 @@ -27,6 +27,7 @@
     2.4          lemon/dfs.h \
     2.5          lemon/dijkstra.h \
     2.6          lemon/dim2.h \
     2.7 +        lemon/dimacs.h \
     2.8  	lemon/elevator.h \
     2.9  	lemon/error.h \
    2.10  	lemon/full_graph.h \
     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/lemon/dimacs.h	Thu Nov 27 22:04:46 2008 +0000
     3.3 @@ -0,0 +1,248 @@
     3.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     3.5 + *
     3.6 + * This file is a part of LEMON, a generic C++ optimization library.
     3.7 + *
     3.8 + * Copyright (C) 2003-2008
     3.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    3.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    3.11 + *
    3.12 + * Permission to use, modify and distribute this software is granted
    3.13 + * provided that this copyright notice appears in all copies. For
    3.14 + * precise terms see the accompanying LICENSE file.
    3.15 + *
    3.16 + * This software is provided "AS IS" with no warranty of any kind,
    3.17 + * express or implied, and with no claim as to its suitability for any
    3.18 + * purpose.
    3.19 + *
    3.20 + */
    3.21 +
    3.22 +#ifndef LEMON_DIMACS_H
    3.23 +#define LEMON_DIMACS_H
    3.24 +
    3.25 +#include <iostream>
    3.26 +#include <string>
    3.27 +#include <vector>
    3.28 +#include <lemon/maps.h>
    3.29 +
    3.30 +/// \ingroup dimacs_group
    3.31 +/// \file
    3.32 +/// \brief DIMACS file format reader.
    3.33 +
    3.34 +namespace lemon {
    3.35 +
    3.36 +  ///@defgroup dimacs_group DIMACS format
    3.37 +  ///\brief Read and write files in DIMACS format
    3.38 +  ///
    3.39 +  ///Tools to read a digraph from or write it to a file in DIMACS format
    3.40 +  ///data
    3.41 +  ///\ingroup io_group
    3.42 +
    3.43 +  /// \addtogroup dimacs_group
    3.44 +  /// @{
    3.45 +
    3.46 +  /// DIMACS min cost flow reader function.
    3.47 +  ///
    3.48 +  /// This function reads a min cost flow instance from DIMACS format,
    3.49 +  /// i.e. from DIMACS files having a line starting with
    3.50 +  /// \code
    3.51 +  ///   p min
    3.52 +  /// \endcode
    3.53 +  /// At the beginning \c g is cleared by \c g.clear(). The supply
    3.54 +  /// amount of the nodes are written to \c supply (signed). The
    3.55 +  /// lower bounds, capacities and costs of the arcs are written to
    3.56 +  /// \c lower, \c capacity and \c cost.
    3.57 +  template <typename Digraph, typename LowerMap,
    3.58 +    typename CapacityMap, typename CostMap,
    3.59 +    typename SupplyMap>
    3.60 +  void readDimacs( std::istream& is,
    3.61 +                   Digraph &g,
    3.62 +                   LowerMap& lower,
    3.63 +                   CapacityMap& capacity,
    3.64 +                   CostMap& cost,
    3.65 +                   SupplyMap& supply )
    3.66 +  {
    3.67 +    g.clear();
    3.68 +    std::vector<typename Digraph::Node> nodes;
    3.69 +    typename Digraph::Arc e;
    3.70 +    std::string problem, str;
    3.71 +    char c;
    3.72 +    int n, m;
    3.73 +    int i, j;
    3.74 +    typename SupplyMap::Value sup;
    3.75 +    typename CapacityMap::Value low;
    3.76 +    typename CapacityMap::Value cap;
    3.77 +    typename CostMap::Value co;
    3.78 +    while (is >> c) {
    3.79 +      switch (c) {
    3.80 +      case 'c': // comment line
    3.81 +        getline(is, str);
    3.82 +        break;
    3.83 +      case 'p': // problem definition line
    3.84 +        is >> problem >> n >> m;
    3.85 +        getline(is, str);
    3.86 +        if (problem != "min") return;
    3.87 +        nodes.resize(n + 1);
    3.88 +        for (int k = 1; k <= n; ++k) {
    3.89 +          nodes[k] = g.addNode();
    3.90 +          supply.set(nodes[k], 0);
    3.91 +        }
    3.92 +        break;
    3.93 +      case 'n': // node definition line
    3.94 +        is >> i >> sup;
    3.95 +        getline(is, str);
    3.96 +        supply.set(nodes[i], sup);
    3.97 +        break;
    3.98 +      case 'a': // arc (arc) definition line
    3.99 +        is >> i >> j >> low >> cap >> co;
   3.100 +        getline(is, str);
   3.101 +        e = g.addArc(nodes[i], nodes[j]);
   3.102 +        lower.set(e, low);
   3.103 +        if (cap >= 0)
   3.104 +          capacity.set(e, cap);
   3.105 +        else
   3.106 +          capacity.set(e, -1);
   3.107 +        cost.set(e, co);
   3.108 +        break;
   3.109 +      }
   3.110 +    }
   3.111 +  }
   3.112 +
   3.113 +  /// DIMACS max flow reader function.
   3.114 +  ///
   3.115 +  /// This function reads a max flow instance from DIMACS format,
   3.116 +  /// i.e. from DIMACS files having a line starting with
   3.117 +  /// \code
   3.118 +  ///   p max
   3.119 +  /// \endcode
   3.120 +  /// At the beginning \c g is cleared by \c g.clear(). The arc
   3.121 +  /// capacities are written to \c capacity and \c s and \c t are
   3.122 +  /// set to the source and the target nodes.
   3.123 +  template<typename Digraph, typename CapacityMap>
   3.124 +  void readDimacs(std::istream& is, Digraph &g, CapacityMap& capacity,
   3.125 +                  typename Digraph::Node &s, typename Digraph::Node &t) {
   3.126 +    g.clear();
   3.127 +    std::vector<typename Digraph::Node> nodes;
   3.128 +    typename Digraph::Arc e;
   3.129 +    std::string problem;
   3.130 +    char c, d;
   3.131 +    int n, m;
   3.132 +    int i, j;
   3.133 +    typename CapacityMap::Value _cap;
   3.134 +    std::string str;
   3.135 +    while (is >> c) {
   3.136 +      switch (c) {
   3.137 +      case 'c': // comment line
   3.138 +        getline(is, str);
   3.139 +        break;
   3.140 +      case 'p': // problem definition line
   3.141 +        is >> problem >> n >> m;
   3.142 +        getline(is, str);
   3.143 +        nodes.resize(n + 1);
   3.144 +        for (int k = 1; k <= n; ++k)
   3.145 +          nodes[k] = g.addNode();
   3.146 +        break;
   3.147 +      case 'n': // node definition line
   3.148 +        if (problem == "sp") { // shortest path problem
   3.149 +          is >> i;
   3.150 +          getline(is, str);
   3.151 +          s = nodes[i];
   3.152 +        }
   3.153 +        if (problem == "max") { // max flow problem
   3.154 +          is >> i >> d;
   3.155 +          getline(is, str);
   3.156 +          if (d == 's') s = nodes[i];
   3.157 +          if (d == 't') t = nodes[i];
   3.158 +        }
   3.159 +        break;
   3.160 +      case 'a': // arc (arc) definition line
   3.161 +        if (problem == "max" || problem == "sp") {
   3.162 +          is >> i >> j >> _cap;
   3.163 +          getline(is, str);
   3.164 +          e = g.addArc(nodes[i], nodes[j]);
   3.165 +          capacity.set(e, _cap);
   3.166 +        } else {
   3.167 +          is >> i >> j;
   3.168 +          getline(is, str);
   3.169 +          g.addArc(nodes[i], nodes[j]);
   3.170 +        }
   3.171 +        break;
   3.172 +      }
   3.173 +    }
   3.174 +  }
   3.175 +
   3.176 +  /// DIMACS shortest path reader function.
   3.177 +  ///
   3.178 +  /// This function reads a shortest path instance from DIMACS format,
   3.179 +  /// i.e. from DIMACS files having a line starting with
   3.180 +  /// \code
   3.181 +  ///   p sp
   3.182 +  /// \endcode
   3.183 +  /// At the beginning \c g is cleared by \c g.clear(). The arc
   3.184 +  /// capacities are written to \c capacity and \c s is set to the
   3.185 +  /// source node.
   3.186 +  template<typename Digraph, typename CapacityMap>
   3.187 +  void readDimacs(std::istream& is, Digraph &g, CapacityMap& capacity,
   3.188 +                  typename Digraph::Node &s) {
   3.189 +    readDimacs(is, g, capacity, s, s);
   3.190 +  }
   3.191 +
   3.192 +  /// DIMACS capacitated digraph reader function.
   3.193 +  ///
   3.194 +  /// This function reads an arc capacitated digraph instance from
   3.195 +  /// DIMACS format. At the beginning \c g is cleared by \c g.clear()
   3.196 +  /// and the arc capacities are written to \c capacity.
   3.197 +  template<typename Digraph, typename CapacityMap>
   3.198 +  void readDimacs(std::istream& is, Digraph &g, CapacityMap& capacity) {
   3.199 +    typename Digraph::Node u;
   3.200 +    readDimacs(is, g, capacity, u, u);
   3.201 +  }
   3.202 +
   3.203 +  /// DIMACS plain digraph reader function.
   3.204 +  ///
   3.205 +  /// This function reads a digraph without any designated nodes and
   3.206 +  /// maps from DIMACS format, i.e. from DIMACS files having a line
   3.207 +  /// starting with
   3.208 +  /// \code
   3.209 +  ///   p mat
   3.210 +  /// \endcode
   3.211 +  /// At the beginning \c g is cleared by \c g.clear().
   3.212 +  template<typename Digraph>
   3.213 +  void readDimacs(std::istream& is, Digraph &g) {
   3.214 +    typename Digraph::Node u;
   3.215 +    NullMap<typename Digraph::Arc, int> n;
   3.216 +    readDimacs(is, g, n, u, u);
   3.217 +  }
   3.218 +
   3.219 +  /// DIMACS plain digraph writer function.
   3.220 +  ///
   3.221 +  /// This function writes a digraph without any designated nodes and
   3.222 +  /// maps into DIMACS format, i.e. into DIMACS file having a line
   3.223 +  /// starting with
   3.224 +  /// \code
   3.225 +  ///   p mat
   3.226 +  /// \endcode
   3.227 +  template<typename Digraph>
   3.228 +  void writeDimacs(std::ostream& os, const Digraph &g) {
   3.229 +    typedef typename Digraph::NodeIt NodeIt;
   3.230 +    typedef typename Digraph::ArcIt ArcIt;
   3.231 +
   3.232 +    os << "c matching problem" << std::endl;
   3.233 +    os << "p mat " << g.nodeNum() << " " << g.arcNum() << std::endl;
   3.234 +
   3.235 +    typename Digraph::template NodeMap<int> nodes(g);
   3.236 +    int i = 1;
   3.237 +    for(NodeIt v(g); v != INVALID; ++v) {
   3.238 +      nodes.set(v, i);
   3.239 +      ++i;
   3.240 +    }
   3.241 +    for(ArcIt e(g); e != INVALID; ++e) {
   3.242 +      os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)]
   3.243 +         << std::endl;
   3.244 +    }
   3.245 +  }
   3.246 +
   3.247 +  /// @}
   3.248 +
   3.249 +} //namespace lemon
   3.250 +
   3.251 +#endif //LEMON_DIMACS_H
     4.1 --- a/tools/Makefile.am	Fri Nov 21 10:49:39 2008 +0000
     4.2 +++ b/tools/Makefile.am	Thu Nov 27 22:04:46 2008 +0000
     4.3 @@ -1,6 +1,10 @@
     4.4  if WANT_TOOLS
     4.5  
     4.6 -bin_PROGRAMS +=
     4.7 +bin_PROGRAMS += \
     4.8 +	tools/dimacs-to-lgf
     4.9 +
    4.10  dist_bin_SCRIPTS += tools/lemon-0.x-to-1.x.sh
    4.11  
    4.12  endif WANT_TOOLS
    4.13 +
    4.14 +tools_dimacs_to_lgf_SOURCES = tools/dimacs-to-lgf.cc
     5.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     5.2 +++ b/tools/dimacs-to-lgf.cc	Thu Nov 27 22:04:46 2008 +0000
     5.3 @@ -0,0 +1,168 @@
     5.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     5.5 + *
     5.6 + * This file is a part of LEMON, a generic C++ optimization library.
     5.7 + *
     5.8 + * Copyright (C) 2003-2008
     5.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    5.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    5.11 + *
    5.12 + * Permission to use, modify and distribute this software is granted
    5.13 + * provided that this copyright notice appears in all copies. For
    5.14 + * precise terms see the accompanying LICENSE file.
    5.15 + *
    5.16 + * This software is provided "AS IS" with no warranty of any kind,
    5.17 + * express or implied, and with no claim as to its suitability for any
    5.18 + * purpose.
    5.19 + *
    5.20 + */
    5.21 +
    5.22 +///\ingroup tools
    5.23 +///\file
    5.24 +///\brief DIMACS to LGF converter.
    5.25 +///
    5.26 +/// This program converts various DIMACS formats to the LEMON Digraph Format
    5.27 +/// (LGF).
    5.28 +///
    5.29 +/// See
    5.30 +/// \verbatim
    5.31 +///  dimacs-to-lgf --help
    5.32 +/// \endverbatim
    5.33 +/// for more info on usage.
    5.34 +///
    5.35 +
    5.36 +#include <iostream>
    5.37 +#include <fstream>
    5.38 +#include <cstring>
    5.39 +
    5.40 +#include <lemon/smart_graph.h>
    5.41 +#include <lemon/dimacs.h>
    5.42 +#include <lemon/lgf_writer.h>
    5.43 +
    5.44 +#include <lemon/arg_parser.h>
    5.45 +
    5.46 +using namespace std;
    5.47 +using namespace lemon;
    5.48 +
    5.49 +
    5.50 +int main(int argc, const char *argv[]) {
    5.51 +  typedef SmartDigraph Digraph;
    5.52 +
    5.53 +  typedef Digraph::Arc Arc;
    5.54 +  typedef Digraph::Node Node;
    5.55 +  typedef Digraph::ArcIt ArcIt;
    5.56 +  typedef Digraph::NodeIt NodeIt;
    5.57 +  typedef Digraph::ArcMap<double> DoubleArcMap;
    5.58 +  typedef Digraph::NodeMap<double> DoubleNodeMap;
    5.59 +
    5.60 +  std::string inputName;
    5.61 +  std::string outputName;
    5.62 +  std::string typeName;
    5.63 +
    5.64 +  bool mincostflow;
    5.65 +  bool maxflow;
    5.66 +  bool shortestpath;
    5.67 +  bool capacitated;
    5.68 +  bool plain;
    5.69 +
    5.70 +  bool version;
    5.71 +
    5.72 +  ArgParser ap(argc, argv);
    5.73 +  ap.refOption("-input",
    5.74 +               "use FILE as input instead of standard input",
    5.75 +               inputName).synonym("i", "-input")
    5.76 +    .refOption("-output",
    5.77 +               "use FILE as output instead of standard output",
    5.78 +               outputName).synonym("o", "-output")
    5.79 +    .refOption("-mincostflow",
    5.80 +               "set the type of the digraph to \"mincostflow\" digraph",
    5.81 +               mincostflow)
    5.82 +    .optionGroup("type", "-mincostflow").synonym("mcf", "-mincostflow")
    5.83 +    .refOption("-maxflow",
    5.84 +               "set the type of the digraph to \"maxflow\" digraph",
    5.85 +               maxflow)
    5.86 +    .optionGroup("type", "-maxflow").synonym("mf", "-maxflow")
    5.87 +    .refOption("-shortestpath",
    5.88 +               "set the type of the digraph to \"shortestpath\" digraph",
    5.89 +               shortestpath)
    5.90 +    .optionGroup("type", "-shortestpath").synonym("sp", "-shortestpath")
    5.91 +    .refOption("-capacitated",
    5.92 +               "set the type of the digraph to \"capacitated\" digraph",
    5.93 +               capacitated)
    5.94 +    .optionGroup("type", "-capacitated").synonym("cap", "-capacitated")
    5.95 +    .refOption("-plain",
    5.96 +               "set the type of the digraph to \"plain\" digraph",
    5.97 +               plain)
    5.98 +    .optionGroup("type", "-plain").synonym("pl", "-plain")
    5.99 +    .onlyOneGroup("type")
   5.100 +    .mandatoryGroup("type")
   5.101 +    .refOption("-version", "show version information", version)
   5.102 +    .synonym("v", "-version")
   5.103 +    .run();
   5.104 +
   5.105 +  ifstream input;
   5.106 +  if (!inputName.empty()) {
   5.107 +    input.open(inputName.c_str());
   5.108 +    if (!input) {
   5.109 +      cerr << "File open error" << endl;
   5.110 +      return -1;
   5.111 +    }
   5.112 +  }
   5.113 +  istream& is = (inputName.empty() ? cin : input);
   5.114 +
   5.115 +  ofstream output;
   5.116 +  if (!outputName.empty()) {
   5.117 +    output.open(outputName.c_str());
   5.118 +    if (!output) {
   5.119 +      cerr << "File open error" << endl;
   5.120 +      return -1;
   5.121 +    }
   5.122 +  }
   5.123 +  ostream& os = (outputName.empty() ? cout : output);
   5.124 +
   5.125 +  if (mincostflow) {
   5.126 +    Digraph digraph;
   5.127 +    DoubleArcMap lower(digraph), capacity(digraph), cost(digraph);
   5.128 +    DoubleNodeMap supply(digraph);
   5.129 +    readDimacs(is, digraph, lower, capacity, cost, supply);
   5.130 +    DigraphWriter<Digraph>(digraph, os).
   5.131 +      nodeMap("supply", supply).
   5.132 +      arcMap("lower", lower).
   5.133 +      arcMap("capacity", capacity).
   5.134 +      arcMap("cost", cost).
   5.135 +      run();
   5.136 +  } else if (maxflow) {
   5.137 +    Digraph digraph;
   5.138 +    Node s, t;
   5.139 +    DoubleArcMap capacity(digraph);
   5.140 +    readDimacs(is, digraph, capacity, s, t);
   5.141 +    DigraphWriter<Digraph>(digraph, os).
   5.142 +      arcMap("capacity", capacity).
   5.143 +      node("source", s).
   5.144 +      node("target", t).
   5.145 +      run();
   5.146 +  } else if (shortestpath) {
   5.147 +    Digraph digraph;
   5.148 +    Node s;
   5.149 +    DoubleArcMap capacity(digraph);
   5.150 +    readDimacs(is, digraph, capacity, s);
   5.151 +    DigraphWriter<Digraph>(digraph, os).
   5.152 +      arcMap("capacity", capacity).
   5.153 +      node("source", s).
   5.154 +      run();
   5.155 +  } else if (capacitated) {
   5.156 +    Digraph digraph;
   5.157 +    DoubleArcMap capacity(digraph);
   5.158 +    readDimacs(is, digraph, capacity);
   5.159 +    DigraphWriter<Digraph>(digraph, os).
   5.160 +      arcMap("capacity", capacity).
   5.161 +      run();
   5.162 +  } else if (plain) {
   5.163 +    Digraph digraph;
   5.164 +    readDimacs(is, digraph);
   5.165 +    DigraphWriter<Digraph>(digraph, os).run();
   5.166 +  } else {
   5.167 +    cerr << "Invalid type error" << endl;
   5.168 +    return -1;
   5.169 +  }
   5.170 +  return 0;
   5.171 +}