1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/hugo/dimacs.h Thu May 06 13:21:24 2004 +0000
1.3 @@ -0,0 +1,206 @@
1.4 +// -*- c++ -*-
1.5 +#ifndef HUGO_DIMACS_H
1.6 +#define HUGO_DIMACS_H
1.7 +
1.8 +#include <iostream>
1.9 +#include <string>
1.10 +#include <vector>
1.11 +#include <maps.h>
1.12 +
1.13 +/// \file
1.14 +/// \brief Dimacs file format reader.
1.15 +
1.16 +namespace hugo {
1.17 +
1.18 + /// Dimacs flow file format reader function.
1.19 +
1.20 + /// This function reads a flow instance from dimacs flow format.
1.21 + /// At the beginning \c g is cleared by \c g.clear().
1.22 + /// If the data coming from \c is is a max flow problem instance, then
1.23 + /// \c s and \c t will be respectively the source and target nodes
1.24 + /// and \c capacity will contain the edge capacities.
1.25 + /// If the data is a shortest path problem instance then \c s will be the
1.26 + /// source node and \c capacity will contain the edge lengths.
1.27 + ///
1.28 + ///\author Marton Makai
1.29 + template<typename Graph, typename CapacityMap>
1.30 + void readDimacsMaxFlow(std::istream& is, Graph &g,
1.31 + typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) {
1.32 + g.clear();
1.33 + int cap;
1.34 + char d;
1.35 + std::string problem;
1.36 + char c;
1.37 + int i, j;
1.38 + std::string str;
1.39 + int n, m;
1.40 + typename Graph::Edge e;
1.41 + std::vector<typename Graph::Node> nodes;
1.42 + while (is>>c) {
1.43 + switch (c) {
1.44 + case 'c': //comment
1.45 + getline(is, str);
1.46 + break;
1.47 + case 'p': //problem definition
1.48 + is >> problem >> n >> m;
1.49 + getline(is, str);
1.50 + nodes.resize(n+1);
1.51 + for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
1.52 + break;
1.53 + case 'n': //node definition
1.54 + if (problem=="sp") { //shortest path problem
1.55 + is >> i;
1.56 + getline(is, str);
1.57 + s=nodes[i];
1.58 + }
1.59 + if (problem=="max") { //max flow problem
1.60 + is >> i >> d;
1.61 + getline(is, str);
1.62 + if (d=='s') s=nodes[i];
1.63 + if (d=='t') t=nodes[i];
1.64 + }
1.65 + break;
1.66 + case 'a':
1.67 + is >> i >> j >> cap;
1.68 + getline(is, str);
1.69 + e=g.addEdge(nodes[i], nodes[j]);
1.70 + capacity.update();
1.71 + capacity.set(e, cap);
1.72 + break;
1.73 + }
1.74 + }
1.75 + }
1.76 +
1.77 + /// matching problem
1.78 + template<typename Graph>
1.79 + void readDimacs(std::istream& is, Graph &g) {
1.80 + typename Graph::Node u;
1.81 + NullMap<typename Graph::Edge, int> n;
1.82 + readDimacs(is, g, n, u, u, n);
1.83 + std::cout<<"igen en.";
1.84 + }
1.85 +
1.86 + /// sg problem
1.87 + template<typename Graph, typename CapacityMap>
1.88 + void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
1.89 + typename Graph::Node u;
1.90 + NullMap<typename Graph::Edge, int> n;
1.91 + readDimacs(is, g, capacity, u, u, n);
1.92 + }
1.93 +
1.94 + /// shortest path problem
1.95 + template<typename Graph, typename CapacityMap>
1.96 + void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
1.97 + typename Graph::Node &s) {
1.98 + NullMap<typename Graph::Edge, int> n;
1.99 + readDimacs(is, g, capacity, s, s, n);
1.100 + }
1.101 +
1.102 + /// max flow problem
1.103 + template<typename Graph, typename CapacityMap>
1.104 + void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
1.105 + typename Graph::Node &s, typename Graph::Node &t) {
1.106 + NullMap<typename Graph::Edge, int> n;
1.107 + readDimacs(is, g, capacity, s, t, n);
1.108 + }
1.109 +
1.110 + /// min cost flow problem
1.111 + template<typename Graph, typename CapacityMap, typename CostMap>
1.112 + void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
1.113 + typename Graph::Node &s, typename Graph::Node &t,
1.114 + CostMap& cost) {
1.115 + g.clear();
1.116 + typename CapacityMap::ValueType _cap;
1.117 + typename CostMap::ValueType _cost;
1.118 + char d;
1.119 + std::string problem;
1.120 + char c;
1.121 + int i, j;
1.122 + std::string str;
1.123 + int n, m;
1.124 + typename Graph::Edge e;
1.125 + std::vector<typename Graph::Node> nodes;
1.126 + while (is>>c) {
1.127 + switch (c) {
1.128 + case 'c': //comment
1.129 + getline(is, str);
1.130 + break;
1.131 + case 'p': //problem definition
1.132 + is >> problem >> n >> m;
1.133 + getline(is, str);
1.134 + nodes.resize(n+1);
1.135 + for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
1.136 + break;
1.137 + case 'n': //node definition
1.138 + if (problem=="sp") { //shortest path problem
1.139 + is >> i;
1.140 + getline(is, str);
1.141 + s=nodes[i];
1.142 + }
1.143 + if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem
1.144 + is >> i >> d;
1.145 + getline(is, str);
1.146 + if (d=='s') s=nodes[i];
1.147 + if (d=='t') t=nodes[i];
1.148 + }
1.149 + break;
1.150 + case 'a':
1.151 + if ( problem == "mat" ) {
1.152 + is >> i >> j;
1.153 + getline(is, str);
1.154 + g.addEdge(nodes[i], nodes[j]);
1.155 + }
1.156 + if ( problem == "max" || problem == "sp") {
1.157 + is >> i >> j >> _cap;
1.158 + getline(is, str);
1.159 + e=g.addEdge(nodes[i], nodes[j]);
1.160 + capacity.update();
1.161 + capacity.set(e, _cap);
1.162 + }
1.163 + if ( problem == "min" ) {
1.164 + is >> i >> j >> _cap >> _cost;
1.165 + getline(is, str);
1.166 + e=g.addEdge(nodes[i], nodes[j]);
1.167 + capacity.update();
1.168 + capacity.set(e, _cap);
1.169 + cost.update();
1.170 + cost.set(e, _cost);
1.171 + }
1.172 + break;
1.173 + }
1.174 + }
1.175 + }
1.176 +
1.177 +
1.178 +
1.179 + /// write matching problem
1.180 + template<typename Graph>
1.181 + void writeDimacs(std::ostream& os, const Graph &g) {
1.182 + typedef typename Graph::NodeIt NodeIt;
1.183 + typedef typename Graph::EdgeIt EdgeIt;
1.184 +
1.185 + typename Graph::template NodeMap<int> nodes(g);
1.186 +
1.187 + os << "c matching problem" << std::endl;
1.188 +
1.189 + int i=1;
1.190 + NodeIt v;
1.191 + for(g.first(v); g.valid(v); g.next(v)) {
1.192 + nodes.set(v, i);
1.193 + ++i;
1.194 + }
1.195 +
1.196 + os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
1.197 +
1.198 + EdgeIt e;
1.199 + for(g.first(e); g.valid(e); g.next(e)) {
1.200 + os << "a " << nodes[g.tail(e)] << " " << nodes[g.head(e)] << std::endl;
1.201 + }
1.202 +
1.203 + }
1.204 +
1.205 +
1.206 +
1.207 +} //namespace hugo
1.208 +
1.209 +#endif //HUGO_DIMACS_H