File: read_dimacs.hpp

package info (click to toggle)
boost1.62 1.62.0+dfsg-4
  • links: PTS, VCS
  • area: main
  • in suites: stretch
  • size: 686,420 kB
  • sloc: cpp: 2,609,004; xml: 972,558; ansic: 53,674; python: 32,437; sh: 8,829; asm: 3,071; cs: 2,121; makefile: 964; perl: 859; yacc: 472; php: 132; ruby: 94; f90: 55; sql: 13; csh: 6
file content (310 lines) | stat: -rw-r--r-- 10,186 bytes parent folder | download | duplicates (13)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
//=======================================================================
// 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