1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/lemon/dimacs.h Wed Sep 29 15:30:04 2004 +0000
1.3 @@ -0,0 +1,207 @@
1.4 +/* -*- C++ -*-
1.5 + * src/lemon/dimacs.h - Part of LEMON, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
1.9 + *
1.10 + * Permission to use, modify and distribute this software is granted
1.11 + * provided that this copyright notice appears in all copies. For
1.12 + * precise terms see the accompanying LICENSE file.
1.13 + *
1.14 + * This software is provided "AS IS" with no warranty of any kind,
1.15 + * express or implied, and with no claim as to its suitability for any
1.16 + * purpose.
1.17 + *
1.18 + */
1.19 +
1.20 +#ifndef LEMON_DIMACS_H
1.21 +#define LEMON_DIMACS_H
1.22 +
1.23 +#include <iostream>
1.24 +#include <string>
1.25 +#include <vector>
1.26 +#include <lemon/maps.h>
1.27 +
1.28 +/// \ingroup misc
1.29 +/// \file
1.30 +/// \brief Dimacs file format reader.
1.31 +
1.32 +namespace lemon {
1.33 +
1.34 +
1.35 + /// \addtogroup misc
1.36 + /// @{
1.37 +
1.38 + /// Dimacs min cost flow reader function.
1.39 +
1.40 + /// This function reads a min cost flow instance from dimacs format,
1.41 + /// i.e. from dimacs files having a line starting with \c p \c "min".
1.42 + /// At the beginning \c g is cleared by \c g.clear(). The edge
1.43 + /// capacities are written to \c capacity, \c s and \c t are set to
1.44 + /// the source and the target nodes resp. and the cost of the edges
1.45 + /// are written to \c cost.
1.46 + ///
1.47 + /// \author Marton Makai
1.48 + template<typename Graph, typename CapacityMap, typename CostMap>
1.49 + void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
1.50 + typename Graph::Node &s, typename Graph::Node &t,
1.51 + CostMap& cost) {
1.52 + g.clear();
1.53 + typename CapacityMap::ValueType _cap;
1.54 + typename CostMap::ValueType _cost;
1.55 + char d;
1.56 + std::string problem;
1.57 + char c;
1.58 + int i, j;
1.59 + std::string str;
1.60 + int n, m;
1.61 + typename Graph::Edge e;
1.62 + std::vector<typename Graph::Node> nodes;
1.63 + while (is>>c) {
1.64 + switch (c) {
1.65 + case 'c': //comment
1.66 + getline(is, str);
1.67 + break;
1.68 + case 'p': //problem definition
1.69 + is >> problem >> n >> m;
1.70 + getline(is, str);
1.71 + nodes.resize(n+1);
1.72 + for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
1.73 + break;
1.74 + case 'n': //node definition
1.75 + if (problem=="sp") { //shortest path problem
1.76 + is >> i;
1.77 + getline(is, str);
1.78 + s=nodes[i];
1.79 + }
1.80 + if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem
1.81 + is >> i >> d;
1.82 + getline(is, str);
1.83 + if (d=='s') s=nodes[i];
1.84 + if (d=='t') t=nodes[i];
1.85 + }
1.86 + break;
1.87 + case 'a':
1.88 + if ( problem == "max" || problem == "sp") {
1.89 + is >> i >> j >> _cap;
1.90 + getline(is, str);
1.91 + e=g.addEdge(nodes[i], nodes[j]);
1.92 + //capacity.update();
1.93 + capacity.set(e, _cap);
1.94 + } else {
1.95 + if ( problem == "min" ) {
1.96 + is >> i >> j >> _cap >> _cost;
1.97 + getline(is, str);
1.98 + e=g.addEdge(nodes[i], nodes[j]);
1.99 + //capacity.update();
1.100 + capacity.set(e, _cap);
1.101 + //cost.update();
1.102 + cost.set(e, _cost);
1.103 + } else {
1.104 + is >> i >> j;
1.105 + getline(is, str);
1.106 + g.addEdge(nodes[i], nodes[j]);
1.107 + }
1.108 + }
1.109 + break;
1.110 + }
1.111 + }
1.112 + }
1.113 +
1.114 +
1.115 + /// Dimacs max flow reader function.
1.116 +
1.117 + /// This function reads a max flow instance from dimacs format,
1.118 + /// i.e. from dimacs files having a line starting with \c p \c
1.119 + /// "max". At the beginning \c g is cleared by \c g.clear(). The
1.120 + /// edge capacities are written to \c capacity and \c s and \c t are
1.121 + /// set to the source and the target nodes.
1.122 + ///
1.123 + /// \author Marton Makai
1.124 + template<typename Graph, typename CapacityMap>
1.125 + void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
1.126 + typename Graph::Node &s, typename Graph::Node &t) {
1.127 + NullMap<typename Graph::Edge, int> n;
1.128 + readDimacs(is, g, capacity, s, t, n);
1.129 + }
1.130 +
1.131 +
1.132 + /// Dimacs shortest path reader function.
1.133 +
1.134 + /// This function reads a shortest path instance from dimacs format,
1.135 + /// i.e. from dimacs files having a line starting with \c p \c "sp".
1.136 + /// At the beginning \c g is cleared by \c g.clear(). The edge
1.137 + /// capacities are written to \c capacity and \c s is set to the
1.138 + /// source node.
1.139 + ///
1.140 + /// \author Marton Makai
1.141 + template<typename Graph, typename CapacityMap>
1.142 + void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
1.143 + typename Graph::Node &s) {
1.144 + NullMap<typename Graph::Edge, int> n;
1.145 + readDimacs(is, g, capacity, s, s, n);
1.146 + }
1.147 +
1.148 +
1.149 + /// Dimacs capacitated graph reader function.
1.150 +
1.151 + /// This function reads an edge capacitated graph instance from
1.152 + /// dimacs format. At the beginning \c g is cleared by \c g.clear()
1.153 + /// and the edge capacities are written to \c capacity.
1.154 + ///
1.155 + /// \author Marton Makai
1.156 + template<typename Graph, typename CapacityMap>
1.157 + void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
1.158 + typename Graph::Node u;
1.159 + NullMap<typename Graph::Edge, int> n;
1.160 + readDimacs(is, g, capacity, u, u, n);
1.161 + }
1.162 +
1.163 +
1.164 + /// Dimacs plain graph reader function.
1.165 +
1.166 + /// This function reads a graph without any designated nodes and
1.167 + /// maps from dimacs format, i.e. from dimacs files having a line
1.168 + /// starting with \c p \c "mat". At the beginning \c g is cleared
1.169 + /// by \c g.clear().
1.170 + ///
1.171 + /// \author Marton Makai
1.172 + template<typename Graph>
1.173 + void readDimacs(std::istream& is, Graph &g) {
1.174 + typename Graph::Node u;
1.175 + NullMap<typename Graph::Edge, int> n;
1.176 + readDimacs(is, g, n, u, u, n);
1.177 + }
1.178 +
1.179 +
1.180 +
1.181 +
1.182 + /// write matching problem
1.183 + template<typename Graph>
1.184 + void writeDimacs(std::ostream& os, const Graph &g) {
1.185 + typedef typename Graph::NodeIt NodeIt;
1.186 + typedef typename Graph::EdgeIt EdgeIt;
1.187 +
1.188 + typename Graph::template NodeMap<int> nodes(g);
1.189 +
1.190 + os << "c matching problem" << std::endl;
1.191 +
1.192 + int i=1;
1.193 + for(NodeIt v(g); v!=INVALID; ++v) {
1.194 + nodes.set(v, i);
1.195 + ++i;
1.196 + }
1.197 +
1.198 + os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
1.199 +
1.200 + for(EdgeIt e(g); e!=INVALID; ++e) {
1.201 + os << "a " << nodes[g.tail(e)] << " " << nodes[g.head(e)] << std::endl;
1.202 + }
1.203 +
1.204 + }
1.205 +
1.206 + /// @}
1.207 +
1.208 +} //namespace lemon
1.209 +
1.210 +#endif //LEMON_DIMACS_H