COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/dimacs.h @ 1220:20b26ee5812b

Last change on this file since 1220:20b26ee5812b was 1190:477a0fe37552, checked in by Balazs Dezso, 19 years ago

Bug fix

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