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