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