00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
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':
00076 getline(is, str);
00077 break;
00078 case 'p':
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':
00085 if (problem=="sp") {
00086 is >> i;
00087 getline(is, str);
00088 s=nodes[i];
00089 }
00090 if (problem=="max" || problem=="min") {
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
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
00110 capacity.set(e, _cap);
00111
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 }
00229
00230 #endif //LEMON_DIMACS_H