1.1 --- a/src/lemon/dimacs.h Sat May 21 21:04:57 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,228 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - * src/lemon/dimacs.h - Part of LEMON, a generic C++ optimization library
1.6 - *
1.7 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 - * (Egervary Research Group on Combinatorial Optimization, 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 -#include <lemon/invalid.h>
1.28 -
1.29 -/// \ingroup dimacs_group
1.30 -/// \file
1.31 -/// \brief Dimacs file format reader.
1.32 -
1.33 -namespace lemon {
1.34 -
1.35 - ///
1.36 - ///@defgroup dimacs_group DIMACS format
1.37 - ///\brief Read and write files in DIMACS format
1.38 - ///
1.39 - ///Tools to read a graph from or write it to a file in DIMACS format
1.40 - ///data
1.41 - ///\ingroup io_group
1.42 -
1.43 - /// \addtogroup dimacs_group
1.44 - /// @{
1.45 -
1.46 - /// Dimacs min cost flow reader function.
1.47 -
1.48 - /// This function reads a min cost flow instance from dimacs format,
1.49 - /// i.e. from dimacs files having a line starting with
1.50 - /// \code
1.51 - /// p "min"
1.52 - /// \endcode
1.53 - /// At the beginning \c g is cleared by \c g.clear(). The edge
1.54 - /// capacities are written to \c capacity, \c s and \c t are set to
1.55 - /// the source and the target nodes resp. and the cost of the edges
1.56 - /// are written to \c cost.
1.57 - ///
1.58 - /// \author Marton Makai
1.59 - template<typename Graph, typename CapacityMap, typename CostMap>
1.60 - void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
1.61 - typename Graph::Node &s, typename Graph::Node &t,
1.62 - CostMap& cost) {
1.63 - g.clear();
1.64 - typename CapacityMap::Value _cap;
1.65 - typename CostMap::Value _cost;
1.66 - char d;
1.67 - std::string problem;
1.68 - char c;
1.69 - int i, j;
1.70 - std::string str;
1.71 - int n, m;
1.72 - typename Graph::Edge e;
1.73 - std::vector<typename Graph::Node> nodes;
1.74 - while (is>>c) {
1.75 - switch (c) {
1.76 - case 'c': //comment
1.77 - getline(is, str);
1.78 - break;
1.79 - case 'p': //problem definition
1.80 - is >> problem >> n >> m;
1.81 - getline(is, str);
1.82 - nodes.resize(n+1);
1.83 - for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
1.84 - break;
1.85 - case 'n': //node definition
1.86 - if (problem=="sp") { //shortest path problem
1.87 - is >> i;
1.88 - getline(is, str);
1.89 - s=nodes[i];
1.90 - }
1.91 - if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem
1.92 - is >> i >> d;
1.93 - getline(is, str);
1.94 - if (d=='s') s=nodes[i];
1.95 - if (d=='t') t=nodes[i];
1.96 - }
1.97 - break;
1.98 - case 'a':
1.99 - if ( problem == "max" || problem == "sp") {
1.100 - is >> i >> j >> _cap;
1.101 - getline(is, str);
1.102 - e=g.addEdge(nodes[i], nodes[j]);
1.103 - //capacity.update();
1.104 - capacity.set(e, _cap);
1.105 - } else {
1.106 - if ( problem == "min" ) {
1.107 - is >> i >> j >> _cap >> _cost;
1.108 - getline(is, str);
1.109 - e=g.addEdge(nodes[i], nodes[j]);
1.110 - //capacity.update();
1.111 - capacity.set(e, _cap);
1.112 - //cost.update();
1.113 - cost.set(e, _cost);
1.114 - } else {
1.115 - is >> i >> j;
1.116 - getline(is, str);
1.117 - g.addEdge(nodes[i], nodes[j]);
1.118 - }
1.119 - }
1.120 - break;
1.121 - }
1.122 - }
1.123 - }
1.124 -
1.125 -
1.126 - /// Dimacs max flow reader function.
1.127 -
1.128 - /// This function reads a max flow instance from dimacs format,
1.129 - /// i.e. from dimacs files having a line starting with
1.130 - /// \code
1.131 - /// p "max"
1.132 - /// \endcode
1.133 - ///At the beginning \c g is cleared by \c g.clear(). The
1.134 - /// edge capacities are written to \c capacity and \c s and \c t are
1.135 - /// set to the source and the target nodes.
1.136 - ///
1.137 - /// \author Marton Makai
1.138 - template<typename Graph, typename CapacityMap>
1.139 - void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
1.140 - typename Graph::Node &s, typename Graph::Node &t) {
1.141 - NullMap<typename Graph::Edge, int> n;
1.142 - readDimacs(is, g, capacity, s, t, n);
1.143 - }
1.144 -
1.145 -
1.146 - /// Dimacs shortest path reader function.
1.147 -
1.148 - /// This function reads a shortest path instance from dimacs format,
1.149 - /// i.e. from dimacs files having a line starting with
1.150 - /// \code
1.151 - /// p "sp"
1.152 - /// \endcode
1.153 - /// At the beginning \c g is cleared by \c g.clear(). The edge
1.154 - /// capacities are written to \c capacity and \c s is set to the
1.155 - /// source node.
1.156 - ///
1.157 - /// \author Marton Makai
1.158 - template<typename Graph, typename CapacityMap>
1.159 - void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
1.160 - typename Graph::Node &s) {
1.161 - NullMap<typename Graph::Edge, int> n;
1.162 - readDimacs(is, g, capacity, s, s, n);
1.163 - }
1.164 -
1.165 -
1.166 - /// Dimacs capacitated graph reader function.
1.167 -
1.168 - /// This function reads an edge capacitated graph instance from
1.169 - /// dimacs format. At the beginning \c g is cleared by \c g.clear()
1.170 - /// and the edge capacities are written to \c capacity.
1.171 - ///
1.172 - /// \author Marton Makai
1.173 - template<typename Graph, typename CapacityMap>
1.174 - void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
1.175 - typename Graph::Node u;
1.176 - NullMap<typename Graph::Edge, int> n;
1.177 - readDimacs(is, g, capacity, u, u, n);
1.178 - }
1.179 -
1.180 -
1.181 - /// Dimacs plain graph reader function.
1.182 -
1.183 - /// This function reads a graph without any designated nodes and
1.184 - /// maps from dimacs format, i.e. from dimacs files having a line
1.185 - /// starting with
1.186 - /// \code
1.187 - /// p "mat"
1.188 - /// \endcode
1.189 - /// At the beginning \c g is cleared
1.190 - /// by \c g.clear().
1.191 - ///
1.192 - /// \author Marton Makai
1.193 - template<typename Graph>
1.194 - void readDimacs(std::istream& is, Graph &g) {
1.195 - typename Graph::Node u;
1.196 - NullMap<typename Graph::Edge, int> n;
1.197 - readDimacs(is, g, n, u, u, n);
1.198 - }
1.199 -
1.200 -
1.201 -
1.202 -
1.203 - /// write matching problem
1.204 - template<typename Graph>
1.205 - void writeDimacs(std::ostream& os, const Graph &g) {
1.206 - typedef typename Graph::NodeIt NodeIt;
1.207 - typedef typename Graph::EdgeIt EdgeIt;
1.208 -
1.209 - typename Graph::template NodeMap<int> nodes(g);
1.210 -
1.211 - os << "c matching problem" << std::endl;
1.212 -
1.213 - int i=1;
1.214 - for(NodeIt v(g); v!=INVALID; ++v) {
1.215 - nodes.set(v, i);
1.216 - ++i;
1.217 - }
1.218 -
1.219 - os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
1.220 -
1.221 - for(EdgeIt e(g); e!=INVALID; ++e) {
1.222 - os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)] << std::endl;
1.223 - }
1.224 -
1.225 - }
1.226 -
1.227 - /// @}
1.228 -
1.229 -} //namespace lemon
1.230 -
1.231 -#endif //LEMON_DIMACS_H