dimacs.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  *
00003  * This file is a part of LEMON, a generic C++ optimization library
00004  *
00005  * Copyright (C) 2003-2006
00006  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00007  * (Egervary Research Group on Combinatorial Optimization, EGRES).
00008  *
00009  * Permission to use, modify and distribute this software is granted
00010  * provided that this copyright notice appears in all copies. For
00011  * precise terms see the accompanying LICENSE file.
00012  *
00013  * This software is provided "AS IS" with no warranty of any kind,
00014  * express or implied, and with no claim as to its suitability for any
00015  * purpose.
00016  *
00017  */
00018 
00019 #ifndef LEMON_DIMACS_H
00020 #define LEMON_DIMACS_H
00021 
00022 #include <iostream>
00023 #include <string>
00024 #include <vector>
00025 #include <lemon/maps.h>
00026 #include <lemon/invalid.h>
00027 
00031 
00032 namespace lemon {
00033 
00041 
00044 
00046 
00058   template<typename Graph, typename CapacityMap, typename CostMap>
00059   void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 
00060                   typename Graph::Node &s, typename Graph::Node &t, 
00061                   CostMap& cost) {
00062     g.clear();
00063     typename CapacityMap::Value _cap;
00064     typename CostMap::Value _cost;
00065     char d;
00066     std::string problem;
00067     char c;
00068     int i, j;
00069     std::string str;
00070     int n, m; 
00071     typename Graph::Edge e;
00072     std::vector<typename Graph::Node> nodes;
00073     while (is>>c) {
00074       switch (c) {
00075       case 'c': //comment
00076         getline(is, str);
00077         break;
00078       case 'p': //problem definition
00079         is >> problem >> n >> m;
00080         getline(is, str);
00081         nodes.resize(n+1);
00082         for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
00083         break;
00084       case 'n': //node definition
00085         if (problem=="sp") { //shortest path problem
00086           is >> i;
00087           getline(is, str);
00088           s=nodes[i];
00089         }
00090         if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem
00091           is >> i >> d;
00092           getline(is, str);
00093           if (d=='s') s=nodes[i];
00094           if (d=='t') t=nodes[i];
00095         }
00096         break;
00097       case 'a':
00098         if ( problem == "max" || problem == "sp") {
00099           is >> i >> j >> _cap;
00100           getline(is, str);
00101           e=g.addEdge(nodes[i], nodes[j]);
00102           //capacity.update();
00103           capacity.set(e, _cap);
00104         } else {
00105           if ( problem == "min" ) {
00106             is >> i >> j >> _cap >> _cost;
00107             getline(is, str);
00108             e=g.addEdge(nodes[i], nodes[j]);
00109             //capacity.update();
00110             capacity.set(e, _cap);
00111             //cost.update();
00112             cost.set(e, _cost);
00113           } else {
00114             is >> i >> j;
00115             getline(is, str);
00116             g.addEdge(nodes[i], nodes[j]);
00117           }
00118         }
00119         break;
00120       }
00121     }
00122   }
00123 
00124 
00126 
00137   template<typename Graph, typename CapacityMap>
00138   void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 
00139                   typename Graph::Node &s, typename Graph::Node &t) {
00140     NullMap<typename Graph::Edge, int> n;
00141     readDimacs(is, g, capacity, s, t, n);
00142   }
00143 
00144 
00146 
00157   template<typename Graph, typename CapacityMap>
00158   void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 
00159                   typename Graph::Node &s) {
00160     NullMap<typename Graph::Edge, int> n;
00161     readDimacs(is, g, capacity, s, s, n);
00162   }
00163 
00164 
00166 
00172   template<typename Graph, typename CapacityMap>
00173   void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
00174     typename Graph::Node u;
00175     NullMap<typename Graph::Edge, int> n;
00176     readDimacs(is, g, capacity, u, u, n);
00177   }
00178 
00179 
00181 
00192   template<typename Graph>
00193   void readDimacs(std::istream& is, Graph &g) {
00194     typename Graph::Node u;
00195     NullMap<typename Graph::Edge, int> n;
00196     readDimacs(is, g, n, u, u, n);
00197   }
00198   
00199 
00200 
00201   
00203   template<typename Graph>
00204   void writeDimacs(std::ostream& os, const Graph &g) {
00205     typedef typename Graph::NodeIt NodeIt;
00206     typedef typename Graph::EdgeIt EdgeIt;  
00207     
00208     typename Graph::template NodeMap<int> nodes(g);
00209 
00210     os << "c matching problem" << std::endl;
00211 
00212     int i=1;
00213     for(NodeIt v(g); v!=INVALID; ++v) {
00214       nodes.set(v, i);
00215       ++i;
00216     }    
00217     
00218     os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
00219 
00220     for(EdgeIt e(g); e!=INVALID; ++e) {
00221       os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)] << std::endl; 
00222     }
00223 
00224   }
00225 
00227 
00228 } //namespace lemon
00229 
00230 #endif //LEMON_DIMACS_H

Generated on Fri Feb 3 18:36:34 2006 for LEMON by  doxygen 1.4.6