tools/dimacs-to-lgf.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Thu, 12 Nov 2009 23:26:13 +0100
changeset 806 fa6f37d7a25b
parent 561 6e0525ec5355
child 1179 d7e25df22e88
permissions -rw-r--r--
Entirely rework CapacityScaling (#180)

- Use the new interface similarly to NetworkSimplex.
- Rework the implementation using an efficient internal structure
for handling the residual network. This improvement made the
code much faster (up to 2-5 times faster on large graphs).
- Handle GEQ supply type (LEQ is not supported).
- Handle negative costs for arcs of finite capacity.
(Note that this algorithm cannot handle arcs of negative cost
and infinite upper bound, thus it returns UNBOUNDED if such
an arc exists.)
- Extend the documentation.
     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 }