1.1 --- a/src/include/dimacs.h Thu May 06 09:26:23 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,206 +0,0 @@
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