diff -r 666f914201fb -r 2fe1408b6811 epoc32/include/stdapis/boost/graph/read_dimacs.hpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/epoc32/include/stdapis/boost/graph/read_dimacs.hpp Tue Mar 16 16:12:26 2010 +0000 @@ -0,0 +1,278 @@ +//======================================================================= +// 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. + + Reads from stdin. + + This works, but could use some polishing. +*/ + +/* ----------------------------------------------------------------- */ + +#include +#include + +namespace boost { + +template +int read_dimacs_max_flow(Graph& g, + CapacityMap capacity, + ReverseEdgeMap reverse_edge, + typename graph_traits::vertex_descriptor& src, + typename graph_traits::vertex_descriptor& sink) +{ + // 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 */ + const char* PROBLEM_TYPE = "max"; /* name of problem type*/ + + typedef typename graph_traits::vertices_size_type vertices_size_type; + typedef typename graph_traits::vertex_descriptor vertex_descriptor; + typedef typename graph_traits::edge_descriptor edge_descriptor; + + std::vector 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[3]; /* 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 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(std::cin, 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 */ + 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 ( strcmp ( 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 = 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 ( 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 */ + 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; + tie(e1, in1) = add_edge(verts[tail], verts[head], g); + 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 ( feof (stdin) == 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 ( 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 */ + + printf ( "\nline %ld of input - %s\n", + no_lines, err_message[err_no] ); + + exit (1); + return (0); /* to avoid warning */ +} +/* -------------------- end of parser -------------------*/ + +} // namespace boost