COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/dimacs.h @ 1993:2115143eceea

Last change on this file since 1993:2115143eceea was 1993:2115143eceea, checked in by Balazs Dezso, 18 years ago

utility, invalid and traits moved to bits

File size: 6.0 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_DIMACS_H
20#define LEMON_DIMACS_H
21
22#include <iostream>
23#include <string>
24#include <vector>
25#include <lemon/maps.h>
26#include <lemon/bits/invalid.h>
27
28/// \ingroup dimacs_group
29/// \file
30/// \brief Dimacs file format reader.
31
32namespace lemon {
33
34  ///
35  ///@defgroup dimacs_group DIMACS format
36  ///\brief Read and write files in DIMACS format
37  ///
38  ///Tools to read a graph from or write it to a file in DIMACS format
39  ///data
40  ///\ingroup io_group
41
42  /// \addtogroup dimacs_group
43  /// @{
44
45  /// Dimacs min cost flow reader function.
46
47  /// This function reads a min cost flow instance from dimacs format,
48  /// i.e. from dimacs files having a line starting with
49  ///\code
50  /// p "min"
51  ///\endcode
52  /// At the beginning \c g is cleared by \c g.clear(). The edge
53  /// capacities are written to \c capacity, \c s and \c t are set to
54  /// the source and the target nodes resp. and the cost of the edges
55  /// are written to \c cost.
56  ///
57  /// \author Marton Makai
58  template<typename Graph, typename CapacityMap, typename CostMap>
59  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
60                  typename Graph::Node &s, typename Graph::Node &t,
61                  CostMap& cost) {
62    g.clear();
63    typename CapacityMap::Value _cap;
64    typename CostMap::Value _cost;
65    char d;
66    std::string problem;
67    char c;
68    int i, j;
69    std::string str;
70    int n, m;
71    typename Graph::Edge e;
72    std::vector<typename Graph::Node> nodes;
73    while (is>>c) {
74      switch (c) {
75      case 'c': //comment
76        getline(is, str);
77        break;
78      case 'p': //problem definition
79        is >> problem >> n >> m;
80        getline(is, str);
81        nodes.resize(n+1);
82        for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
83        break;
84      case 'n': //node definition
85        if (problem=="sp") { //shortest path problem
86          is >> i;
87          getline(is, str);
88          s=nodes[i];
89        }
90        if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem
91          is >> i >> d;
92          getline(is, str);
93          if (d=='s') s=nodes[i];
94          if (d=='t') t=nodes[i];
95        }
96        break;
97      case 'a':
98        if ( problem == "max" || problem == "sp") {
99          is >> i >> j >> _cap;
100          getline(is, str);
101          e=g.addEdge(nodes[i], nodes[j]);
102          //capacity.update();
103          capacity.set(e, _cap);
104        } else {
105          if ( problem == "min" ) {
106            is >> i >> j >> _cap >> _cost;
107            getline(is, str);
108            e=g.addEdge(nodes[i], nodes[j]);
109            //capacity.update();
110            capacity.set(e, _cap);
111            //cost.update();
112            cost.set(e, _cost);
113          } else {
114            is >> i >> j;
115            getline(is, str);
116            g.addEdge(nodes[i], nodes[j]);
117          }
118        }
119        break;
120      }
121    }
122  }
123
124
125  /// Dimacs max flow reader function.
126
127  /// This function reads a max flow instance from dimacs format,
128  /// i.e. from dimacs files having a line starting with
129  ///\code
130  /// p "max"
131  ///\endcode
132  ///At the beginning \c g is cleared by \c g.clear(). The
133  /// edge capacities are written to \c capacity and \c s and \c t are
134  /// set to the source and the target nodes.
135  ///
136  /// \author Marton Makai
137  template<typename Graph, typename CapacityMap>
138  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
139                  typename Graph::Node &s, typename Graph::Node &t) {
140    NullMap<typename Graph::Edge, int> n;
141    readDimacs(is, g, capacity, s, t, n);
142  }
143
144
145  /// Dimacs shortest path reader function.
146
147  /// This function reads a shortest path instance from dimacs format,
148  /// i.e. from dimacs files having a line starting with
149  ///\code
150  /// p "sp"
151  ///\endcode
152  /// At the beginning \c g is cleared by \c g.clear(). The edge
153  /// capacities are written to \c capacity and \c s is set to the
154  /// source node.
155  ///
156  /// \author Marton Makai
157  template<typename Graph, typename CapacityMap>
158  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
159                  typename Graph::Node &s) {
160    NullMap<typename Graph::Edge, int> n;
161    readDimacs(is, g, capacity, s, s, n);
162  }
163
164
165  /// Dimacs capacitated graph reader function.
166
167  /// This function reads an edge capacitated graph instance from
168  /// dimacs format.  At the beginning \c g is cleared by \c g.clear()
169  /// and the edge capacities are written to \c capacity.
170  ///
171  /// \author Marton Makai
172  template<typename Graph, typename CapacityMap>
173  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
174    typename Graph::Node u;
175    NullMap<typename Graph::Edge, int> n;
176    readDimacs(is, g, capacity, u, u, n);
177  }
178
179
180  /// Dimacs plain graph reader function.
181
182  /// This function reads a graph without any designated nodes and
183  /// maps from dimacs format, i.e. from dimacs files having a line
184  /// starting with
185  ///\code
186  /// p "mat"
187  ///\endcode
188  /// At the beginning \c g is cleared
189  /// by \c g.clear().
190  ///
191  /// \author Marton Makai
192  template<typename Graph>
193  void readDimacs(std::istream& is, Graph &g) {
194    typename Graph::Node u;
195    NullMap<typename Graph::Edge, int> n;
196    readDimacs(is, g, n, u, u, n);
197  }
198 
199
200
201 
202  /// write matching problem
203  template<typename Graph>
204  void writeDimacs(std::ostream& os, const Graph &g) {
205    typedef typename Graph::NodeIt NodeIt;
206    typedef typename Graph::EdgeIt EdgeIt; 
207   
208    typename Graph::template NodeMap<int> nodes(g);
209
210    os << "c matching problem" << std::endl;
211
212    int i=1;
213    for(NodeIt v(g); v!=INVALID; ++v) {
214      nodes.set(v, i);
215      ++i;
216    }   
217   
218    os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
219
220    for(EdgeIt e(g); e!=INVALID; ++e) {
221      os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)] << std::endl;
222    }
223
224  }
225
226  /// @}
227
228} //namespace lemon
229
230#endif //LEMON_DIMACS_H
Note: See TracBrowser for help on using the repository browser.