1.1 --- a/src/include/dimacs.h Tue May 04 14:54:21 2004 +0000
1.2 +++ b/src/include/dimacs.h Tue May 04 16:16:49 2004 +0000
1.3 @@ -5,6 +5,7 @@
1.4 #include <iostream>
1.5 #include <string>
1.6 #include <vector>
1.7 +#include <maps.h>
1.8
1.9 /// \file
1.10 /// \brief Dimacs file format reader.
1.11 @@ -23,7 +24,8 @@
1.12 ///
1.13 ///\author Marton Makai
1.14 template<typename Graph, typename CapacityMap>
1.15 - void readDimacsMaxFlow(std::istream& is, Graph &g, typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) {
1.16 + void readDimacsMaxFlow(std::istream& is, Graph &g,
1.17 + typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) {
1.18 g.clear();
1.19 int cap;
1.20 char d;
1.21 @@ -68,7 +70,137 @@
1.22 }
1.23 }
1.24 }
1.25 +
1.26 + /// matching problem
1.27 + template<typename Graph>
1.28 + void readDimacs(std::istream& is, Graph &g) {
1.29 + typename Graph::Node u;
1.30 + NullMap<typename Graph::Edge, int> n;
1.31 + readDimacs(is, g, n, u, u, n);
1.32 + std::cout<<"igen en.";
1.33 + }
1.34 +
1.35 + /// sg problem
1.36 + template<typename Graph, typename CapacityMap>
1.37 + void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
1.38 + typename Graph::Node u;
1.39 + NullMap<typename Graph::Edge, int> n;
1.40 + readDimacs(is, g, cap, u, u, n);
1.41 + }
1.42 +
1.43 + /// shortest path problem
1.44 + template<typename Graph, typename CapacityMap>
1.45 + void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
1.46 + typename Graph::Node &s) {
1.47 + NullMap<typename Graph::Edge, int> n;
1.48 + readDimacs(is, g, capacity, s, s, n);
1.49 + }
1.50 +
1.51 + /// max flow problem
1.52 + template<typename Graph, typename CapacityMap>
1.53 + void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
1.54 + typename Graph::Node &s, typename Graph::Node &t) {
1.55 + NullMap<typename Graph::Edge, int> n;
1.56 + readDimacs(is, g, capacity, s, t, n);
1.57 + }
1.58 +
1.59 + /// min cost flow problem
1.60 + template<typename Graph, typename CapacityMap, typename CostMap>
1.61 + void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
1.62 + typename Graph::Node &s, typename Graph::Node &t,
1.63 + CostMap& cost) {
1.64 + g.clear();
1.65 + typename CapacityMap::ValueType _cap;
1.66 + typename CostMap::ValueType _cost;
1.67 + char d;
1.68 + std::string problem;
1.69 + char c;
1.70 + int i, j;
1.71 + std::string str;
1.72 + int n, m;
1.73 + typename Graph::Edge e;
1.74 + std::vector<typename Graph::Node> nodes;
1.75 + while (is>>c) {
1.76 + switch (c) {
1.77 + case 'c': //comment
1.78 + getline(is, str);
1.79 + break;
1.80 + case 'p': //problem definition
1.81 + is >> problem >> n >> m;
1.82 + getline(is, str);
1.83 + nodes.resize(n+1);
1.84 + for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
1.85 + break;
1.86 + case 'n': //node definition
1.87 + if (problem=="sp") { //shortest path problem
1.88 + is >> i;
1.89 + getline(is, str);
1.90 + s=nodes[i];
1.91 + }
1.92 + if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem
1.93 + is >> i >> d;
1.94 + getline(is, str);
1.95 + if (d=='s') s=nodes[i];
1.96 + if (d=='t') t=nodes[i];
1.97 + }
1.98 + break;
1.99 + case 'a':
1.100 + if ( problem == "mat" ) {
1.101 + is >> i >> j;
1.102 + getline(is, str);
1.103 + g.addEdge(nodes[i], nodes[j]);
1.104 + }
1.105 + if ( problem == "max" || problem == "sp") {
1.106 + is >> i >> j >> _cap;
1.107 + getline(is, str);
1.108 + e=g.addEdge(nodes[i], nodes[j]);
1.109 + capacity.update();
1.110 + capacity.set(e, _cap);
1.111 + }
1.112 + if ( problem == "min" ) {
1.113 + is >> i >> j >> _cap >> _cost;
1.114 + getline(is, str);
1.115 + e=g.addEdge(nodes[i], nodes[j]);
1.116 + capacity.update();
1.117 + capacity.set(e, _cap);
1.118 + cost.update();
1.119 + cost.set(e, _cost);
1.120 + }
1.121 + break;
1.122 + }
1.123 + }
1.124 + }
1.125 +
1.126 +
1.127
1.128 + /// write matching problem
1.129 + template<typename Graph>
1.130 + void writeDimacs(std::ostream& os, const Graph &g) {
1.131 + typedef typename Graph::NodeIt NodeIt;
1.132 + typedef typename Graph::EdgeIt EdgeIt;
1.133 +
1.134 + typename Graph::template NodeMap<int> nodes(g);
1.135 +
1.136 + os << "c matching problem" << std::endl;
1.137 +
1.138 + int i=1;
1.139 + NodeIt v;
1.140 + for(g.first(v); g.valid(v); g.next(v)) {
1.141 + nodes.set(v, i);
1.142 + ++i;
1.143 + }
1.144 +
1.145 + os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
1.146 +
1.147 + EdgeIt e;
1.148 + for(g.first(e); g.valid(e); g.next(e)) {
1.149 + os << "a " << nodes[g.tail(e)] << " " << nodes[g.head(e)] << std::endl;
1.150 + }
1.151 +
1.152 + }
1.153 +
1.154 +
1.155 +
1.156 } //namespace hugo
1.157
1.158 #endif //HUGO_DIMACS_H