Bug fixes.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #ifndef LEMON_DIMACS_H
20 #define LEMON_DIMACS_H
25 #include <lemon/maps.h>
26 #include <lemon/bits/invalid.h>
28 /// \ingroup dimacs_group
30 /// \brief DIMACS file format reader.
34 ///@defgroup dimacs_group DIMACS format
35 ///\brief Read and write files in DIMACS format
37 ///Tools to read a graph from or write it to a file in DIMACS format
41 /// \addtogroup dimacs_group
44 /// DIMACS min cost flow reader function.
46 /// This function reads a min cost flow instance from DIMACS format,
47 /// i.e. from DIMACS files having a line starting with
51 /// At the beginning \c g is cleared by \c g.clear(). The supply
52 /// amount of the nodes are written to \c supply (signed). The
53 /// lower bounds, capacities and costs of the edges are written to
54 /// \c lower, \c capacity and \c cost.
56 /// \author Marton Makai and Peter Kovacs
57 template <typename Graph, typename LowerMap,
58 typename CapacityMap, typename CostMap,
60 void readDimacs( std::istream& is,
63 CapacityMap& capacity,
68 std::vector<typename Graph::Node> nodes;
69 typename Graph::Edge e;
70 std::string problem, str;
74 typename SupplyMap::Value sup;
75 typename CapacityMap::Value low;
76 typename CapacityMap::Value cap;
77 typename CostMap::Value co;
80 case 'c': // comment line
83 case 'p': // problem definition line
84 is >> problem >> n >> m;
86 if (problem != "min") return;
88 for (int k = 1; k <= n; ++k) {
89 nodes[k] = g.addNode();
90 supply.set(nodes[k], 0);
93 case 'n': // node definition line
96 supply.set(nodes[i], sup);
98 case 'a': // edge (arc) definition line
99 is >> i >> j >> low >> cap >> co;
101 e = g.addEdge(nodes[i], nodes[j]);
104 capacity.set(e, cap);
113 /// DIMACS max flow reader function.
115 /// This function reads a max flow instance from DIMACS format,
116 /// i.e. from DIMACS files having a line starting with
120 /// At the beginning \c g is cleared by \c g.clear(). The edge
121 /// capacities are written to \c capacity and \c s and \c t are
122 /// set to the source and the target nodes.
124 /// \author Marton Makai
125 template<typename Graph, typename CapacityMap>
126 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
127 typename Graph::Node &s, typename Graph::Node &t) {
129 std::vector<typename Graph::Node> nodes;
130 typename Graph::Edge e;
135 typename CapacityMap::Value _cap;
139 case 'c': // comment line
142 case 'p': // problem definition line
143 is >> problem >> n >> m;
146 for (int k = 1; k <= n; ++k)
147 nodes[k] = g.addNode();
149 case 'n': // node definition line
150 if (problem == "sp") { // shortest path problem
155 if (problem == "max") { // max flow problem
158 if (d == 's') s = nodes[i];
159 if (d == 't') t = nodes[i];
162 case 'a': // edge (arc) definition line
163 if (problem == "max" || problem == "sp") {
164 is >> i >> j >> _cap;
166 e = g.addEdge(nodes[i], nodes[j]);
167 capacity.set(e, _cap);
171 g.addEdge(nodes[i], nodes[j]);
178 /// DIMACS shortest path reader function.
180 /// This function reads a shortest path instance from DIMACS format,
181 /// i.e. from DIMACS files having a line starting with
185 /// At the beginning \c g is cleared by \c g.clear(). The edge
186 /// capacities are written to \c capacity and \c s is set to the
189 /// \author Marton Makai
190 template<typename Graph, typename CapacityMap>
191 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
192 typename Graph::Node &s) {
193 readDimacs(is, g, capacity, s, s);
196 /// DIMACS capacitated graph reader function.
198 /// This function reads an edge capacitated graph instance from
199 /// DIMACS format. At the beginning \c g is cleared by \c g.clear()
200 /// and the edge capacities are written to \c capacity.
202 /// \author Marton Makai
203 template<typename Graph, typename CapacityMap>
204 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
205 typename Graph::Node u;
206 readDimacs(is, g, capacity, u, u);
209 /// DIMACS plain graph reader function.
211 /// This function reads a graph without any designated nodes and
212 /// maps from DIMACS format, i.e. from DIMACS files having a line
217 /// At the beginning \c g is cleared by \c g.clear().
219 /// \author Marton Makai
220 template<typename Graph>
221 void readDimacs(std::istream& is, Graph &g) {
222 typename Graph::Node u;
223 NullMap<typename Graph::Edge, int> n;
224 readDimacs(is, g, n, u, u);
227 /// DIMACS plain graph writer function.
229 /// This function writes a graph without any designated nodes and
230 /// maps into DIMACS format, i.e. into DIMACS file having a line
236 /// \author Marton Makai
237 template<typename Graph>
238 void writeDimacs(std::ostream& os, const Graph &g) {
239 typedef typename Graph::NodeIt NodeIt;
240 typedef typename Graph::EdgeIt EdgeIt;
242 os << "c matching problem" << std::endl;
243 os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
245 typename Graph::template NodeMap<int> nodes(g);
247 for(NodeIt v(g); v != INVALID; ++v) {
251 for(EdgeIt e(g); e != INVALID; ++e) {
252 os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)] << std::endl;
260 #endif //LEMON_DIMACS_H