1.1 --- a/src/hugo/dimacs.h Fri May 07 10:22:30 2004 +0000
1.2 +++ b/src/hugo/dimacs.h Fri May 07 10:34:36 2004 +0000
1.3 @@ -7,103 +7,26 @@
1.4 #include <vector>
1.5 #include <hugo/maps.h>
1.6
1.7 +/// \ingroup misc
1.8 /// \file
1.9 /// \brief Dimacs file format reader.
1.10
1.11 namespace hugo {
1.12
1.13 - /// Dimacs flow file format reader function.
1.14
1.15 - /// This function reads a flow instance from dimacs flow format.
1.16 - /// At the beginning \c g is cleared by \c g.clear().
1.17 - /// If the data coming from \c is is a max flow problem instance, then
1.18 - /// \c s and \c t will be respectively the source and target nodes
1.19 - /// and \c capacity will contain the edge capacities.
1.20 - /// If the data is a shortest path problem instance then \c s will be the
1.21 - /// source node and \c capacity will contain the edge lengths.
1.22 + /// \addtogroup misc
1.23 + /// @{
1.24 +
1.25 + /// Dimacs min cost flow reader function.
1.26 +
1.27 + /// This function reads a min cost flow instance from dimacs format,
1.28 + /// i.e. from dimacs files having a line starting with \c p \c "min".
1.29 + /// At the beginning \c g is cleared by \c g.clear(). The edge
1.30 + /// capacities are written to \c capacity, \c s and \c t are set to
1.31 + /// the source and the target nodes resp. and the cost of the edges
1.32 + /// are written to \c cost.
1.33 ///
1.34 - ///\author Marton Makai
1.35 - template<typename Graph, typename CapacityMap>
1.36 - void readDimacsMaxFlow(std::istream& is, Graph &g,
1.37 - typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) {
1.38 - g.clear();
1.39 - int cap;
1.40 - char d;
1.41 - std::string problem;
1.42 - char c;
1.43 - int i, j;
1.44 - std::string str;
1.45 - int n, m;
1.46 - typename Graph::Edge e;
1.47 - std::vector<typename Graph::Node> nodes;
1.48 - while (is>>c) {
1.49 - switch (c) {
1.50 - case 'c': //comment
1.51 - getline(is, str);
1.52 - break;
1.53 - case 'p': //problem definition
1.54 - is >> problem >> n >> m;
1.55 - getline(is, str);
1.56 - nodes.resize(n+1);
1.57 - for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
1.58 - break;
1.59 - case 'n': //node definition
1.60 - if (problem=="sp") { //shortest path problem
1.61 - is >> i;
1.62 - getline(is, str);
1.63 - s=nodes[i];
1.64 - }
1.65 - if (problem=="max") { //max flow problem
1.66 - is >> i >> d;
1.67 - getline(is, str);
1.68 - if (d=='s') s=nodes[i];
1.69 - if (d=='t') t=nodes[i];
1.70 - }
1.71 - break;
1.72 - case 'a':
1.73 - is >> i >> j >> cap;
1.74 - getline(is, str);
1.75 - e=g.addEdge(nodes[i], nodes[j]);
1.76 - capacity.update();
1.77 - capacity.set(e, cap);
1.78 - break;
1.79 - }
1.80 - }
1.81 - }
1.82 -
1.83 - /// matching problem
1.84 - template<typename Graph>
1.85 - void readDimacs(std::istream& is, Graph &g) {
1.86 - typename Graph::Node u;
1.87 - NullMap<typename Graph::Edge, int> n;
1.88 - readDimacs(is, g, n, u, u, n);
1.89 - }
1.90 -
1.91 - /// sg problem
1.92 - template<typename Graph, typename CapacityMap>
1.93 - void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
1.94 - typename Graph::Node u;
1.95 - NullMap<typename Graph::Edge, int> n;
1.96 - readDimacs(is, g, capacity, u, u, n);
1.97 - }
1.98 -
1.99 - /// shortest path problem
1.100 - template<typename Graph, typename CapacityMap>
1.101 - void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
1.102 - typename Graph::Node &s) {
1.103 - NullMap<typename Graph::Edge, int> n;
1.104 - readDimacs(is, g, capacity, s, s, n);
1.105 - }
1.106 -
1.107 - /// max flow problem
1.108 - template<typename Graph, typename CapacityMap>
1.109 - void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
1.110 - typename Graph::Node &s, typename Graph::Node &t) {
1.111 - NullMap<typename Graph::Edge, int> n;
1.112 - readDimacs(is, g, capacity, s, t, n);
1.113 - }
1.114 -
1.115 - /// min cost flow problem
1.116 + /// \author Marton Makai
1.117 template<typename Graph, typename CapacityMap, typename CostMap>
1.118 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
1.119 typename Graph::Node &s, typename Graph::Node &t,
1.120 @@ -144,26 +67,26 @@
1.121 }
1.122 break;
1.123 case 'a':
1.124 - if ( problem == "mat" ) {
1.125 - is >> i >> j;
1.126 - getline(is, str);
1.127 - g.addEdge(nodes[i], nodes[j]);
1.128 - }
1.129 if ( problem == "max" || problem == "sp") {
1.130 is >> i >> j >> _cap;
1.131 getline(is, str);
1.132 e=g.addEdge(nodes[i], nodes[j]);
1.133 capacity.update();
1.134 capacity.set(e, _cap);
1.135 - }
1.136 - if ( problem == "min" ) {
1.137 - is >> i >> j >> _cap >> _cost;
1.138 - getline(is, str);
1.139 - e=g.addEdge(nodes[i], nodes[j]);
1.140 - capacity.update();
1.141 - capacity.set(e, _cap);
1.142 - cost.update();
1.143 - cost.set(e, _cost);
1.144 + } else {
1.145 + if ( problem == "min" ) {
1.146 + is >> i >> j >> _cap >> _cost;
1.147 + getline(is, str);
1.148 + e=g.addEdge(nodes[i], nodes[j]);
1.149 + capacity.update();
1.150 + capacity.set(e, _cap);
1.151 + cost.update();
1.152 + cost.set(e, _cost);
1.153 + } else {
1.154 + is >> i >> j;
1.155 + getline(is, str);
1.156 + g.addEdge(nodes[i], nodes[j]);
1.157 + }
1.158 }
1.159 break;
1.160 }
1.161 @@ -171,6 +94,72 @@
1.162 }
1.163
1.164
1.165 + /// Dimacs max flow reader function.
1.166 +
1.167 + /// This function reads a max flow instance from dimacs format,
1.168 + /// i.e. from dimacs files having a line starting with \c p \c
1.169 + /// "max". At the beginning \c g is cleared by \c g.clear(). The
1.170 + /// edge capacities are written to \c capacity and \c s and \c t are
1.171 + /// set to the source and the target nodes.
1.172 + ///
1.173 + /// \author Marton Makai
1.174 + template<typename Graph, typename CapacityMap>
1.175 + void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
1.176 + typename Graph::Node &s, typename Graph::Node &t) {
1.177 + NullMap<typename Graph::Edge, int> n;
1.178 + readDimacs(is, g, capacity, s, t, n);
1.179 + }
1.180 +
1.181 +
1.182 + /// Dimacs shortest path reader function.
1.183 +
1.184 + /// This function reads a shortest path instance from dimacs format,
1.185 + /// i.e. from dimacs files having a line starting with \c p \c "sp".
1.186 + /// At the beginning \c g is cleared by \c g.clear(). The edge
1.187 + /// capacities are written to \c capacity and \c s is set to the
1.188 + /// source node.
1.189 + ///
1.190 + /// \author Marton Makai
1.191 + template<typename Graph, typename CapacityMap>
1.192 + void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
1.193 + typename Graph::Node &s) {
1.194 + NullMap<typename Graph::Edge, int> n;
1.195 + readDimacs(is, g, capacity, s, s, n);
1.196 + }
1.197 +
1.198 +
1.199 + /// Dimacs capacitated graph reader function.
1.200 +
1.201 + /// This function reads an edge capacitated graph instance from
1.202 + /// dimacs format. At the beginning \c g is cleared by \c g.clear()
1.203 + /// and the edge capacities are written to \c capacity.
1.204 + ///
1.205 + /// \author Marton Makai
1.206 + template<typename Graph, typename CapacityMap>
1.207 + void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
1.208 + typename Graph::Node u;
1.209 + NullMap<typename Graph::Edge, int> n;
1.210 + readDimacs(is, g, capacity, u, u, n);
1.211 + }
1.212 +
1.213 +
1.214 + /// Dimacs plain graph reader function.
1.215 +
1.216 + /// This function reads a graph without any designated nodes and
1.217 + /// maps from dimacs format, i.e. from dimacs files having a line
1.218 + /// starting with \c p \c "mat". At the beginning \c g is cleared
1.219 + /// by \c g.clear().
1.220 + ///
1.221 + /// \author Marton Makai
1.222 + template<typename Graph>
1.223 + void readDimacs(std::istream& is, Graph &g) {
1.224 + typename Graph::Node u;
1.225 + NullMap<typename Graph::Edge, int> n;
1.226 + readDimacs(is, g, n, u, u, n);
1.227 + }
1.228 +
1.229 +
1.230 +
1.231
1.232 /// write matching problem
1.233 template<typename Graph>
1.234 @@ -199,7 +188,56 @@
1.235 }
1.236
1.237
1.238 + /// @}
1.239
1.240 } //namespace hugo
1.241
1.242 #endif //HUGO_DIMACS_H
1.243 +
1.244 +// template<typename Graph, typename CapacityMap>
1.245 +// void readDimacsMaxFlow(std::istream& is, Graph &g,
1.246 +// typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) {
1.247 +// g.clear();
1.248 +// int cap;
1.249 +// char d;
1.250 +// std::string problem;
1.251 +// char c;
1.252 +// int i, j;
1.253 +// std::string str;
1.254 +// int n, m;
1.255 +// typename Graph::Edge e;
1.256 +// std::vector<typename Graph::Node> nodes;
1.257 +// while (is>>c) {
1.258 +// switch (c) {
1.259 +// case 'c': //comment
1.260 +// getline(is, str);
1.261 +// break;
1.262 +// case 'p': //problem definition
1.263 +// is >> problem >> n >> m;
1.264 +// getline(is, str);
1.265 +// nodes.resize(n+1);
1.266 +// for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
1.267 +// break;
1.268 +// case 'n': //node definition
1.269 +// if (problem=="sp") { //shortest path problem
1.270 +// is >> i;
1.271 +// getline(is, str);
1.272 +// s=nodes[i];
1.273 +// }
1.274 +// if (problem=="max") { //max flow problem
1.275 +// is >> i >> d;
1.276 +// getline(is, str);
1.277 +// if (d=='s') s=nodes[i];
1.278 +// if (d=='t') t=nodes[i];
1.279 +// }
1.280 +// break;
1.281 +// case 'a':
1.282 +// is >> i >> j >> cap;
1.283 +// getline(is, str);
1.284 +// e=g.addEdge(nodes[i], nodes[j]);
1.285 +// capacity.update();
1.286 +// capacity.set(e, cap);
1.287 +// break;
1.288 +// }
1.289 +// }
1.290 +// }