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