00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
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':
00066 getline(is, str);
00067 break;
00068 case 'p':
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':
00075 if (problem=="sp") {
00076 is >> i;
00077 getline(is, str);
00078 s=nodes[i];
00079 }
00080 if (problem=="max" || problem=="min") {
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
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
00100 capacity.set(e, _cap);
00101
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 }
00219
00220 #endif //LEMON_DIMACS_H