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