Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / read_dimacs.hpp
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
23 namespace boost {
24
25 template <class Graph, class CapacityMap, class ReverseEdgeMap>
26 int 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