COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/dimacs.h @ 981:2e34b796d532

Last change on this file since 981:2e34b796d532 was 964:2c0c20e90116, checked in by Alpar Juttner, 19 years ago

Doc improvements

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