path: root/boost/graph/read_dimacs.hpp

//=======================================================================
// 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>::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] );

  return -1;
}
/* --------------------   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