tools/dimacs-to-lgf.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 24 Mar 2009 00:18:25 +0100
changeset 604 8c3112a66878
parent 387 24a2c6ee6cb0
child 561 6e0525ec5355
permissions -rw-r--r--
Use XTI implementation instead of ATI in NetworkSimplex (#234)

XTI (eXtended Threaded Index) is an imporved version of the widely
known ATI (Augmented Threaded Index) method for storing and updating
the spanning tree structure in Network Simplex algorithms.

In the ATI data structure three indices are stored for each node:
predecessor, thread and depth. In the XTI data structure depth is
replaced by the number of successors and the last successor
(according to the thread index).
     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 }