| //======================================================================= |
| // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. |
| // Authors: Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee |
| // |
| // Distributed under the Boost Software License, Version 1.0. (See |
| // accompanying file LICENSE_1_0.txt or copy at |
| // http://www.boost.org/LICENSE_1_0.txt) |
| //======================================================================= |
| |
| /* |
| Reads maximal flow problem in extended DIMACS format. |
| This works, but could use some polishing. |
| */ |
| |
| /* ----------------------------------------------------------------- */ |
| |
| #ifndef BOOST_GRAPH_READ_DIMACS_HPP |
| #define BOOST_GRAPH_READ_DIMACS_HPP |
| |
| #include <vector> |
| #include <iostream> |
| #include <string> |
| #include <cstdio> |
| #include <cstring> |
| #include <cstdlib> |
| |
| #include <boost/graph/graph_traits.hpp> |
| |
| namespace boost { |
| |
| namespace detail { |
| |
| template <class Graph, class CapacityMap, class ReverseEdgeMap> |
| int 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) |
| { |
| // const int MAXLINE = 100; /* max line length in the input file */ |
| const int ARC_FIELDS = 3; /* no of fields in arc line */ |
| const int NODE_FIELDS = 2; /* no of fields in node line */ |
| const int P_FIELDS = 3; /* no of fields in problem line */ |
| |
| typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type; |
| typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; |
| typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor; |
| |
| std::vector<vertex_descriptor> verts; |
| |
| long m, n, /* number of edges and nodes */ |
| i, head, tail, cap; |
| |
| long no_lines=0, /* no of current input line */ |
| no_plines=0, /* no of problem-lines */ |
| no_nslines=0, /* no of node-source-lines */ |
| no_nklines=0, /* no of node-source-lines */ |
| no_alines=0; /* no of arc-lines */ |
| |
| std::string in_line; /* for reading input line */ |
| char pr_type[4]; /* for reading type of the problem */ |
| char nd; /* source (s) or sink (t) */ |
| |
| int k, /* temporary */ |
| err_no; /* no of detected error */ |
| |
| /* -------------- error numbers & error messages ---------------- */ |
| const int EN1 = 0; |
| const int EN2 = 1; |
| const int EN3 = 2; |
| const int EN4 = 3; |
| // const int EN6 = 4; |
| // const int EN10 = 5; |
| // const int EN7 = 6; |
| const int EN8 = 7; |
| const int EN9 = 8; |
| const int EN11 = 9; |
| const int EN12 = 10; |
| // const int EN13 = 11; |
| const int EN14 = 12; |
| const int EN16 = 13; |
| const int EN15 = 14; |
| const int EN17 = 15; |
| const int EN18 = 16; |
| const int EN21 = 17; |
| const int EN19 = 18; |
| const int EN20 = 19; |
| const int EN22 = 20; |
| |
| static char *err_message[] = |
| { |
| /* 0*/ "more than one problem line.", |
| /* 1*/ "wrong number of parameters in the problem line.", |
| /* 2*/ "it is not a Max Flow problem line.", |
| /* 3*/ "bad value of a parameter in the problem line.", |
| /* 4*/ "can't obtain enough memory to solve this problem.", |
| /* 5*/ "more than one line with the problem name.", |
| /* 6*/ "can't read problem name.", |
| /* 7*/ "problem description must be before node description.", |
| /* 8*/ "this parser doesn't support multiply sources and sinks.", |
| /* 9*/ "wrong number of parameters in the node line.", |
| /*10*/ "wrong value of parameters in the node line.", |
| /*11*/ " ", |
| /*12*/ "source and sink descriptions must be before arc descriptions.", |
| /*13*/ "too many arcs in the input.", |
| /*14*/ "wrong number of parameters in the arc line.", |
| /*15*/ "wrong value of parameters in the arc line.", |
| /*16*/ "unknown line type in the input.", |
| /*17*/ "reading error.", |
| /*18*/ "not enough arcs in the input.", |
| /*19*/ "source or sink doesn't have incident arcs.", |
| /*20*/ "can't read anything from the input file." |
| }; |
| /* --------------------------------------------------------------- */ |
| |
| /* The main loop: |
| - reads the line of the input, |
| - analyses its type, |
| - checks correctness of parameters, |
| - puts data to the arrays, |
| - does service functions |
| */ |
| |
| while (std::getline(in, in_line)) { |
| ++no_lines; |
| |
| switch (in_line[0]) { |
| case 'c': /* skip lines with comments */ |
| case '\n': /* skip empty lines */ |
| case '\0': /* skip empty lines at the end of file */ |
| break; |
| |
| case 'p': /* problem description */ |
| if ( no_plines > 0 ) |
| /* more than one problem line */ |
| { err_no = EN1 ; goto error; } |
| |
| no_plines = 1; |
| |
| if ( |
| /* reading problem line: type of problem, no of nodes, no of arcs */ |
| std::sscanf ( in_line.c_str(), "%*c %3s %ld %ld", pr_type, &n, &m ) |
| != P_FIELDS |
| ) |
| /*wrong number of parameters in the problem line*/ |
| { err_no = EN2; goto error; } |
| |
| if ( pr_type != problem_type ) |
| /*wrong problem type*/ |
| { err_no = EN3; goto error; } |
| |
| if ( n <= 0 || m <= 0 ) |
| /*wrong value of no of arcs or nodes*/ |
| { err_no = EN4; goto error; } |
| |
| { |
| for (long vi = 0; vi < n; ++vi) |
| verts.push_back(add_vertex(g)); |
| } |
| break; |
| |
| case 'n': /* source(s) description */ |
| if ( no_plines == 0 ) |
| /* there was not problem line above */ |
| { err_no = EN8; goto error; } |
| |
| /* reading source or sink */ |
| k = std::sscanf ( in_line.c_str(),"%*c %ld %c", &i, &nd ); |
| --i; // index from 0 |
| if ( k < NODE_FIELDS ) |
| /* node line is incorrect */ |
| { err_no = EN11; goto error; } |
| |
| if ( i < 0 || i > n ) |
| /* wrong value of node */ |
| { err_no = EN12; goto error; } |
| |
| switch (nd) { |
| case 's': /* source line */ |
| |
| if ( no_nslines != 0) |
| /* more than one source line */ |
| { err_no = EN9; goto error; } |
| |
| no_nslines = 1; |
| src = verts[i]; |
| break; |
| |
| case 't': /* sink line */ |
| |
| if ( no_nklines != 0) |
| /* more than one sink line */ |
| { err_no = EN9; goto error; } |
| |
| no_nklines = 1; |
| sink = verts[i]; |
| break; |
| |
| default: |
| /* wrong type of node-line */ |
| err_no = EN12; goto error; |
| } |
| break; |
| |
| case 'a': /* arc description */ |
| if ( require_source_and_sink && (no_nslines == 0 || no_nklines == 0) ) |
| /* there was not source and sink description above */ |
| { err_no = EN14; goto error; } |
| |
| if ( no_alines >= m ) |
| /*too many arcs on input*/ |
| { err_no = EN16; goto error; } |
| |
| if ( |
| /* reading an arc description */ |
| std::sscanf ( in_line.c_str(),"%*c %ld %ld %ld", |
| &tail, &head, &cap ) |
| != ARC_FIELDS |
| ) |
| /* arc description is not correct */ |
| { err_no = EN15; goto error; } |
| |
| --tail; // index from 0, not 1 |
| --head; |
| if ( tail < 0 || tail > n || |
| head < 0 || head > n |
| ) |
| /* wrong value of nodes */ |
| { err_no = EN17; goto error; } |
| |
| { |
| edge_descriptor e1, e2; |
| bool in1, in2; |
| boost::tie(e1, in1) = add_edge(verts[tail], verts[head], g); |
| boost::tie(e2, in2) = add_edge(verts[head], verts[tail], g); |
| if (!in1 || !in2) { |
| std::cerr << "unable to add edge (" << head << "," << tail << ")" |
| << std::endl; |
| return -1; |
| } |
| capacity[e1] = cap; |
| capacity[e2] = 0; |
| reverse_edge[e1] = e2; |
| reverse_edge[e2] = e1; |
| } |
| ++no_alines; |
| break; |
| |
| default: |
| /* unknown type of line */ |
| err_no = EN18; goto error; |
| |
| } /* end of switch */ |
| } /* end of input loop */ |
| |
| /* ----- all is red or error while reading ----- */ |
| |
| if ( in.eof() == 0 ) /* reading error */ |
| { err_no=EN21; goto error; } |
| |
| if ( no_lines == 0 ) /* empty input */ |
| { err_no = EN22; goto error; } |
| |
| if ( no_alines < m ) /* not enough arcs */ |
| { err_no = EN19; goto error; } |
| |
| if ( require_source_and_sink && |
| (out_degree(src, g) == 0 || out_degree(sink, g) == 0) ) |
| /* no arc goes out of the source */ |
| { err_no = EN20; goto error; } |
| |
| /* Thanks God! all is done */ |
| return (0); |
| |
| /* ---------------------------------- */ |
| error: /* error found reading input */ |
| |
| std::printf ( "\nline %ld of input - %s\n", |
| no_lines, err_message[err_no] ); |
| |
| std::exit (1); |
| return (0); /* to avoid warning */ |
| } |
| /* -------------------- end of parser -------------------*/ |
| |
| } // namespace detail |
| |
| template <class Graph, class CapacityMap, class ReverseEdgeMap> |
| int 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) { |
| return detail::read_dimacs_max_flow_internal(g, capacity, reverse_edge, src, sink, in, true, "max"); |
| } |
| |
| template <class Graph, class CapacityMap, class ReverseEdgeMap> |
| int read_dimacs_min_cut(Graph& g, |
| CapacityMap capacity, |
| ReverseEdgeMap reverse_edge, |
| std::istream& in = std::cin) { |
| typename graph_traits<Graph>::vertex_descriptor dummy_src, dummy_sink; // Not filled in |
| return detail::read_dimacs_max_flow_internal(g, capacity, reverse_edge, dummy_src, dummy_sink, in, false, "cut"); |
| } |
| |
| } // namespace boost |
| |
| #endif // BOOST_GRAPH_READ_DIMACS_HPP |