35 /// @{ |
35 /// @{ |
36 |
36 |
37 /// DIMACS file type descriptor. |
37 /// DIMACS file type descriptor. |
38 struct DimacsDescriptor |
38 struct DimacsDescriptor |
39 { |
39 { |
40 ///File type enum |
40 ///\brief DIMACS file type enum |
41 enum Type |
41 /// |
42 { |
42 ///DIMACS file type enum. |
43 NONE, MIN, MAX, SP, MAT |
43 enum Type { |
44 }; |
44 NONE, ///< Undefined type. |
|
45 MIN, ///< DIMACS file type for minimum cost flow problems. |
|
46 MAX, ///< DIMACS file type for maximum flow problems. |
|
47 SP, ///< DIMACS file type for shostest path problems. |
|
48 MAT ///< DIMACS file type for plain graphs and matching problems. |
|
49 }; |
45 ///The file type |
50 ///The file type |
46 Type type; |
51 Type type; |
47 ///The number of nodes in the graph |
52 ///The number of nodes in the graph |
48 int nodeNum; |
53 int nodeNum; |
49 ///The number of edges in the graph |
54 ///The number of edges in the graph |
50 int edgeNum; |
55 int edgeNum; |
51 int lineShift; |
56 int lineShift; |
52 /// Constructor. Sets the type to NONE. |
57 ///Constructor. It sets the type to \c NONE. |
53 DimacsDescriptor() : type(NONE) {} |
58 DimacsDescriptor() : type(NONE) {} |
54 }; |
59 }; |
55 |
60 |
56 ///Discover the type of a DIMACS file |
61 ///Discover the type of a DIMACS file |
57 |
62 |
58 ///It starts seeking the beginning of the file for the problem type |
63 ///This function starts seeking the beginning of the given file for the |
59 ///and size info. The found data is returned in a special struct |
64 ///problem type and size info. |
60 ///that can be evaluated and passed to the appropriate reader |
65 ///The found data is returned in a special struct that can be evaluated |
61 ///function. |
66 ///and passed to the appropriate reader function. |
62 DimacsDescriptor dimacsType(std::istream& is) |
67 DimacsDescriptor dimacsType(std::istream& is) |
63 { |
68 { |
64 DimacsDescriptor r; |
69 DimacsDescriptor r; |
65 std::string problem,str; |
70 std::string problem,str; |
66 char c; |
71 char c; |
94 } |
99 } |
95 throw FormatError("Missing problem type declaration."); |
100 throw FormatError("Missing problem type declaration."); |
96 } |
101 } |
97 |
102 |
98 |
103 |
99 |
104 /// \brief DIMACS minimum cost flow reader function. |
100 /// DIMACS minimum cost flow reader function. |
|
101 /// |
105 /// |
102 /// This function reads a minimum cost flow instance from DIMACS format, |
106 /// This function reads a minimum cost flow instance from DIMACS format, |
103 /// i.e. from a DIMACS file having a line starting with |
107 /// i.e. from a DIMACS file having a line starting with |
104 /// \code |
108 /// \code |
105 /// p min |
109 /// p min |
285 if(desc.type!=DimacsDescriptor::MAX) |
289 if(desc.type!=DimacsDescriptor::MAX) |
286 throw FormatError("Problem type mismatch"); |
290 throw FormatError("Problem type mismatch"); |
287 _readDimacs(is,g,capacity,s,t,infty,desc); |
291 _readDimacs(is,g,capacity,s,t,infty,desc); |
288 } |
292 } |
289 |
293 |
290 /// DIMACS shortest path reader function. |
294 /// \brief DIMACS shortest path reader function. |
291 /// |
295 /// |
292 /// This function reads a shortest path instance from DIMACS format, |
296 /// This function reads a shortest path instance from DIMACS format, |
293 /// i.e. from a DIMACS file having a line starting with |
297 /// i.e. from a DIMACS file having a line starting with |
294 /// \code |
298 /// \code |
295 /// p sp |
299 /// p sp |
311 if(desc.type!=DimacsDescriptor::SP) |
315 if(desc.type!=DimacsDescriptor::SP) |
312 throw FormatError("Problem type mismatch"); |
316 throw FormatError("Problem type mismatch"); |
313 _readDimacs(is, g, length, s, t, 0, desc); |
317 _readDimacs(is, g, length, s, t, 0, desc); |
314 } |
318 } |
315 |
319 |
316 /// DIMACS capacitated digraph reader function. |
320 /// \brief DIMACS capacitated digraph reader function. |
317 /// |
321 /// |
318 /// This function reads an arc capacitated digraph instance from |
322 /// This function reads an arc capacitated digraph instance from |
319 /// DIMACS 'max' or 'sp' format. |
323 /// DIMACS 'max' or 'sp' format. |
320 /// At the beginning, \c g is cleared by \c g.clear() |
324 /// At the beginning, \c g is cleared by \c g.clear() |
321 /// and the arc capacities/lengths are written to the \c capacity |
325 /// and the arc capacities/lengths are written to the \c capacity |
357 dummy<1> = 1) |
361 dummy<1> = 1) |
358 { |
362 { |
359 g.addArc(s,t); |
363 g.addArc(s,t); |
360 } |
364 } |
361 |
365 |
362 /// DIMACS plain (di)graph reader function. |
366 /// \brief DIMACS plain (di)graph reader function. |
363 /// |
367 /// |
364 /// This function reads a (di)graph without any designated nodes and |
368 /// This function reads a plain (di)graph without any designated nodes |
365 /// maps from DIMACS format, i.e. from DIMACS files having a line |
369 /// and maps (e.g. a matching instance) from DIMACS format, i.e. from |
366 /// starting with |
370 /// DIMACS files having a line starting with |
367 /// \code |
371 /// \code |
368 /// p mat |
372 /// p mat |
369 /// \endcode |
373 /// \endcode |
370 /// At the beginning, \c g is cleared by \c g.clear(). |
374 /// At the beginning, \c g is cleared by \c g.clear(). |
371 /// |
375 /// |