1 //=======================================================================
2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
3 // Authors: Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee
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 //=======================================================================
11 Reads maximal flow problem in extended DIMACS format.
12 This works, but could use some polishing.
15 /* ----------------------------------------------------------------- */
17 #ifndef BOOST_GRAPH_READ_DIMACS_HPP
18 #define BOOST_GRAPH_READ_DIMACS_HPP
27 #include <boost/graph/graph_traits.hpp>
33 template <class Graph, class CapacityMap, class ReverseEdgeMap>
34 int read_dimacs_max_flow_internal(Graph& g,
36 ReverseEdgeMap reverse_edge,
37 typename graph_traits<Graph>::vertex_descriptor& src,
38 typename graph_traits<Graph>::vertex_descriptor& sink,
40 bool require_source_and_sink,
41 const std::string& problem_type)
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 */
48 typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
49 typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
51 std::vector<vertex_descriptor> verts;
53 long m, n, /* number of edges and nodes */
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 */
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) */
66 int k, /* temporary */
67 err_no; /* no of detected error */
69 /* -------------- error numbers & error messages ---------------- */
75 // const int EN10 = 5;
81 // const int EN13 = 11;
92 static const char *err_message[] =
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.",
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."
116 /* --------------------------------------------------------------- */
119 - reads the line of the input,
121 - checks correctness of parameters,
122 - puts data to the arrays,
123 - does service functions
126 while (std::getline(in, in_line)) {
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 */
135 case 'p': /* problem description */
137 /* more than one problem line */
138 { err_no = EN1 ; goto error; }
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 )
147 /*wrong number of parameters in the problem line*/
148 { err_no = EN2; goto error; }
150 if ( pr_type != problem_type )
151 /*wrong problem type*/
152 { err_no = EN3; goto error; }
154 if ( n <= 0 || m <= 0 )
155 /*wrong value of no of arcs or nodes*/
156 { err_no = EN4; goto error; }
159 for (long vi = 0; vi < n; ++vi)
160 verts.push_back(add_vertex(g));
164 case 'n': /* source(s) description */
165 if ( no_plines == 0 )
166 /* there was not problem line above */
167 { err_no = EN8; goto error; }
169 /* reading source or sink */
170 k = std::sscanf ( in_line.c_str(),"%*c %ld %c", &i, &nd );
172 if ( k < NODE_FIELDS )
173 /* node line is incorrect */
174 { err_no = EN11; goto error; }
176 if ( i < 0 || i > n )
177 /* wrong value of node */
178 { err_no = EN12; goto error; }
181 case 's': /* source line */
183 if ( no_nslines != 0)
184 /* more than one source line */
185 { err_no = EN9; goto error; }
191 case 't': /* sink line */
193 if ( no_nklines != 0)
194 /* more than one sink line */
195 { err_no = EN9; goto error; }
202 /* wrong type of node-line */
203 err_no = EN12; goto error;
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; }
212 if ( no_alines >= m )
213 /*too many arcs on input*/
214 { err_no = EN16; goto error; }
217 /* reading an arc description */
218 std::sscanf ( in_line.c_str(),"%*c %ld %ld %ld",
222 /* arc description is not correct */
223 { err_no = EN15; goto error; }
225 --tail; // index from 0, not 1
227 if ( tail < 0 || tail > n ||
230 /* wrong value of nodes */
231 { err_no = EN17; goto error; }
234 edge_descriptor e1, e2;
236 boost::tie(e1, in1) = add_edge(verts[tail], verts[head], g);
237 boost::tie(e2, in2) = add_edge(verts[head], verts[tail], g);
239 std::cerr << "unable to add edge (" << head << "," << tail << ")"
245 reverse_edge[e1] = e2;
246 reverse_edge[e2] = e1;
252 /* unknown type of line */
253 err_no = EN18; goto error;
255 } /* end of switch */
256 } /* end of input loop */
258 /* ----- all is red or error while reading ----- */
260 if ( in.eof() == 0 ) /* reading error */
261 { err_no=EN21; goto error; }
263 if ( no_lines == 0 ) /* empty input */
264 { err_no = EN22; goto error; }
266 if ( no_alines < m ) /* not enough arcs */
267 { err_no = EN19; goto error; }
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; }
274 /* Thanks God! all is done */
277 /* ---------------------------------- */
278 error: /* error found reading input */
280 std::printf ( "\nline %ld of input - %s\n",
281 no_lines, err_message[err_no] );
285 /* -------------------- end of parser -------------------*/
287 } // namespace detail
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");
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");
310 #endif // BOOST_GRAPH_READ_DIMACS_HPP