38 ///\ingroup io_group |
39 ///\ingroup io_group |
39 |
40 |
40 /// \addtogroup dimacs_group |
41 /// \addtogroup dimacs_group |
41 /// @{ |
42 /// @{ |
42 |
43 |
|
44 |
|
45 /// DIMACS file type descriptor. |
|
46 struct DimacsDescriptor |
|
47 { |
|
48 ///File type enum |
|
49 enum Type |
|
50 { |
|
51 NONE, MIN, MAX, SP, MAT |
|
52 }; |
|
53 ///The file type |
|
54 Type type; |
|
55 ///The number of nodes on the graph |
|
56 int nodeNum; |
|
57 ///The number of edges on the graph |
|
58 int edgeNum; |
|
59 int lineShift; |
|
60 /// Constructor. Sets the type to NONE. |
|
61 DimacsDescriptor() : type(NONE) {} |
|
62 }; |
|
63 |
|
64 ///Discover the type of a DIMACS file |
|
65 |
|
66 ///It starts seeking the begining of the file for the problem type |
|
67 ///and size info. The found date is returned in a special struct |
|
68 ///that can be evaluated and passed to the appropriate reader |
|
69 ///function. |
|
70 DimacsDescriptor dimacsType(std::istream& is) |
|
71 { |
|
72 DimacsDescriptor r; |
|
73 std::string problem,str; |
|
74 char c; |
|
75 r.lineShift=0; |
|
76 while (is >> c) |
|
77 switch(c) |
|
78 { |
|
79 case 'p': |
|
80 if(is >> problem >> r.nodeNum >> r.edgeNum) |
|
81 { |
|
82 getline(is, str); |
|
83 r.lineShift++; |
|
84 if(problem=="min") r.type=DimacsDescriptor::MIN; |
|
85 else if(problem=="max") r.type=DimacsDescriptor::MAX; |
|
86 else if(problem=="sp") r.type=DimacsDescriptor::SP; |
|
87 else if(problem=="mat") r.type=DimacsDescriptor::MAT; |
|
88 else throw FormatError("Unknown problem type"); |
|
89 return r; |
|
90 } |
|
91 else |
|
92 { |
|
93 throw FormatError("Missing or wrong problem type declaration."); |
|
94 } |
|
95 break; |
|
96 case 'c': |
|
97 getline(is, str); |
|
98 r.lineShift++; |
|
99 break; |
|
100 default: |
|
101 throw FormatError("Unknown DIMACS declaration."); |
|
102 } |
|
103 throw FormatError("Missing problem type declaration."); |
|
104 } |
|
105 |
|
106 |
|
107 |
43 /// DIMACS min cost flow reader function. |
108 /// DIMACS min cost flow reader function. |
44 /// |
109 /// |
45 /// This function reads a min cost flow instance from DIMACS format, |
110 /// This function reads a min cost flow instance from DIMACS format, |
46 /// i.e. from DIMACS files having a line starting with |
111 /// i.e. from DIMACS files having a line starting with |
47 /// \code |
112 /// \code |
48 /// p min |
113 /// p min |
49 /// \endcode |
114 /// \endcode |
50 /// At the beginning \c g is cleared by \c g.clear(). The supply |
115 /// At the beginning, \c g is cleared by \c g.clear(). The supply |
51 /// amount of the nodes are written to \c supply (signed). The |
116 /// amount of the nodes are written to \c supply (signed). The |
52 /// lower bounds, capacities and costs of the arcs are written to |
117 /// lower bounds, capacities and costs of the arcs are written to |
53 /// \c lower, \c capacity and \c cost. |
118 /// \c lower, \c capacity and \c cost. |
|
119 /// |
|
120 /// If the file type was previously evaluated by dimacsType(), then |
|
121 /// the descriptor struct should be given by the \c dest parameter. |
54 template <typename Digraph, typename LowerMap, |
122 template <typename Digraph, typename LowerMap, |
55 typename CapacityMap, typename CostMap, |
123 typename CapacityMap, typename CostMap, |
56 typename SupplyMap> |
124 typename SupplyMap> |
57 void readDimacsMin( std::istream& is, |
125 void readDimacsMin(std::istream& is, |
58 Digraph &g, |
126 Digraph &g, |
59 LowerMap& lower, |
127 LowerMap& lower, |
60 CapacityMap& capacity, |
128 CapacityMap& capacity, |
61 CostMap& cost, |
129 CostMap& cost, |
62 SupplyMap& supply ) |
130 SupplyMap& supply, |
|
131 DimacsDescriptor desc=DimacsDescriptor()) |
63 { |
132 { |
64 g.clear(); |
133 g.clear(); |
65 std::vector<typename Digraph::Node> nodes; |
134 std::vector<typename Digraph::Node> nodes; |
66 typename Digraph::Arc e; |
135 typename Digraph::Arc e; |
67 std::string problem, str; |
136 std::string problem, str; |
68 char c; |
137 char c; |
69 int n, m; |
|
70 int i, j; |
138 int i, j; |
|
139 if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); |
|
140 if(desc.type!=DimacsDescriptor::MIN) |
|
141 throw FormatError("Problem type mismatch"); |
|
142 |
|
143 nodes.resize(desc.nodeNum + 1); |
|
144 for (int k = 1; k <= desc.nodeNum; ++k) { |
|
145 nodes[k] = g.addNode(); |
|
146 supply.set(nodes[k], 0); |
|
147 } |
|
148 |
71 typename SupplyMap::Value sup; |
149 typename SupplyMap::Value sup; |
72 typename CapacityMap::Value low; |
150 typename CapacityMap::Value low; |
73 typename CapacityMap::Value cap; |
151 typename CapacityMap::Value cap; |
74 typename CostMap::Value co; |
152 typename CostMap::Value co; |
75 while (is >> c) { |
153 while (is >> c) { |
76 switch (c) { |
154 switch (c) { |
77 case 'c': // comment line |
155 case 'c': // comment line |
78 getline(is, str); |
156 getline(is, str); |
79 break; |
|
80 case 'p': // problem definition line |
|
81 is >> problem >> n >> m; |
|
82 getline(is, str); |
|
83 if (problem != "min") return; |
|
84 nodes.resize(n + 1); |
|
85 for (int k = 1; k <= n; ++k) { |
|
86 nodes[k] = g.addNode(); |
|
87 supply.set(nodes[k], 0); |
|
88 } |
|
89 break; |
157 break; |
90 case 'n': // node definition line |
158 case 'n': // node definition line |
91 is >> i >> sup; |
159 is >> i >> sup; |
92 getline(is, str); |
160 getline(is, str); |
93 supply.set(nodes[i], sup); |
161 supply.set(nodes[i], sup); |
105 break; |
173 break; |
106 } |
174 } |
107 } |
175 } |
108 } |
176 } |
109 |
177 |
110 /// DIMACS max flow reader function. |
|
111 /// |
|
112 /// This function reads a max flow instance from DIMACS format, |
|
113 /// i.e. from DIMACS files having a line starting with |
|
114 /// \code |
|
115 /// p max |
|
116 /// \endcode |
|
117 /// At the beginning \c g is cleared by \c g.clear(). The arc |
|
118 /// capacities are written to \c capacity and \c s and \c t are |
|
119 /// set to the source and the target nodes. |
|
120 template<typename Digraph, typename CapacityMap> |
178 template<typename Digraph, typename CapacityMap> |
121 void readDimacsMax(std::istream& is, Digraph &g, CapacityMap& capacity, |
179 void _readDimacs(std::istream& is, |
122 typename Digraph::Node &s, typename Digraph::Node &t) { |
180 Digraph &g, |
|
181 CapacityMap& capacity, |
|
182 typename Digraph::Node &s, |
|
183 typename Digraph::Node &t, |
|
184 DimacsDescriptor desc=DimacsDescriptor()) { |
123 g.clear(); |
185 g.clear(); |
|
186 s=t=INVALID; |
124 std::vector<typename Digraph::Node> nodes; |
187 std::vector<typename Digraph::Node> nodes; |
125 typename Digraph::Arc e; |
188 typename Digraph::Arc e; |
126 std::string problem; |
|
127 char c, d; |
189 char c, d; |
128 int n, m; |
|
129 int i, j; |
190 int i, j; |
130 typename CapacityMap::Value _cap; |
191 typename CapacityMap::Value _cap; |
131 std::string str; |
192 std::string str; |
|
193 nodes.resize(desc.nodeNum + 1); |
|
194 for (int k = 1; k <= desc.nodeNum; ++k) { |
|
195 nodes[k] = g.addNode(); |
|
196 } |
|
197 |
132 while (is >> c) { |
198 while (is >> c) { |
133 switch (c) { |
199 switch (c) { |
134 case 'c': // comment line |
200 case 'c': // comment line |
135 getline(is, str); |
201 getline(is, str); |
136 break; |
202 break; |
137 case 'p': // problem definition line |
|
138 is >> problem >> n >> m; |
|
139 getline(is, str); |
|
140 nodes.resize(n + 1); |
|
141 for (int k = 1; k <= n; ++k) |
|
142 nodes[k] = g.addNode(); |
|
143 break; |
|
144 case 'n': // node definition line |
203 case 'n': // node definition line |
145 if (problem == "sp") { // shortest path problem |
204 if (desc.type==DimacsDescriptor::SP) { // shortest path problem |
146 is >> i; |
205 is >> i; |
147 getline(is, str); |
206 getline(is, str); |
148 s = nodes[i]; |
207 s = nodes[i]; |
149 } |
208 } |
150 if (problem == "max") { // max flow problem |
209 if (desc.type==DimacsDescriptor::MAX) { // max flow problem |
151 is >> i >> d; |
210 is >> i >> d; |
152 getline(is, str); |
211 getline(is, str); |
153 if (d == 's') s = nodes[i]; |
212 if (d == 's') s = nodes[i]; |
154 if (d == 't') t = nodes[i]; |
213 if (d == 't') t = nodes[i]; |
155 } |
214 } |
156 break; |
215 break; |
157 case 'a': // arc (arc) definition line |
216 case 'a': // arc (arc) definition line |
158 if (problem == "max" || problem == "sp") { |
217 if (desc.type==DimacsDescriptor::SP || |
|
218 desc.type==DimacsDescriptor::MAX) { |
159 is >> i >> j >> _cap; |
219 is >> i >> j >> _cap; |
160 getline(is, str); |
220 getline(is, str); |
161 e = g.addArc(nodes[i], nodes[j]); |
221 e = g.addArc(nodes[i], nodes[j]); |
162 capacity.set(e, _cap); |
222 capacity.set(e, _cap); |
163 } else { |
223 } else { |
168 break; |
228 break; |
169 } |
229 } |
170 } |
230 } |
171 } |
231 } |
172 |
232 |
|
233 /// DIMACS max flow reader function. |
|
234 /// |
|
235 /// This function reads a max flow instance from DIMACS format, |
|
236 /// i.e. from DIMACS files having a line starting with |
|
237 /// \code |
|
238 /// p max |
|
239 /// \endcode |
|
240 /// At the beginning, \c g is cleared by \c g.clear(). The arc |
|
241 /// capacities are written to \c capacity and \c s and \c t are |
|
242 /// set to the source and the target nodes. |
|
243 /// |
|
244 /// If the file type was previously evaluated by dimacsType(), then |
|
245 /// the descriptor struct should be given by the \c dest parameter. |
|
246 template<typename Digraph, typename CapacityMap> |
|
247 void readDimacsMax(std::istream& is, |
|
248 Digraph &g, |
|
249 CapacityMap& capacity, |
|
250 typename Digraph::Node &s, |
|
251 typename Digraph::Node &t, |
|
252 DimacsDescriptor desc=DimacsDescriptor()) { |
|
253 if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); |
|
254 if(desc.type!=DimacsDescriptor::MAX) |
|
255 throw FormatError("Problem type mismatch"); |
|
256 _readDimacs(is,g,capacity,s,t,desc); |
|
257 } |
|
258 |
173 /// DIMACS shortest path reader function. |
259 /// DIMACS shortest path reader function. |
174 /// |
260 /// |
175 /// This function reads a shortest path instance from DIMACS format, |
261 /// This function reads a shortest path instance from DIMACS format, |
176 /// i.e. from DIMACS files having a line starting with |
262 /// i.e. from DIMACS files having a line starting with |
177 /// \code |
263 /// \code |
178 /// p sp |
264 /// p sp |
179 /// \endcode |
265 /// \endcode |
180 /// At the beginning \c g is cleared by \c g.clear(). The arc |
266 /// At the beginning, \c g is cleared by \c g.clear(). The arc |
181 /// capacities are written to \c capacity and \c s is set to the |
267 /// lengths are written to \c lenght and \c s is set to the |
182 /// source node. |
268 /// source node. |
|
269 /// |
|
270 /// If the file type was previously evaluated by dimacsType(), then |
|
271 /// the descriptor struct should be given by the \c dest parameter. |
|
272 template<typename Digraph, typename LengthMap> |
|
273 void readDimacsSp(std::istream& is, |
|
274 Digraph &g, |
|
275 LengthMap& length, |
|
276 typename Digraph::Node &s, |
|
277 DimacsDescriptor desc=DimacsDescriptor()) { |
|
278 typename Digraph::Node t; |
|
279 if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); |
|
280 if(desc.type!=DimacsDescriptor::SP) |
|
281 throw FormatError("Problem type mismatch"); |
|
282 _readDimacs(is, g, length, s, t,desc); |
|
283 } |
|
284 |
|
285 /// DIMACS capacitated digraph reader function. |
|
286 /// |
|
287 /// This function reads an arc capacitated digraph instance from |
|
288 /// DIMACS 'mat' or 'sp' format. |
|
289 /// At the beginning, \c g is cleared by \c g.clear() |
|
290 /// and the arc capacities/lengths are written to \c capacity. |
|
291 /// |
|
292 /// If the file type was previously evaluated by dimacsType(), then |
|
293 /// the descriptor struct should be given by the \c dest parameter. |
183 template<typename Digraph, typename CapacityMap> |
294 template<typename Digraph, typename CapacityMap> |
184 void readDimacsSp(std::istream& is, Digraph &g, CapacityMap& capacity, |
295 void readDimacsCap(std::istream& is, |
185 typename Digraph::Node &s) { |
296 Digraph &g, |
186 typename Digraph::Node t; |
297 CapacityMap& capacity, |
187 readDimacsMax(is, g, capacity, s, t); |
298 DimacsDescriptor desc=DimacsDescriptor()) { |
188 } |
|
189 |
|
190 /// DIMACS capacitated digraph reader function. |
|
191 /// |
|
192 /// This function reads an arc capacitated digraph instance from |
|
193 /// DIMACS format. At the beginning \c g is cleared by \c g.clear() |
|
194 /// and the arc capacities are written to \c capacity. |
|
195 template<typename Digraph, typename CapacityMap> |
|
196 void readDimacsMax(std::istream& is, Digraph &g, CapacityMap& capacity) { |
|
197 typename Digraph::Node u,v; |
299 typename Digraph::Node u,v; |
198 readDimacsMax(is, g, capacity, u, v); |
300 if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); |
|
301 if(desc.type!=DimacsDescriptor::MAX || desc.type!=DimacsDescriptor::SP) |
|
302 throw FormatError("Problem type mismatch"); |
|
303 _readDimacs(is, g, capacity, u, v, desc); |
199 } |
304 } |
200 |
305 |
201 /// DIMACS plain digraph reader function. |
306 /// DIMACS plain digraph reader function. |
202 /// |
307 /// |
203 /// This function reads a digraph without any designated nodes and |
308 /// This function reads a digraph without any designated nodes and |
204 /// maps from DIMACS format, i.e. from DIMACS files having a line |
309 /// maps from DIMACS format, i.e. from DIMACS files having a line |
205 /// starting with |
310 /// starting with |
206 /// \code |
311 /// \code |
207 /// p mat |
312 /// p mat |
208 /// \endcode |
313 /// \endcode |
209 /// At the beginning \c g is cleared by \c g.clear(). |
314 /// At the beginning, \c g is cleared by \c g.clear(). |
|
315 /// |
|
316 /// If the file type was previously evaluated by dimacsType(), then |
|
317 /// the descriptor struct should be given by the \c dest parameter. |
210 template<typename Digraph> |
318 template<typename Digraph> |
211 void readDimacsMat(std::istream& is, Digraph &g) { |
319 void readDimacsMat(std::istream& is, Digraph &g, |
|
320 DimacsDescriptor desc=DimacsDescriptor()) { |
212 typename Digraph::Node u,v; |
321 typename Digraph::Node u,v; |
213 NullMap<typename Digraph::Arc, int> n; |
322 NullMap<typename Digraph::Arc, int> n; |
214 readDimacsMax(is, g, n, u, v); |
323 if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); |
|
324 if(desc.type!=DimacsDescriptor::MAT) |
|
325 throw FormatError("Problem type mismatch"); |
|
326 _readDimacs(is, g, n, u, v, desc); |
215 } |
327 } |
216 |
328 |
217 /// DIMACS plain digraph writer function. |
329 /// DIMACS plain digraph writer function. |
218 /// |
330 /// |
219 /// This function writes a digraph without any designated nodes and |
331 /// This function writes a digraph without any designated nodes and |
220 /// maps into DIMACS format, i.e. into DIMACS file having a line |
332 /// maps into DIMACS format, i.e. into DIMACS file having a line |
221 /// starting with |
333 /// starting with |
222 /// \code |
334 /// \code |
223 /// p mat |
335 /// p mat |
224 /// \endcode |
336 /// \endcode |
|
337 /// If \c comment is not empty, then it will be printed in the first line |
|
338 /// prefixed by 'c'. |
225 template<typename Digraph> |
339 template<typename Digraph> |
226 void writeDimacsMat(std::ostream& os, const Digraph &g) { |
340 void writeDimacsMat(std::ostream& os, const Digraph &g, |
|
341 std::string comment="") { |
227 typedef typename Digraph::NodeIt NodeIt; |
342 typedef typename Digraph::NodeIt NodeIt; |
228 typedef typename Digraph::ArcIt ArcIt; |
343 typedef typename Digraph::ArcIt ArcIt; |
229 |
344 |
230 os << "c matching problem" << std::endl; |
345 if(!comment.empty()) |
|
346 os << "c " << comment << std::endl; |
231 os << "p mat " << g.nodeNum() << " " << g.arcNum() << std::endl; |
347 os << "p mat " << g.nodeNum() << " " << g.arcNum() << std::endl; |
232 |
348 |
233 typename Digraph::template NodeMap<int> nodes(g); |
349 typename Digraph::template NodeMap<int> nodes(g); |
234 int i = 1; |
350 int i = 1; |
235 for(NodeIt v(g); v != INVALID; ++v) { |
351 for(NodeIt v(g); v != INVALID; ++v) { |