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