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