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