source: NonGTP/Boost/boost/graph/read_dimacs.hpp @ 857

Revision 857, 9.1 KB checked in by igarcia, 19 years ago (diff)
Line 
1//=======================================================================
2// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
3// Authors: Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee
4//
5// Distributed under the Boost Software License, Version 1.0. (See
6// accompanying file LICENSE_1_0.txt or copy at
7// http://www.boost.org/LICENSE_1_0.txt)
8//=======================================================================
9
10/*
11  Reads maximal flow problem in extended DIMACS format.
12 
13  Reads from stdin.
14
15  This works, but could use some polishing.
16*/
17
18/* ----------------------------------------------------------------- */
19
20#include <vector>
21#include <stdio.h>
22
23namespace boost {
24
25template <class Graph, class CapacityMap, class ReverseEdgeMap>
26int read_dimacs_max_flow(Graph& g,
27                         CapacityMap capacity,
28                         ReverseEdgeMap reverse_edge,
29                         typename graph_traits<Graph>::vertex_descriptor& src,
30                         typename graph_traits<Graph>::vertex_descriptor& sink)
31{
32  //  const int MAXLINE = 100;      /* max line length in the input file */
33  const int ARC_FIELDS = 3;     /* no of fields in arc line  */
34  const int NODE_FIELDS = 2;    /* no of fields in node line  */
35  const int P_FIELDS = 3;       /* no of fields in problem line */
36  const char* PROBLEM_TYPE = "max"; /* name of problem type*/
37
38  typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
39  typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
40  typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
41 
42  std::vector<vertex_descriptor> verts;
43
44  long m, n,                    /*  number of edges and nodes */
45    i, head, tail, cap;
46
47  long no_lines=0,              /* no of current input line */
48    no_plines=0,                /* no of problem-lines */
49    no_nslines=0,               /* no of node-source-lines */
50    no_nklines=0,               /* no of node-source-lines */
51    no_alines=0;                /* no of arc-lines */
52 
53  std::string in_line;          /* for reading input line */
54  char pr_type[3];              /* for reading type of the problem */
55  char nd;                      /* source (s) or sink (t) */
56 
57  int k,                        /* temporary */
58    err_no;                     /* no of detected error */
59
60  /* -------------- error numbers & error messages ---------------- */
61  const int EN1   = 0;
62  const int EN2   = 1;
63  const int EN3   = 2;
64  const int EN4   = 3;
65  //  const int EN6   = 4;
66  //  const int EN10  = 5;
67  //  const int EN7   = 6;
68  const int EN8   = 7;
69  const int EN9   = 8;
70  const int EN11  = 9;
71  const int EN12 = 10;
72  //  const int EN13 = 11;
73  const int EN14 = 12;
74  const int EN16 = 13;
75  const int EN15 = 14;
76  const int EN17 = 15;
77  const int EN18 = 16;
78  const int EN21 = 17;
79  const int EN19 = 18;
80  const int EN20 = 19;
81  const int EN22 = 20;
82 
83  static char *err_message[] =
84  {
85    /* 0*/    "more than one problem line.",
86    /* 1*/    "wrong number of parameters in the problem line.",
87    /* 2*/    "it is not a Max Flow problem line.",
88    /* 3*/    "bad value of a parameter in the problem line.",
89    /* 4*/    "can't obtain enough memory to solve this problem.",
90    /* 5*/    "more than one line with the problem name.",
91    /* 6*/    "can't read problem name.",
92    /* 7*/    "problem description must be before node description.",
93    /* 8*/    "this parser doesn't support multiply sources and sinks.",
94    /* 9*/    "wrong number of parameters in the node line.",
95    /*10*/    "wrong value of parameters in the node line.",
96    /*11*/    " ",
97    /*12*/    "source and sink descriptions must be before arc descriptions.",
98    /*13*/    "too many arcs in the input.",
99    /*14*/    "wrong number of parameters in the arc line.",
100    /*15*/    "wrong value of parameters in the arc line.",
101    /*16*/    "unknown line type in the input.",
102    /*17*/    "reading error.",
103    /*18*/    "not enough arcs in the input.",
104    /*19*/    "source or sink doesn't have incident arcs.",
105    /*20*/    "can't read anything from the input file."
106  };
107  /* --------------------------------------------------------------- */
108
109  /* The main loop:
110     -  reads the line of the input,
111     -  analyses its type,
112     -  checks correctness of parameters,
113     -  puts data to the arrays,
114     -  does service functions
115  */
116
117  while (std::getline(std::cin, in_line)) {
118    ++no_lines;
119
120    switch (in_line[0]) {
121    case 'c':                  /* skip lines with comments */
122    case '\n':                 /* skip empty lines   */
123    case '\0':                 /* skip empty lines at the end of file */
124      break;
125     
126    case 'p':                  /* problem description      */
127      if ( no_plines > 0 )
128        /* more than one problem line */
129        { err_no = EN1 ; goto error; }
130     
131      no_plines = 1;
132     
133      if (
134          /* reading problem line: type of problem, no of nodes, no of arcs */
135          sscanf ( in_line.c_str(), "%*c %3s %ld %ld", pr_type, &n, &m )
136          != P_FIELDS
137          )
138        /*wrong number of parameters in the problem line*/
139        { err_no = EN2; goto error; }
140     
141      if ( strcmp ( pr_type, PROBLEM_TYPE ) )
142        /*wrong problem type*/
143        { err_no = EN3; goto error; }
144     
145      if ( n <= 0  || m <= 0 )
146        /*wrong value of no of arcs or nodes*/
147        { err_no = EN4; goto error; }
148
149      {
150        for (long vi = 0; vi < n; ++vi)
151          verts.push_back(add_vertex(g));
152      }
153      break;
154     
155    case 'n':                    /* source(s) description */
156      if ( no_plines == 0 )
157        /* there was not problem line above */
158        { err_no = EN8; goto error; }
159     
160      /* reading source  or sink */
161      k = sscanf ( in_line.c_str(),"%*c %ld %c", &i, &nd );
162      --i; // index from 0
163      if ( k < NODE_FIELDS )
164        /* node line is incorrect */
165        { err_no = EN11; goto error; }
166     
167      if ( i < 0 || i > n )
168        /* wrong value of node */
169        { err_no = EN12; goto error; }
170     
171      switch (nd) {
172      case 's':  /* source line */
173       
174        if ( no_nslines != 0)
175          /* more than one source line */
176          { err_no = EN9; goto error; }
177       
178        no_nslines = 1;
179        src = verts[i];
180        break;
181       
182      case 't':  /* sink line */
183       
184        if ( no_nklines != 0)
185          /* more than one sink line */
186          { err_no = EN9; goto error; }
187       
188        no_nklines = 1;
189        sink = verts[i];
190        break;
191       
192      default:
193        /* wrong type of node-line */
194        err_no = EN12; goto error;
195      }
196      break;
197     
198    case 'a':                    /* arc description */
199      if ( no_nslines == 0 || no_nklines == 0 )
200        /* there was not source and sink description above */
201        { err_no = EN14; goto error; }
202     
203      if ( no_alines >= m )
204        /*too many arcs on input*/
205        { err_no = EN16; goto error; }
206     
207      if (
208          /* reading an arc description */
209          sscanf ( in_line.c_str(),"%*c %ld %ld %ld",
210                   &tail, &head, &cap )
211          != ARC_FIELDS
212          )
213        /* arc description is not correct */
214        { err_no = EN15; goto error; }
215
216      --tail; // index from 0, not 1
217      --head;
218      if ( tail < 0  ||  tail > n  ||
219           head < 0  ||  head > n 
220           )
221        /* wrong value of nodes */
222        { err_no = EN17; goto error; }
223
224      {     
225        edge_descriptor e1, e2;
226        bool in1, in2;
227        tie(e1, in1) = add_edge(verts[tail], verts[head], g);
228        tie(e2, in2) = add_edge(verts[head], verts[tail], g);
229        if (!in1 || !in2) {
230          std::cerr << "unable to add edge (" << head << "," << tail << ")"
231                    << std::endl;
232          return -1;
233        }
234        capacity[e1] = cap;
235        capacity[e2] = 0;
236        reverse_edge[e1] = e2;
237        reverse_edge[e2] = e1;
238      }
239      ++no_alines;
240      break;
241     
242    default:
243      /* unknown type of line */
244      err_no = EN18; goto error;
245     
246    } /* end of switch */
247  }     /* end of input loop */
248 
249  /* ----- all is red  or  error while reading ----- */
250 
251  if ( feof (stdin) == 0 ) /* reading error */
252    { err_no=EN21; goto error; }
253 
254  if ( no_lines == 0 ) /* empty input */
255    { err_no = EN22; goto error; }
256 
257  if ( no_alines < m ) /* not enough arcs */
258    { err_no = EN19; goto error; }
259 
260  if ( out_degree(src, g) == 0 || out_degree(sink, g) == 0  )
261    /* no arc goes out of the source */
262    { err_no = EN20; goto error; }
263 
264  /* Thanks God! all is done */
265  return (0);
266 
267  /* ---------------------------------- */
268 error:  /* error found reading input */
269 
270  printf ( "\nline %ld of input - %s\n",
271           no_lines, err_message[err_no] );
272 
273  exit (1);
274  return (0); /* to avoid warning */
275}
276/* --------------------   end of parser  -------------------*/
277
278} // namespace boost
Note: See TracBrowser for help on using the repository browser.