| //======================================================================= | |
| // 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 const 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 |