epoc32/include/stdapis/boost/graph/read_dimacs.hpp
branchSymbian2
changeset 2 2fe1408b6811
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/epoc32/include/stdapis/boost/graph/read_dimacs.hpp	Tue Mar 16 16:12:26 2010 +0000
     1.3 @@ -0,0 +1,278 @@
     1.4 +//=======================================================================
     1.5 +// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
     1.6 +// Authors: Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee
     1.7 +//
     1.8 +// Distributed under the Boost Software License, Version 1.0. (See
     1.9 +// accompanying file LICENSE_1_0.txt or copy at
    1.10 +// http://www.boost.org/LICENSE_1_0.txt)
    1.11 +//=======================================================================
    1.12 +
    1.13 +/*
    1.14 +  Reads maximal flow problem in extended DIMACS format.
    1.15 +  
    1.16 +  Reads from stdin. 
    1.17 +
    1.18 +  This works, but could use some polishing. 
    1.19 +*/
    1.20 +
    1.21 +/* ----------------------------------------------------------------- */
    1.22 +
    1.23 +#include <vector>
    1.24 +#include <stdio.h>
    1.25 +
    1.26 +namespace boost {
    1.27 +
    1.28 +template <class Graph, class CapacityMap, class ReverseEdgeMap>
    1.29 +int read_dimacs_max_flow(Graph& g,
    1.30 +                         CapacityMap capacity, 
    1.31 +                         ReverseEdgeMap reverse_edge,
    1.32 +                         typename graph_traits<Graph>::vertex_descriptor& src,
    1.33 +                         typename graph_traits<Graph>::vertex_descriptor& sink)
    1.34 +{
    1.35 +  //  const int MAXLINE = 100;      /* max line length in the input file */
    1.36 +  const int ARC_FIELDS = 3;     /* no of fields in arc line  */
    1.37 +  const int NODE_FIELDS = 2;    /* no of fields in node line  */
    1.38 +  const int P_FIELDS = 3;       /* no of fields in problem line */
    1.39 +  const char* PROBLEM_TYPE = "max"; /* name of problem type*/
    1.40 +
    1.41 +  typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
    1.42 +  typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
    1.43 +  typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
    1.44 +  
    1.45 +  std::vector<vertex_descriptor> verts;
    1.46 +
    1.47 +  long m, n,                    /*  number of edges and nodes */
    1.48 +    i, head, tail, cap;
    1.49 +
    1.50 +  long no_lines=0,              /* no of current input line */
    1.51 +    no_plines=0,                /* no of problem-lines */
    1.52 +    no_nslines=0,               /* no of node-source-lines */
    1.53 +    no_nklines=0,               /* no of node-source-lines */
    1.54 +    no_alines=0;                /* no of arc-lines */
    1.55 +  
    1.56 +  std::string in_line;          /* for reading input line */
    1.57 +  char pr_type[3];              /* for reading type of the problem */
    1.58 +  char nd;                      /* source (s) or sink (t) */
    1.59 +  
    1.60 +  int k,                        /* temporary */
    1.61 +    err_no;                     /* no of detected error */
    1.62 +
    1.63 +  /* -------------- error numbers & error messages ---------------- */
    1.64 +  const int EN1   = 0;
    1.65 +  const int EN2   = 1;
    1.66 +  const int EN3   = 2;
    1.67 +  const int EN4   = 3;
    1.68 +  //  const int EN6   = 4;
    1.69 +  //  const int EN10  = 5;
    1.70 +  //  const int EN7   = 6;
    1.71 +  const int EN8   = 7;
    1.72 +  const int EN9   = 8;
    1.73 +  const int EN11  = 9;
    1.74 +  const int EN12 = 10;
    1.75 +  //  const int EN13 = 11;
    1.76 +  const int EN14 = 12;
    1.77 +  const int EN16 = 13;
    1.78 +  const int EN15 = 14;
    1.79 +  const int EN17 = 15;
    1.80 +  const int EN18 = 16;
    1.81 +  const int EN21 = 17;
    1.82 +  const int EN19 = 18;
    1.83 +  const int EN20 = 19;
    1.84 +  const int EN22 = 20;
    1.85 +  
    1.86 +  static char *err_message[] = 
    1.87 +  { 
    1.88 +    /* 0*/    "more than one problem line.",
    1.89 +    /* 1*/    "wrong number of parameters in the problem line.",
    1.90 +    /* 2*/    "it is not a Max Flow problem line.",
    1.91 +    /* 3*/    "bad value of a parameter in the problem line.",
    1.92 +    /* 4*/    "can't obtain enough memory to solve this problem.",
    1.93 +    /* 5*/    "more than one line with the problem name.",
    1.94 +    /* 6*/    "can't read problem name.",
    1.95 +    /* 7*/    "problem description must be before node description.",
    1.96 +    /* 8*/    "this parser doesn't support multiply sources and sinks.",
    1.97 +    /* 9*/    "wrong number of parameters in the node line.",
    1.98 +    /*10*/    "wrong value of parameters in the node line.",
    1.99 +    /*11*/    " ",
   1.100 +    /*12*/    "source and sink descriptions must be before arc descriptions.",
   1.101 +    /*13*/    "too many arcs in the input.",
   1.102 +    /*14*/    "wrong number of parameters in the arc line.",
   1.103 +    /*15*/    "wrong value of parameters in the arc line.",
   1.104 +    /*16*/    "unknown line type in the input.",
   1.105 +    /*17*/    "reading error.",
   1.106 +    /*18*/    "not enough arcs in the input.",
   1.107 +    /*19*/    "source or sink doesn't have incident arcs.",
   1.108 +    /*20*/    "can't read anything from the input file."
   1.109 +  };
   1.110 +  /* --------------------------------------------------------------- */
   1.111 +
   1.112 +  /* The main loop:
   1.113 +     -  reads the line of the input,
   1.114 +     -  analyses its type,
   1.115 +     -  checks correctness of parameters,
   1.116 +     -  puts data to the arrays,
   1.117 +     -  does service functions
   1.118 +  */
   1.119 +
   1.120 +  while (std::getline(std::cin, in_line)) {
   1.121 +    ++no_lines;
   1.122 +
   1.123 +    switch (in_line[0]) {
   1.124 +    case 'c':                  /* skip lines with comments */
   1.125 +    case '\n':                 /* skip empty lines   */
   1.126 +    case '\0':                 /* skip empty lines at the end of file */
   1.127 +      break;
   1.128 +      
   1.129 +    case 'p':                  /* problem description      */
   1.130 +      if ( no_plines > 0 )
   1.131 +        /* more than one problem line */
   1.132 +        { err_no = EN1 ; goto error; }
   1.133 +      
   1.134 +      no_plines = 1;
   1.135 +      
   1.136 +      if (
   1.137 +          /* reading problem line: type of problem, no of nodes, no of arcs */
   1.138 +          sscanf ( in_line.c_str(), "%*c %3s %ld %ld", pr_type, &n, &m )
   1.139 +          != P_FIELDS
   1.140 +          )
   1.141 +        /*wrong number of parameters in the problem line*/
   1.142 +        { err_no = EN2; goto error; }
   1.143 +      
   1.144 +      if ( strcmp ( pr_type, PROBLEM_TYPE ) )
   1.145 +        /*wrong problem type*/
   1.146 +        { err_no = EN3; goto error; }
   1.147 +      
   1.148 +      if ( n <= 0  || m <= 0 )
   1.149 +        /*wrong value of no of arcs or nodes*/
   1.150 +        { err_no = EN4; goto error; }
   1.151 +
   1.152 +      {
   1.153 +        for (long vi = 0; vi < n; ++vi)
   1.154 +          verts.push_back(add_vertex(g));
   1.155 +      }
   1.156 +      break;
   1.157 +      
   1.158 +    case 'n':                    /* source(s) description */
   1.159 +      if ( no_plines == 0 )
   1.160 +        /* there was not problem line above */
   1.161 +        { err_no = EN8; goto error; }
   1.162 +      
   1.163 +      /* reading source  or sink */
   1.164 +      k = sscanf ( in_line.c_str(),"%*c %ld %c", &i, &nd );
   1.165 +      --i; // index from 0
   1.166 +      if ( k < NODE_FIELDS )
   1.167 +        /* node line is incorrect */
   1.168 +        { err_no = EN11; goto error; }
   1.169 +      
   1.170 +      if ( i < 0 || i > n )
   1.171 +        /* wrong value of node */
   1.172 +        { err_no = EN12; goto error; }
   1.173 +      
   1.174 +      switch (nd) {
   1.175 +      case 's':  /* source line */
   1.176 +        
   1.177 +        if ( no_nslines != 0)
   1.178 +          /* more than one source line */ 
   1.179 +          { err_no = EN9; goto error; }
   1.180 +        
   1.181 +        no_nslines = 1;
   1.182 +        src = verts[i];
   1.183 +        break;
   1.184 +        
   1.185 +      case 't':  /* sink line */
   1.186 +        
   1.187 +        if ( no_nklines != 0)
   1.188 +          /* more than one sink line */
   1.189 +          { err_no = EN9; goto error; }
   1.190 +        
   1.191 +        no_nklines = 1;
   1.192 +        sink = verts[i];
   1.193 +        break;
   1.194 +        
   1.195 +      default:
   1.196 +        /* wrong type of node-line */
   1.197 +        err_no = EN12; goto error; 
   1.198 +      }
   1.199 +      break;
   1.200 +      
   1.201 +    case 'a':                    /* arc description */
   1.202 +      if ( no_nslines == 0 || no_nklines == 0 ) 
   1.203 +        /* there was not source and sink description above */
   1.204 +        { err_no = EN14; goto error; }
   1.205 +      
   1.206 +      if ( no_alines >= m )
   1.207 +        /*too many arcs on input*/
   1.208 +        { err_no = EN16; goto error; }
   1.209 +      
   1.210 +      if (
   1.211 +          /* reading an arc description */
   1.212 +          sscanf ( in_line.c_str(),"%*c %ld %ld %ld",
   1.213 +                   &tail, &head, &cap )
   1.214 +          != ARC_FIELDS
   1.215 +          ) 
   1.216 +        /* arc description is not correct */
   1.217 +        { err_no = EN15; goto error; }
   1.218 +
   1.219 +      --tail; // index from 0, not 1
   1.220 +      --head;
   1.221 +      if ( tail < 0  ||  tail > n  ||
   1.222 +           head < 0  ||  head > n  
   1.223 +           )
   1.224 +        /* wrong value of nodes */
   1.225 +        { err_no = EN17; goto error; }
   1.226 +
   1.227 +      {      
   1.228 +        edge_descriptor e1, e2; 
   1.229 +        bool in1, in2;
   1.230 +        tie(e1, in1) = add_edge(verts[tail], verts[head], g);
   1.231 +        tie(e2, in2) = add_edge(verts[head], verts[tail], g);
   1.232 +        if (!in1 || !in2) {
   1.233 +          std::cerr << "unable to add edge (" << head << "," << tail << ")" 
   1.234 +                    << std::endl;
   1.235 +          return -1;
   1.236 +        }
   1.237 +        capacity[e1] = cap;
   1.238 +        capacity[e2] = 0;
   1.239 +        reverse_edge[e1] = e2;
   1.240 +        reverse_edge[e2] = e1;
   1.241 +      }
   1.242 +      ++no_alines;
   1.243 +      break;
   1.244 +      
   1.245 +    default:
   1.246 +      /* unknown type of line */
   1.247 +      err_no = EN18; goto error;
   1.248 +      
   1.249 +    } /* end of switch */
   1.250 +  }     /* end of input loop */
   1.251 +  
   1.252 +  /* ----- all is red  or  error while reading ----- */ 
   1.253 +  
   1.254 +  if ( feof (stdin) == 0 ) /* reading error */
   1.255 +    { err_no=EN21; goto error; } 
   1.256 +  
   1.257 +  if ( no_lines == 0 ) /* empty input */
   1.258 +    { err_no = EN22; goto error; } 
   1.259 +  
   1.260 +  if ( no_alines < m ) /* not enough arcs */
   1.261 +    { err_no = EN19; goto error; } 
   1.262 +  
   1.263 +  if ( out_degree(src, g) == 0 || out_degree(sink, g) == 0  ) 
   1.264 +    /* no arc goes out of the source */
   1.265 +    { err_no = EN20; goto error; }
   1.266 +  
   1.267 +  /* Thanks God! all is done */
   1.268 +  return (0);
   1.269 +  
   1.270 +  /* ---------------------------------- */
   1.271 + error:  /* error found reading input */
   1.272 +  
   1.273 +  printf ( "\nline %ld of input - %s\n", 
   1.274 +           no_lines, err_message[err_no] );
   1.275 +  
   1.276 +  exit (1);
   1.277 +  return (0); /* to avoid warning */
   1.278 +}
   1.279 +/* --------------------   end of parser  -------------------*/
   1.280 +
   1.281 +} // namespace boost