COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/dimacs.h @ 1359:1581f961cfaa

Last change on this file since 1359:1581f961cfaa was 1359:1581f961cfaa, checked in by Alpar Juttner, 15 years ago

Correct the english name of EGRES.

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