]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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(in, 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 ( in_line.c_str(), "%*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 ( in_line.c_str(),"%*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 ( in_line.c_str(),"%*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 ( "\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 |