equal
deleted
inserted
replaced
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
2 * |
2 * |
3 * This file is a part of LEMON, a generic C++ optimization library. |
3 * This file is a part of LEMON, a generic C++ optimization library. |
4 * |
4 * |
5 * Copyright (C) 2003-2009 |
5 * Copyright (C) 2003-2010 |
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
8 * |
8 * |
9 * Permission to use, modify and distribute this software is granted |
9 * Permission to use, modify and distribute this software is granted |
10 * provided that this copyright notice appears in all copies. For |
10 * provided that this copyright notice appears in all copies. For |
59 }; |
59 }; |
60 |
60 |
61 ///Discover the type of a DIMACS file |
61 ///Discover the type of a DIMACS file |
62 |
62 |
63 ///This function starts seeking the beginning of the given file for the |
63 ///This function starts seeking the beginning of the given file for the |
64 ///problem type and size info. |
64 ///problem type and size info. |
65 ///The found data is returned in a special struct that can be evaluated |
65 ///The found data is returned in a special struct that can be evaluated |
66 ///and passed to the appropriate reader function. |
66 ///and passed to the appropriate reader function. |
67 DimacsDescriptor dimacsType(std::istream& is) |
67 DimacsDescriptor dimacsType(std::istream& is) |
68 { |
68 { |
69 DimacsDescriptor r; |
69 DimacsDescriptor r; |
210 |
210 |
211 if(infty==0) |
211 if(infty==0) |
212 infty = std::numeric_limits<Capacity>::has_infinity ? |
212 infty = std::numeric_limits<Capacity>::has_infinity ? |
213 std::numeric_limits<Capacity>::infinity() : |
213 std::numeric_limits<Capacity>::infinity() : |
214 std::numeric_limits<Capacity>::max(); |
214 std::numeric_limits<Capacity>::max(); |
215 |
215 |
216 while (is >> c) { |
216 while (is >> c) { |
217 switch (c) { |
217 switch (c) { |
218 case 'c': // comment line |
218 case 'c': // comment line |
219 getline(is, str); |
219 getline(is, str); |
220 break; |
220 break; |
235 if (desc.type==DimacsDescriptor::SP) { |
235 if (desc.type==DimacsDescriptor::SP) { |
236 is >> i >> j >> _cap; |
236 is >> i >> j >> _cap; |
237 getline(is, str); |
237 getline(is, str); |
238 e = g.addArc(nodes[i], nodes[j]); |
238 e = g.addArc(nodes[i], nodes[j]); |
239 capacity.set(e, _cap); |
239 capacity.set(e, _cap); |
240 } |
240 } |
241 else if (desc.type==DimacsDescriptor::MAX) { |
241 else if (desc.type==DimacsDescriptor::MAX) { |
242 is >> i >> j >> _cap; |
242 is >> i >> j >> _cap; |
243 getline(is, str); |
243 getline(is, str); |
244 e = g.addArc(nodes[i], nodes[j]); |
244 e = g.addArc(nodes[i], nodes[j]); |
245 if (_cap >= 0) |
245 if (_cap >= 0) |
360 _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t, |
360 _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t, |
361 dummy<1> = 1) |
361 dummy<1> = 1) |
362 { |
362 { |
363 g.addArc(s,t); |
363 g.addArc(s,t); |
364 } |
364 } |
365 |
365 |
366 /// \brief DIMACS plain (di)graph reader function. |
366 /// \brief DIMACS plain (di)graph reader function. |
367 /// |
367 /// |
368 /// This function reads a plain (di)graph without any designated nodes |
368 /// This function reads a plain (di)graph without any designated nodes |
369 /// and maps (e.g. a matching instance) from DIMACS format, i.e. from |
369 /// and maps (e.g. a matching instance) from DIMACS format, i.e. from |
370 /// DIMACS files having a line starting with |
370 /// DIMACS files having a line starting with |
371 /// \code |
371 /// \code |
372 /// p mat |
372 /// p mat |
373 /// \endcode |
373 /// \endcode |
374 /// At the beginning, \c g is cleared by \c g.clear(). |
374 /// At the beginning, \c g is cleared by \c g.clear(). |
390 std::string str; |
390 std::string str; |
391 nodes.resize(desc.nodeNum + 1); |
391 nodes.resize(desc.nodeNum + 1); |
392 for (int k = 1; k <= desc.nodeNum; ++k) { |
392 for (int k = 1; k <= desc.nodeNum; ++k) { |
393 nodes[k] = g.addNode(); |
393 nodes[k] = g.addNode(); |
394 } |
394 } |
395 |
395 |
396 while (is >> c) { |
396 while (is >> c) { |
397 switch (c) { |
397 switch (c) { |
398 case 'c': // comment line |
398 case 'c': // comment line |
399 getline(is, str); |
399 getline(is, str); |
400 break; |
400 break; |