tools/dimacs-to-lgf.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 03 Apr 2009 18:59:15 +0200
changeset 655 6ac5d9ae1d3d
parent 402 24a2c6ee6cb0
child 608 6e0525ec5355
permissions -rw-r--r--
Support real types + numerical stability fix in NS (#254)

- Real types are supported by appropriate inicialization.
- A feature of the XTI spanning tree structure is removed to ensure
numerical stability (could cause problems using integer types).
The node potentials are updated always on the lower subtree,
in order to prevent overflow problems.
The former method isn't notably faster during to our tests.
alpar@400
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@400
     2
 *
alpar@400
     3
 * This file is a part of LEMON, a generic C++ optimization library.
alpar@400
     4
 *
alpar@463
     5
 * Copyright (C) 2003-2009
alpar@400
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@400
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@400
     8
 *
alpar@400
     9
 * Permission to use, modify and distribute this software is granted
alpar@400
    10
 * provided that this copyright notice appears in all copies. For
alpar@400
    11
 * precise terms see the accompanying LICENSE file.
alpar@400
    12
 *
alpar@400
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@400
    14
 * express or implied, and with no claim as to its suitability for any
alpar@400
    15
 * purpose.
alpar@400
    16
 *
alpar@400
    17
 */
alpar@400
    18
alpar@400
    19
///\ingroup tools
alpar@400
    20
///\file
alpar@400
    21
///\brief DIMACS to LGF converter.
alpar@400
    22
///
alpar@400
    23
/// This program converts various DIMACS formats to the LEMON Digraph Format
alpar@400
    24
/// (LGF).
alpar@400
    25
///
alpar@400
    26
/// See
alpar@400
    27
/// \verbatim
alpar@400
    28
///  dimacs-to-lgf --help
alpar@400
    29
/// \endverbatim
alpar@400
    30
/// for more info on usage.
alpar@400
    31
///
alpar@400
    32
alpar@400
    33
#include <iostream>
alpar@400
    34
#include <fstream>
alpar@400
    35
#include <cstring>
alpar@400
    36
alpar@400
    37
#include <lemon/smart_graph.h>
alpar@400
    38
#include <lemon/dimacs.h>
alpar@400
    39
#include <lemon/lgf_writer.h>
alpar@400
    40
alpar@400
    41
#include <lemon/arg_parser.h>
alpar@402
    42
#include <lemon/error.h>
alpar@400
    43
alpar@400
    44
using namespace std;
alpar@400
    45
using namespace lemon;
alpar@400
    46
alpar@400
    47
alpar@400
    48
int main(int argc, const char *argv[]) {
alpar@400
    49
  typedef SmartDigraph Digraph;
alpar@400
    50
alpar@400
    51
  typedef Digraph::Arc Arc;
alpar@400
    52
  typedef Digraph::Node Node;
alpar@400
    53
  typedef Digraph::ArcIt ArcIt;
alpar@400
    54
  typedef Digraph::NodeIt NodeIt;
alpar@400
    55
  typedef Digraph::ArcMap<double> DoubleArcMap;
alpar@400
    56
  typedef Digraph::NodeMap<double> DoubleNodeMap;
alpar@400
    57
alpar@400
    58
  std::string inputName;
alpar@400
    59
  std::string outputName;
alpar@400
    60
alpar@400
    61
  ArgParser ap(argc, argv);
alpar@402
    62
  ap.other("[INFILE [OUTFILE]]",
alpar@402
    63
           "If either the INFILE or OUTFILE file is missing the standard\n"
alpar@402
    64
           "     input/output will be used instead.")
alpar@400
    65
    .run();
alpar@400
    66
alpar@400
    67
  ifstream input;
alpar@402
    68
  ofstream output;
alpar@402
    69
alpar@402
    70
  switch(ap.files().size())
alpar@402
    71
    {
alpar@402
    72
    case 2:
alpar@402
    73
      output.open(ap.files()[1].c_str());
alpar@402
    74
      if (!output) {
alpar@402
    75
        throw IoError("Cannot open the file for writing", ap.files()[1]);
alpar@402
    76
      }
alpar@402
    77
    case 1:
alpar@402
    78
      input.open(ap.files()[0].c_str());
alpar@402
    79
      if (!input) {
alpar@402
    80
        throw IoError("File cannot be found", ap.files()[0]);
alpar@402
    81
      }
alpar@402
    82
    case 0:
alpar@402
    83
      break;
alpar@402
    84
    default:
alpar@402
    85
      cerr << ap.commandName() << ": too many arguments\n";
alpar@402
    86
      return 1;
alpar@402
    87
  }
alpar@402
    88
  istream& is = (ap.files().size()<1 ? cin : input);
alpar@402
    89
  ostream& os = (ap.files().size()<2 ? cout : output);
alpar@402
    90
alpar@402
    91
  DimacsDescriptor desc = dimacsType(is);
alpar@402
    92
  switch(desc.type)
alpar@402
    93
    {
alpar@402
    94
    case DimacsDescriptor::MIN:
alpar@402
    95
      {
alpar@402
    96
        Digraph digraph;
alpar@402
    97
        DoubleArcMap lower(digraph), capacity(digraph), cost(digraph);
alpar@402
    98
        DoubleNodeMap supply(digraph);
alpar@402
    99
        readDimacsMin(is, digraph, lower, capacity, cost, supply, desc);
alpar@402
   100
        DigraphWriter<Digraph>(digraph, os).
alpar@402
   101
          nodeMap("supply", supply).
alpar@402
   102
          arcMap("lower", lower).
alpar@402
   103
          arcMap("capacity", capacity).
alpar@402
   104
          arcMap("cost", cost).
alpar@402
   105
          attribute("problem","min").
alpar@402
   106
          run();
alpar@402
   107
      }
alpar@402
   108
      break;
alpar@402
   109
    case DimacsDescriptor::MAX:
alpar@402
   110
      {
alpar@402
   111
        Digraph digraph;
alpar@402
   112
        Node s, t;
alpar@402
   113
        DoubleArcMap capacity(digraph);
alpar@402
   114
        readDimacsMax(is, digraph, capacity, s, t, desc);
alpar@402
   115
        DigraphWriter<Digraph>(digraph, os).
alpar@402
   116
          arcMap("capacity", capacity).
alpar@402
   117
          node("source", s).
alpar@402
   118
          node("target", t).
alpar@402
   119
          attribute("problem","max").
alpar@402
   120
          run();
alpar@402
   121
      }
alpar@402
   122
      break;
alpar@402
   123
    case DimacsDescriptor::SP:
alpar@402
   124
      {
alpar@402
   125
        Digraph digraph;
alpar@402
   126
        Node s;
alpar@402
   127
        DoubleArcMap capacity(digraph);
alpar@402
   128
        readDimacsSp(is, digraph, capacity, s, desc);
alpar@402
   129
        DigraphWriter<Digraph>(digraph, os).
alpar@402
   130
          arcMap("capacity", capacity).
alpar@402
   131
          node("source", s).
alpar@402
   132
          attribute("problem","sp").
alpar@402
   133
          run();
alpar@402
   134
      }
alpar@402
   135
      break;
alpar@402
   136
    case DimacsDescriptor::MAT:
alpar@402
   137
      {
alpar@402
   138
        Digraph digraph;
alpar@402
   139
        readDimacsMat(is, digraph,desc);
alpar@402
   140
        DigraphWriter<Digraph>(digraph, os).
alpar@402
   141
          attribute("problem","mat").
alpar@402
   142
          run();
alpar@402
   143
      }
alpar@402
   144
      break;
alpar@402
   145
    default:
alpar@402
   146
      break;
alpar@400
   147
    }
alpar@400
   148
  return 0;
alpar@400
   149
}