1 //=======================================================================
2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
3 // Authors: Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee
4 //
5 // Distributed under the Boost Software License, Version 1.0. (See
6 // accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 //=======================================================================
9
10 /*
11 Reads maximal flow problem in extended DIMACS format.
12 This works, but could use some polishing.
13 */
14
15 /* ----------------------------------------------------------------- */
16
17 #ifndef BOOST_GRAPH_READ_DIMACS_HPP
18 #define BOOST_GRAPH_READ_DIMACS_HPP
19
20 #include <vector>
21 #include <iostream>
22 #include <string>
23 #include <cstdio>
24 #include <cstring>
25 #include <cstdlib>
26
27 #include <boost/graph/graph_traits.hpp>
28
29 namespace boost
30 {
31
32 namespace detail
33 {
34
35 template < class Graph, class CapacityMap, class ReverseEdgeMap >
read_dimacs_max_flow_internal(Graph & g,CapacityMap capacity,ReverseEdgeMap reverse_edge,typename graph_traits<Graph>::vertex_descriptor & src,typename graph_traits<Graph>::vertex_descriptor & sink,std::istream & in,bool require_source_and_sink,const std::string & problem_type)36 int read_dimacs_max_flow_internal(Graph& g, CapacityMap capacity,
37 ReverseEdgeMap reverse_edge,
38 typename graph_traits< Graph >::vertex_descriptor& src,
39 typename graph_traits< Graph >::vertex_descriptor& sink,
40 std::istream& in, bool require_source_and_sink,
41 const std::string& problem_type)
42 {
43 // const int MAXLINE = 100; /* max line length in the input file
44 // */
45 const int ARC_FIELDS = 3; /* no of fields in arc line */
46 const int NODE_FIELDS = 2; /* no of fields in node line */
47 const int P_FIELDS = 3; /* no of fields in problem line */
48
49 typedef
50 typename graph_traits< Graph >::vertex_descriptor vertex_descriptor;
51 typedef typename graph_traits< Graph >::edge_descriptor edge_descriptor;
52
53 std::vector< vertex_descriptor > verts;
54
55 long m, n, /* number of edges and nodes */
56 i, head, tail, cap;
57
58 long no_lines = 0, /* no of current input line */
59 no_plines = 0, /* no of problem-lines */
60 no_nslines = 0, /* no of node-source-lines */
61 no_nklines = 0, /* no of node-source-lines */
62 no_alines = 0; /* no of arc-lines */
63
64 std::string in_line; /* for reading input line */
65 char pr_type[4]; /* for reading type of the problem */
66 char nd; /* source (s) or sink (t) */
67
68 int k, /* temporary */
69 err_no; /* no of detected error */
70
71 /* -------------- error numbers & error messages ---------------- */
72 const int EN1 = 0;
73 const int EN2 = 1;
74 const int EN3 = 2;
75 const int EN4 = 3;
76 // const int EN6 = 4;
77 // const int EN10 = 5;
78 // const int EN7 = 6;
79 const int EN8 = 7;
80 const int EN9 = 8;
81 const int EN11 = 9;
82 const int EN12 = 10;
83 // const int EN13 = 11;
84 const int EN14 = 12;
85 const int EN16 = 13;
86 const int EN15 = 14;
87 const int EN17 = 15;
88 const int EN18 = 16;
89 const int EN21 = 17;
90 const int EN19 = 18;
91 const int EN20 = 19;
92 const int EN22 = 20;
93
94 static const char* err_message[] = {
95 /* 0*/ "more than one problem line.",
96 /* 1*/ "wrong number of parameters in the problem line.",
97 /* 2*/ "it is not a Max Flow problem line.",
98 /* 3*/ "bad value of a parameter in the problem line.",
99 /* 4*/ "can't obtain enough memory to solve this problem.",
100 /* 5*/ "more than one line with the problem name.",
101 /* 6*/ "can't read problem name.",
102 /* 7*/ "problem description must be before node description.",
103 /* 8*/ "this parser doesn't support multiply sources and sinks.",
104 /* 9*/ "wrong number of parameters in the node line.",
105 /*10*/ "wrong value of parameters in the node line.",
106 /*11*/ " ",
107 /*12*/
108 "source and sink descriptions must be before arc descriptions.",
109 /*13*/ "too many arcs in the input.",
110 /*14*/ "wrong number of parameters in the arc line.",
111 /*15*/ "wrong value of parameters in the arc line.",
112 /*16*/ "unknown line type in the input.",
113 /*17*/ "reading error.",
114 /*18*/ "not enough arcs in the input.",
115 /*19*/ "source or sink doesn't have incident arcs.",
116 /*20*/ "can't read anything from the input file."
117 };
118 /* --------------------------------------------------------------- */
119
120 /* The main loop:
121 - reads the line of the input,
122 - analyses its type,
123 - checks correctness of parameters,
124 - puts data to the arrays,
125 - does service functions
126 */
127
128 while (std::getline(in, in_line))
129 {
130 ++no_lines;
131
132 switch (in_line[0])
133 {
134 case 'c': /* skip lines with comments */
135 case '\n': /* skip empty lines */
136 case '\0': /* skip empty lines at the end of file */
137 break;
138
139 case 'p': /* problem description */
140 if (no_plines > 0)
141 /* more than one problem line */
142 {
143 err_no = EN1;
144 goto error;
145 }
146
147 no_plines = 1;
148
149 if (
150 /* reading problem line: type of problem, no of nodes, no of
151 arcs */
152 std::sscanf(
153 in_line.c_str(), "%*c %3s %ld %ld", pr_type, &n, &m)
154 != P_FIELDS)
155 /*wrong number of parameters in the problem line*/
156 {
157 err_no = EN2;
158 goto error;
159 }
160
161 if (pr_type != problem_type)
162 /*wrong problem type*/
163 {
164 err_no = EN3;
165 goto error;
166 }
167
168 if (n <= 0 || m <= 0)
169 /*wrong value of no of arcs or nodes*/
170 {
171 err_no = EN4;
172 goto error;
173 }
174
175 {
176 for (long vi = 0; vi < n; ++vi)
177 verts.push_back(add_vertex(g));
178 }
179 break;
180
181 case 'n': /* source(s) description */
182 if (no_plines == 0)
183 /* there was not problem line above */
184 {
185 err_no = EN8;
186 goto error;
187 }
188
189 /* reading source or sink */
190 k = std::sscanf(in_line.c_str(), "%*c %ld %c", &i, &nd);
191 --i; // index from 0
192 if (k < NODE_FIELDS)
193 /* node line is incorrect */
194 {
195 err_no = EN11;
196 goto error;
197 }
198
199 if (i < 0 || i > n)
200 /* wrong value of node */
201 {
202 err_no = EN12;
203 goto error;
204 }
205
206 switch (nd)
207 {
208 case 's': /* source line */
209
210 if (no_nslines != 0)
211 /* more than one source line */
212 {
213 err_no = EN9;
214 goto error;
215 }
216
217 no_nslines = 1;
218 src = verts[i];
219 break;
220
221 case 't': /* sink line */
222
223 if (no_nklines != 0)
224 /* more than one sink line */
225 {
226 err_no = EN9;
227 goto error;
228 }
229
230 no_nklines = 1;
231 sink = verts[i];
232 break;
233
234 default:
235 /* wrong type of node-line */
236 err_no = EN12;
237 goto error;
238 }
239 break;
240
241 case 'a': /* arc description */
242 if (require_source_and_sink
243 && (no_nslines == 0 || no_nklines == 0))
244 /* there was not source and sink description above */
245 {
246 err_no = EN14;
247 goto error;
248 }
249
250 if (no_alines >= m)
251 /*too many arcs on input*/
252 {
253 err_no = EN16;
254 goto error;
255 }
256
257 if (
258 /* reading an arc description */
259 std::sscanf(
260 in_line.c_str(), "%*c %ld %ld %ld", &tail, &head, &cap)
261 != ARC_FIELDS)
262 /* arc description is not correct */
263 {
264 err_no = EN15;
265 goto error;
266 }
267
268 --tail; // index from 0, not 1
269 --head;
270 if (tail < 0 || tail > n || head < 0 || head > n)
271 /* wrong value of nodes */
272 {
273 err_no = EN17;
274 goto error;
275 }
276
277 {
278 edge_descriptor e1, e2;
279 bool in1, in2;
280 boost::tie(e1, in1) = add_edge(verts[tail], verts[head], g);
281 boost::tie(e2, in2) = add_edge(verts[head], verts[tail], g);
282 if (!in1 || !in2)
283 {
284 std::cerr << "unable to add edge (" << head << ","
285 << tail << ")" << std::endl;
286 return -1;
287 }
288 capacity[e1] = cap;
289 capacity[e2] = 0;
290 reverse_edge[e1] = e2;
291 reverse_edge[e2] = e1;
292 }
293 ++no_alines;
294 break;
295
296 default:
297 /* unknown type of line */
298 err_no = EN18;
299 goto error;
300
301 } /* end of switch */
302 } /* end of input loop */
303
304 /* ----- all is red or error while reading ----- */
305
306 if (in.eof() == 0) /* reading error */
307 {
308 err_no = EN21;
309 goto error;
310 }
311
312 if (no_lines == 0) /* empty input */
313 {
314 err_no = EN22;
315 goto error;
316 }
317
318 if (no_alines < m) /* not enough arcs */
319 {
320 err_no = EN19;
321 goto error;
322 }
323
324 if (require_source_and_sink
325 && (out_degree(src, g) == 0 || out_degree(sink, g) == 0))
326 /* no arc goes out of the source */
327 {
328 err_no = EN20;
329 goto error;
330 }
331
332 /* Thanks God! all is done */
333 return (0);
334
335 /* ---------------------------------- */
336 error: /* error found reading input */
337
338 std::printf(
339 "\nline %ld of input - %s\n", no_lines, err_message[err_no]);
340
341 return -1;
342 }
343 /* -------------------- end of parser -------------------*/
344
345 } // namespace detail
346
347 template < class Graph, class CapacityMap, class ReverseEdgeMap >
read_dimacs_max_flow(Graph & g,CapacityMap capacity,ReverseEdgeMap reverse_edge,typename graph_traits<Graph>::vertex_descriptor & src,typename graph_traits<Graph>::vertex_descriptor & sink,std::istream & in=std::cin)348 int read_dimacs_max_flow(Graph& g, CapacityMap capacity,
349 ReverseEdgeMap reverse_edge,
350 typename graph_traits< Graph >::vertex_descriptor& src,
351 typename graph_traits< Graph >::vertex_descriptor& sink,
352 std::istream& in = std::cin)
353 {
354 return detail::read_dimacs_max_flow_internal(
355 g, capacity, reverse_edge, src, sink, in, true, "max");
356 }
357
358 template < class Graph, class CapacityMap, class ReverseEdgeMap >
read_dimacs_min_cut(Graph & g,CapacityMap capacity,ReverseEdgeMap reverse_edge,std::istream & in=std::cin)359 int read_dimacs_min_cut(Graph& g, CapacityMap capacity,
360 ReverseEdgeMap reverse_edge, std::istream& in = std::cin)
361 {
362 typename graph_traits< Graph >::vertex_descriptor dummy_src,
363 dummy_sink; // Not filled in
364 return detail::read_dimacs_max_flow_internal(
365 g, capacity, reverse_edge, dummy_src, dummy_sink, in, false, "cut");
366 }
367
368 } // namespace boost
369
370 #endif // BOOST_GRAPH_READ_DIMACS_HPP
371