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>
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)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>
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)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>
read_dimacs_min_cut(Graph & g,CapacityMap capacity,ReverseEdgeMap reverse_edge,std::istream & in=std::cin)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