boost/graph/read_dimacs.hpp

0001 //=======================================================================
0002 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
0003 // Authors: Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee
0004 //
0005 // Distributed under the Boost Software License, Version 1.0. (See
0006 // accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008 //=======================================================================
0009
0010 /*
0011   Reads maximal flow problem in extended DIMACS format.
0012   This works, but could use some polishing.
0013 */
0014
0015 /* ----------------------------------------------------------------- */
0016
0017 #ifndef BOOST_GRAPH_READ_DIMACS_HPP
0018 #define BOOST_GRAPH_READ_DIMACS_HPP
0019
0020 #include <vector>
0021 #include <iostream>
0022 #include <string>
0023 #include <cstdio>
0024 #include <cstring>
0025 #include <cstdlib>
0026
0027 #include <boost/graph/graph_traits.hpp>
0028
0029 namespace boost
0030 {
0031
0032 namespace detail
0033 {
0034
0035     template < class Graph, class CapacityMap, class ReverseEdgeMap >
0036     int read_dimacs_max_flow_internal(Graph& g, CapacityMap capacity,
0037         ReverseEdgeMap reverse_edge,
0038         typename graph_traits< Graph >::vertex_descriptor& src,
0039         typename graph_traits< Graph >::vertex_descriptor& sink,
0040         std::istream& in, bool require_source_and_sink,
0041         const std::string& problem_type)
0042     {
0043         //  const int MAXLINE = 100;      /* max line length in the input file
0044         //  */
0045         const int ARC_FIELDS = 3; /* no of fields in arc line  */
0046         const int NODE_FIELDS = 2; /* no of fields in node line  */
0047         const int P_FIELDS = 3; /* no of fields in problem line */
0048
0049         typedef
0050             typename graph_traits< Graph >::vertex_descriptor vertex_descriptor;
0051         typedef typename graph_traits< Graph >::edge_descriptor edge_descriptor;
0052
0053         std::vector< vertex_descriptor > verts;
0054
0055         long m, n, /*  number of edges and nodes */
0056             i, head, tail, cap;
0057
0058         long no_lines = 0, /* no of current input line */
0059             no_plines = 0, /* no of problem-lines */
0060             no_nslines = 0, /* no of node-source-lines */
0061             no_nklines = 0, /* no of node-source-lines */
0062             no_alines = 0; /* no of arc-lines */
0063
0064         std::string in_line; /* for reading input line */
0065         char pr_type[4]; /* for reading type of the problem */
0066         char nd; /* source (s) or sink (t) */
0067
0068         int k, /* temporary */
0069             err_no; /* no of detected error */
0070
0071         /* -------------- error numbers & error messages ---------------- */
0072         const int EN1 = 0;
0073         const int EN2 = 1;
0074         const int EN3 = 2;
0075         const int EN4 = 3;
0076         //  const int EN6   = 4;
0077         //  const int EN10  = 5;
0078         //  const int EN7   = 6;
0079         const int EN8 = 7;
0080         const int EN9 = 8;
0081         const int EN11 = 9;
0082         const int EN12 = 10;
0083         //  const int EN13 = 11;
0084         const int EN14 = 12;
0085         const int EN16 = 13;
0086         const int EN15 = 14;
0087         const int EN17 = 15;
0088         const int EN18 = 16;
0089         const int EN21 = 17;
0090         const int EN19 = 18;
0091         const int EN20 = 19;
0092         const int EN22 = 20;
0093
0094         static const char* err_message[] = {
0095             /* 0*/ "more than one problem line.",
0096             /* 1*/ "wrong number of parameters in the problem line.",
0097             /* 2*/ "it is not a Max Flow problem line.",
0098             /* 3*/ "bad value of a parameter in the problem line.",
0099             /* 4*/ "can't obtain enough memory to solve this problem.",
0100             /* 5*/ "more than one line with the problem name.",
0101             /* 6*/ "can't read problem name.",
0102             /* 7*/ "problem description must be before node description.",
0103             /* 8*/ "this parser doesn't support multiply sources and sinks.",
0104             /* 9*/ "wrong number of parameters in the node line.",
0105             /*10*/ "wrong value of parameters in the node line.",
0106             /*11*/ " ",
0107             /*12*/
0108             "source and sink descriptions must be before arc descriptions.",
0109             /*13*/ "too many arcs in the input.",
0110             /*14*/ "wrong number of parameters in the arc line.",
0111             /*15*/ "wrong value of parameters in the arc line.",
0112             /*16*/ "unknown line type in the input.",
0113             /*17*/ "reading error.",
0114             /*18*/ "not enough arcs in the input.",
0115             /*19*/ "source or sink doesn't have incident arcs.",
0116             /*20*/ "can't read anything from the input file."
0117         };
0118         /* --------------------------------------------------------------- */
0119
0120         /* The main loop:
0121            -  reads the line of the input,
0122            -  analyses its type,
0123            -  checks correctness of parameters,
0124            -  puts data to the arrays,
0125            -  does service functions
0126         */
0127
0128         while (std::getline(in, in_line))
0129         {
0130             ++no_lines;
0131
0132             switch (in_line[0])
0133             {
0134             case 'c': /* skip lines with comments */
0135             case '\n': /* skip empty lines   */
0136             case '\0': /* skip empty lines at the end of file */
0137                 break;
0138
0139             case 'p': /* problem description      */
0140                 if (no_plines > 0)
0141                 /* more than one problem line */
0142                 {
0143                     err_no = EN1;
0144                     goto error;
0145                 }
0146
0147                 no_plines = 1;
0148
0149                 if (
0150                     /* reading problem line: type of problem, no of nodes, no of
0151                        arcs */
0152                     std::sscanf(
0153                         in_line.c_str(), "%*c %3s %ld %ld", pr_type, &n, &m)
0154                     != P_FIELDS)
0155                 /*wrong number of parameters in the problem line*/
0156                 {
0157                     err_no = EN2;
0158                     goto error;
0159                 }
0160
0161                 if (pr_type != problem_type)
0162                 /*wrong problem type*/
0163                 {
0164                     err_no = EN3;
0165                     goto error;
0166                 }
0167
0168                 if (n <= 0 || m <= 0)
0169                 /*wrong value of no of arcs or nodes*/
0170                 {
0171                     err_no = EN4;
0172                     goto error;
0173                 }
0174
0175                 {
0176                     for (long vi = 0; vi < n; ++vi)
0177                         verts.push_back(add_vertex(g));
0178                 }
0179                 break;
0180
0181             case 'n': /* source(s) description */
0182                 if (no_plines == 0)
0183                 /* there was not problem line above */
0184                 {
0185                     err_no = EN8;
0186                     goto error;
0187                 }
0188
0189                 /* reading source  or sink */
0190                 k = std::sscanf(in_line.c_str(), "%*c %ld %c", &i, &nd);
0191                 --i; // index from 0
0192                 if (k < NODE_FIELDS)
0193                 /* node line is incorrect */
0194                 {
0195                     err_no = EN11;
0196                     goto error;
0197                 }
0198
0199                 if (i < 0 || i > n)
0200                 /* wrong value of node */
0201                 {
0202                     err_no = EN12;
0203                     goto error;
0204                 }
0205
0206                 switch (nd)
0207                 {
0208                 case 's': /* source line */
0209
0210                     if (no_nslines != 0)
0211                     /* more than one source line */
0212                     {
0213                         err_no = EN9;
0214                         goto error;
0215                     }
0216
0217                     no_nslines = 1;
0218                     src = verts[i];
0219                     break;
0220
0221                 case 't': /* sink line */
0222
0223                     if (no_nklines != 0)
0224                     /* more than one sink line */
0225                     {
0226                         err_no = EN9;
0227                         goto error;
0228                     }
0229
0230                     no_nklines = 1;
0231                     sink = verts[i];
0232                     break;
0233
0234                 default:
0235                     /* wrong type of node-line */
0236                     err_no = EN12;
0237                     goto error;
0238                 }
0239                 break;
0240
0241             case 'a': /* arc description */
0242                 if (require_source_and_sink
0243                     && (no_nslines == 0 || no_nklines == 0))
0244                 /* there was not source and sink description above */
0245                 {
0246                     err_no = EN14;
0247                     goto error;
0248                 }
0249
0250                 if (no_alines >= m)
0251                 /*too many arcs on input*/
0252                 {
0253                     err_no = EN16;
0254                     goto error;
0255                 }
0256
0257                 if (
0258                     /* reading an arc description */
0259                     std::sscanf(
0260                         in_line.c_str(), "%*c %ld %ld %ld", &tail, &head, &cap)
0261                     != ARC_FIELDS)
0262                 /* arc description is not correct */
0263                 {
0264                     err_no = EN15;
0265                     goto error;
0266                 }
0267
0268                 --tail; // index from 0, not 1
0269                 --head;
0270                 if (tail < 0 || tail > n || head < 0 || head > n)
0271                 /* wrong value of nodes */
0272                 {
0273                     err_no = EN17;
0274                     goto error;
0275                 }
0276
0277                 {
0278                     edge_descriptor e1, e2;
0279                     bool in1, in2;
0280                     boost::tie(e1, in1) = add_edge(verts[tail], verts[head], g);
0281                     boost::tie(e2, in2) = add_edge(verts[head], verts[tail], g);
0282                     if (!in1 || !in2)
0283                     {
0284                         std::cerr << "unable to add edge (" << head << ","
0285                                   << tail << ")" << std::endl;
0286                         return -1;
0287                     }
0288                     capacity[e1] = cap;
0289                     capacity[e2] = 0;
0290                     reverse_edge[e1] = e2;
0291                     reverse_edge[e2] = e1;
0292                 }
0293                 ++no_alines;
0294                 break;
0295
0296             default:
0297                 /* unknown type of line */
0298                 err_no = EN18;
0299                 goto error;
0300
0301             } /* end of switch */
0302         } /* end of input loop */
0303
0304         /* ----- all is red  or  error while reading ----- */
0305
0306         if (in.eof() == 0) /* reading error */
0307         {
0308             err_no = EN21;
0309             goto error;
0310         }
0311
0312         if (no_lines == 0) /* empty input */
0313         {
0314             err_no = EN22;
0315             goto error;
0316         }
0317
0318         if (no_alines < m) /* not enough arcs */
0319         {
0320             err_no = EN19;
0321             goto error;
0322         }
0323
0324         if (require_source_and_sink
0325             && (out_degree(src, g) == 0 || out_degree(sink, g) == 0))
0326         /* no arc goes out of the source */
0327         {
0328             err_no = EN20;
0329             goto error;
0330         }
0331
0332         /* Thanks God! all is done */
0333         return (0);
0334
0335         /* ---------------------------------- */
0336     error: /* error found reading input */
0337
0338         std::printf(
0339             "\nline %ld of input - %s\n", no_lines, err_message[err_no]);
0340
0341         return -1;
0342     }
0343     /* --------------------   end of parser  -------------------*/
0344
0345 } // namespace detail
0346
0347 template < class Graph, class CapacityMap, class ReverseEdgeMap >
0348 int read_dimacs_max_flow(Graph& g, CapacityMap capacity,
0349     ReverseEdgeMap reverse_edge,
0350     typename graph_traits< Graph >::vertex_descriptor& src,
0351     typename graph_traits< Graph >::vertex_descriptor& sink,
0352     std::istream& in = std::cin)
0353 {
0354     return detail::read_dimacs_max_flow_internal(
0355         g, capacity, reverse_edge, src, sink, in, true, "max");
0356 }
0357
0358 template < class Graph, class CapacityMap, class ReverseEdgeMap >
0359 int read_dimacs_min_cut(Graph& g, CapacityMap capacity,
0360     ReverseEdgeMap reverse_edge, std::istream& in = std::cin)
0361 {
0362     typename graph_traits< Graph >::vertex_descriptor dummy_src,
0363         dummy_sink; // Not filled in
0364     return detail::read_dimacs_max_flow_internal(
0365         g, capacity, reverse_edge, dummy_src, dummy_sink, in, false, "cut");
0366 }
0367
0368 } // namespace boost
0369
0370 #endif // BOOST_GRAPH_READ_DIMACS_HPP