Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

dimacs.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  * src/lemon/dimacs.h - Part of LEMON, a generic C++ optimization library
00003  *
00004  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00005  * (Egervary Combinatorial Optimization Research Group, EGRES).
00006  *
00007  * Permission to use, modify and distribute this software is granted
00008  * provided that this copyright notice appears in all copies. For
00009  * precise terms see the accompanying LICENSE file.
00010  *
00011  * This software is provided "AS IS" with no warranty of any kind,
00012  * express or implied, and with no claim as to its suitability for any
00013  * purpose.
00014  *
00015  */
00016 
00017 #ifndef LEMON_DIMACS_H
00018 #define LEMON_DIMACS_H
00019 
00020 #include <iostream>
00021 #include <string>
00022 #include <vector>
00023 #include <lemon/maps.h>
00024 
00028 
00029 namespace lemon {
00030 
00031 
00034 
00036 
00048   template<typename Graph, typename CapacityMap, typename CostMap>
00049   void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 
00050                   typename Graph::Node &s, typename Graph::Node &t, 
00051                   CostMap& cost) {
00052     g.clear();
00053     typename CapacityMap::Value _cap;
00054     typename CostMap::Value _cost;
00055     char d;
00056     std::string problem;
00057     char c;
00058     int i, j;
00059     std::string str;
00060     int n, m; 
00061     typename Graph::Edge e;
00062     std::vector<typename Graph::Node> nodes;
00063     while (is>>c) {
00064       switch (c) {
00065       case 'c': //comment
00066         getline(is, str);
00067         break;
00068       case 'p': //problem definition
00069         is >> problem >> n >> m;
00070         getline(is, str);
00071         nodes.resize(n+1);
00072         for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
00073         break;
00074       case 'n': //node definition
00075         if (problem=="sp") { //shortest path problem
00076           is >> i;
00077           getline(is, str);
00078           s=nodes[i];
00079         }
00080         if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem
00081           is >> i >> d;
00082           getline(is, str);
00083           if (d=='s') s=nodes[i];
00084           if (d=='t') t=nodes[i];
00085         }
00086         break;
00087       case 'a':
00088         if ( problem == "max" || problem == "sp") {
00089           is >> i >> j >> _cap;
00090           getline(is, str);
00091           e=g.addEdge(nodes[i], nodes[j]);
00092           //capacity.update();
00093           capacity.set(e, _cap);
00094         } else {
00095           if ( problem == "min" ) {
00096             is >> i >> j >> _cap >> _cost;
00097             getline(is, str);
00098             e=g.addEdge(nodes[i], nodes[j]);
00099             //capacity.update();
00100             capacity.set(e, _cap);
00101             //cost.update();
00102             cost.set(e, _cost);
00103           } else {
00104             is >> i >> j;
00105             getline(is, str);
00106             g.addEdge(nodes[i], nodes[j]);
00107           }
00108         }
00109         break;
00110       }
00111     }
00112   }
00113 
00114 
00116 
00127   template<typename Graph, typename CapacityMap>
00128   void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 
00129                   typename Graph::Node &s, typename Graph::Node &t) {
00130     NullMap<typename Graph::Edge, int> n;
00131     readDimacs(is, g, capacity, s, t, n);
00132   }
00133 
00134 
00136 
00147   template<typename Graph, typename CapacityMap>
00148   void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 
00149                   typename Graph::Node &s) {
00150     NullMap<typename Graph::Edge, int> n;
00151     readDimacs(is, g, capacity, s, s, n);
00152   }
00153 
00154 
00156 
00162   template<typename Graph, typename CapacityMap>
00163   void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
00164     typename Graph::Node u;
00165     NullMap<typename Graph::Edge, int> n;
00166     readDimacs(is, g, capacity, u, u, n);
00167   }
00168 
00169 
00171 
00182   template<typename Graph>
00183   void readDimacs(std::istream& is, Graph &g) {
00184     typename Graph::Node u;
00185     NullMap<typename Graph::Edge, int> n;
00186     readDimacs(is, g, n, u, u, n);
00187   }
00188   
00189 
00190 
00191   
00193   template<typename Graph>
00194   void writeDimacs(std::ostream& os, const Graph &g) {
00195     typedef typename Graph::NodeIt NodeIt;
00196     typedef typename Graph::EdgeIt EdgeIt;  
00197     
00198     typename Graph::template NodeMap<int> nodes(g);
00199 
00200     os << "c matching problem" << std::endl;
00201 
00202     int i=1;
00203     for(NodeIt v(g); v!=INVALID; ++v) {
00204       nodes.set(v, i);
00205       ++i;
00206     }    
00207     
00208     os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
00209 
00210     for(EdgeIt e(g); e!=INVALID; ++e) {
00211       os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)] << std::endl; 
00212     }
00213 
00214   }
00215 
00217 
00218 } //namespace lemon
00219 
00220 #endif //LEMON_DIMACS_H

Generated on Sat Mar 19 10:58:39 2005 for LEMON by  doxygen 1.4.1