tools/dimacs-to-lgf.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 15 Mar 2011 19:32:21 +0100
changeset 1047 ddd3c0d3d9bf
parent 608 6e0525ec5355
child 1397 d7e25df22e88
permissions -rw-r--r--
Implement the scaling Price Refinement heuristic in CostScaling (#417)
instead of Early Termination.

These two heuristics are similar, but the newer one is faster
and not only makes it possible to skip some epsilon phases, but
it can improve the performance of the other phases, as well.
     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 /// \code
    28 ///   dimacs-to-lgf --help
    29 /// \endcode
    30 /// for more info on the usage.
    31 
    32 #include <iostream>
    33 #include <fstream>
    34 #include <cstring>
    35 
    36 #include <lemon/smart_graph.h>
    37 #include <lemon/dimacs.h>
    38 #include <lemon/lgf_writer.h>
    39 
    40 #include <lemon/arg_parser.h>
    41 #include <lemon/error.h>
    42 
    43 using namespace std;
    44 using namespace lemon;
    45 
    46 
    47 int main(int argc, const char *argv[]) {
    48   typedef SmartDigraph Digraph;
    49 
    50   typedef Digraph::Arc Arc;
    51   typedef Digraph::Node Node;
    52   typedef Digraph::ArcIt ArcIt;
    53   typedef Digraph::NodeIt NodeIt;
    54   typedef Digraph::ArcMap<double> DoubleArcMap;
    55   typedef Digraph::NodeMap<double> DoubleNodeMap;
    56 
    57   std::string inputName;
    58   std::string outputName;
    59 
    60   ArgParser ap(argc, argv);
    61   ap.other("[INFILE [OUTFILE]]",
    62            "If either the INFILE or OUTFILE file is missing the standard\n"
    63            "     input/output will be used instead.")
    64     .run();
    65 
    66   ifstream input;
    67   ofstream output;
    68 
    69   switch(ap.files().size())
    70     {
    71     case 2:
    72       output.open(ap.files()[1].c_str());
    73       if (!output) {
    74         throw IoError("Cannot open the file for writing", ap.files()[1]);
    75       }
    76     case 1:
    77       input.open(ap.files()[0].c_str());
    78       if (!input) {
    79         throw IoError("File cannot be found", ap.files()[0]);
    80       }
    81     case 0:
    82       break;
    83     default:
    84       cerr << ap.commandName() << ": too many arguments\n";
    85       return 1;
    86   }
    87   istream& is = (ap.files().size()<1 ? cin : input);
    88   ostream& os = (ap.files().size()<2 ? cout : output);
    89 
    90   DimacsDescriptor desc = dimacsType(is);
    91   switch(desc.type)
    92     {
    93     case DimacsDescriptor::MIN:
    94       {
    95         Digraph digraph;
    96         DoubleArcMap lower(digraph), capacity(digraph), cost(digraph);
    97         DoubleNodeMap supply(digraph);
    98         readDimacsMin(is, digraph, lower, capacity, cost, supply, 0, desc);
    99         DigraphWriter<Digraph>(digraph, os).
   100           nodeMap("supply", supply).
   101           arcMap("lower", lower).
   102           arcMap("capacity", capacity).
   103           arcMap("cost", cost).
   104           attribute("problem","min").
   105           run();
   106       }
   107       break;
   108     case DimacsDescriptor::MAX:
   109       {
   110         Digraph digraph;
   111         Node s, t;
   112         DoubleArcMap capacity(digraph);
   113         readDimacsMax(is, digraph, capacity, s, t, 0, desc);
   114         DigraphWriter<Digraph>(digraph, os).
   115           arcMap("capacity", capacity).
   116           node("source", s).
   117           node("target", t).
   118           attribute("problem","max").
   119           run();
   120       }
   121       break;
   122     case DimacsDescriptor::SP:
   123       {
   124         Digraph digraph;
   125         Node s;
   126         DoubleArcMap capacity(digraph);
   127         readDimacsSp(is, digraph, capacity, s, desc);
   128         DigraphWriter<Digraph>(digraph, os).
   129           arcMap("capacity", capacity).
   130           node("source", s).
   131           attribute("problem","sp").
   132           run();
   133       }
   134       break;
   135     case DimacsDescriptor::MAT:
   136       {
   137         Digraph digraph;
   138         readDimacsMat(is, digraph,desc);
   139         DigraphWriter<Digraph>(digraph, os).
   140           attribute("problem","mat").
   141           run();
   142       }
   143       break;
   144     default:
   145       break;
   146     }
   147   return 0;
   148 }