williamr@2: //======================================================================= williamr@2: // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. williamr@2: // Authors: Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee williamr@2: // williamr@2: // Distributed under the Boost Software License, Version 1.0. (See williamr@2: // accompanying file LICENSE_1_0.txt or copy at williamr@2: // http://www.boost.org/LICENSE_1_0.txt) williamr@2: //======================================================================= williamr@2: williamr@2: /* williamr@2: Reads maximal flow problem in extended DIMACS format. williamr@2: williamr@2: Reads from stdin. williamr@2: williamr@2: This works, but could use some polishing. williamr@2: */ williamr@2: williamr@2: /* ----------------------------------------------------------------- */ williamr@2: williamr@2: #include williamr@2: #include williamr@2: williamr@2: namespace boost { williamr@2: williamr@2: template williamr@2: int read_dimacs_max_flow(Graph& g, williamr@2: CapacityMap capacity, williamr@2: ReverseEdgeMap reverse_edge, williamr@2: typename graph_traits::vertex_descriptor& src, williamr@2: typename graph_traits::vertex_descriptor& sink) williamr@2: { williamr@2: // const int MAXLINE = 100; /* max line length in the input file */ williamr@2: const int ARC_FIELDS = 3; /* no of fields in arc line */ williamr@2: const int NODE_FIELDS = 2; /* no of fields in node line */ williamr@2: const int P_FIELDS = 3; /* no of fields in problem line */ williamr@2: const char* PROBLEM_TYPE = "max"; /* name of problem type*/ williamr@2: williamr@2: typedef typename graph_traits::vertices_size_type vertices_size_type; williamr@2: typedef typename graph_traits::vertex_descriptor vertex_descriptor; williamr@2: typedef typename graph_traits::edge_descriptor edge_descriptor; williamr@2: williamr@2: std::vector verts; williamr@2: williamr@2: long m, n, /* number of edges and nodes */ williamr@2: i, head, tail, cap; williamr@2: williamr@2: long no_lines=0, /* no of current input line */ williamr@2: no_plines=0, /* no of problem-lines */ williamr@2: no_nslines=0, /* no of node-source-lines */ williamr@2: no_nklines=0, /* no of node-source-lines */ williamr@2: no_alines=0; /* no of arc-lines */ williamr@2: williamr@2: std::string in_line; /* for reading input line */ williamr@2: char pr_type[3]; /* for reading type of the problem */ williamr@2: char nd; /* source (s) or sink (t) */ williamr@2: williamr@2: int k, /* temporary */ williamr@2: err_no; /* no of detected error */ williamr@2: williamr@2: /* -------------- error numbers & error messages ---------------- */ williamr@2: const int EN1 = 0; williamr@2: const int EN2 = 1; williamr@2: const int EN3 = 2; williamr@2: const int EN4 = 3; williamr@2: // const int EN6 = 4; williamr@2: // const int EN10 = 5; williamr@2: // const int EN7 = 6; williamr@2: const int EN8 = 7; williamr@2: const int EN9 = 8; williamr@2: const int EN11 = 9; williamr@2: const int EN12 = 10; williamr@2: // const int EN13 = 11; williamr@2: const int EN14 = 12; williamr@2: const int EN16 = 13; williamr@2: const int EN15 = 14; williamr@2: const int EN17 = 15; williamr@2: const int EN18 = 16; williamr@2: const int EN21 = 17; williamr@2: const int EN19 = 18; williamr@2: const int EN20 = 19; williamr@2: const int EN22 = 20; williamr@2: williamr@2: static char *err_message[] = williamr@2: { williamr@2: /* 0*/ "more than one problem line.", williamr@2: /* 1*/ "wrong number of parameters in the problem line.", williamr@2: /* 2*/ "it is not a Max Flow problem line.", williamr@2: /* 3*/ "bad value of a parameter in the problem line.", williamr@2: /* 4*/ "can't obtain enough memory to solve this problem.", williamr@2: /* 5*/ "more than one line with the problem name.", williamr@2: /* 6*/ "can't read problem name.", williamr@2: /* 7*/ "problem description must be before node description.", williamr@2: /* 8*/ "this parser doesn't support multiply sources and sinks.", williamr@2: /* 9*/ "wrong number of parameters in the node line.", williamr@2: /*10*/ "wrong value of parameters in the node line.", williamr@2: /*11*/ " ", williamr@2: /*12*/ "source and sink descriptions must be before arc descriptions.", williamr@2: /*13*/ "too many arcs in the input.", williamr@2: /*14*/ "wrong number of parameters in the arc line.", williamr@2: /*15*/ "wrong value of parameters in the arc line.", williamr@2: /*16*/ "unknown line type in the input.", williamr@2: /*17*/ "reading error.", williamr@2: /*18*/ "not enough arcs in the input.", williamr@2: /*19*/ "source or sink doesn't have incident arcs.", williamr@2: /*20*/ "can't read anything from the input file." williamr@2: }; williamr@2: /* --------------------------------------------------------------- */ williamr@2: williamr@2: /* The main loop: williamr@2: - reads the line of the input, williamr@2: - analyses its type, williamr@2: - checks correctness of parameters, williamr@2: - puts data to the arrays, williamr@2: - does service functions williamr@2: */ williamr@2: williamr@2: while (std::getline(std::cin, in_line)) { williamr@2: ++no_lines; williamr@2: williamr@2: switch (in_line[0]) { williamr@2: case 'c': /* skip lines with comments */ williamr@2: case '\n': /* skip empty lines */ williamr@2: case '\0': /* skip empty lines at the end of file */ williamr@2: break; williamr@2: williamr@2: case 'p': /* problem description */ williamr@2: if ( no_plines > 0 ) williamr@2: /* more than one problem line */ williamr@2: { err_no = EN1 ; goto error; } williamr@2: williamr@2: no_plines = 1; williamr@2: williamr@2: if ( williamr@2: /* reading problem line: type of problem, no of nodes, no of arcs */ williamr@2: sscanf ( in_line.c_str(), "%*c %3s %ld %ld", pr_type, &n, &m ) williamr@2: != P_FIELDS williamr@2: ) williamr@2: /*wrong number of parameters in the problem line*/ williamr@2: { err_no = EN2; goto error; } williamr@2: williamr@2: if ( strcmp ( pr_type, PROBLEM_TYPE ) ) williamr@2: /*wrong problem type*/ williamr@2: { err_no = EN3; goto error; } williamr@2: williamr@2: if ( n <= 0 || m <= 0 ) williamr@2: /*wrong value of no of arcs or nodes*/ williamr@2: { err_no = EN4; goto error; } williamr@2: williamr@2: { williamr@2: for (long vi = 0; vi < n; ++vi) williamr@2: verts.push_back(add_vertex(g)); williamr@2: } williamr@2: break; williamr@2: williamr@2: case 'n': /* source(s) description */ williamr@2: if ( no_plines == 0 ) williamr@2: /* there was not problem line above */ williamr@2: { err_no = EN8; goto error; } williamr@2: williamr@2: /* reading source or sink */ williamr@2: k = sscanf ( in_line.c_str(),"%*c %ld %c", &i, &nd ); williamr@2: --i; // index from 0 williamr@2: if ( k < NODE_FIELDS ) williamr@2: /* node line is incorrect */ williamr@2: { err_no = EN11; goto error; } williamr@2: williamr@2: if ( i < 0 || i > n ) williamr@2: /* wrong value of node */ williamr@2: { err_no = EN12; goto error; } williamr@2: williamr@2: switch (nd) { williamr@2: case 's': /* source line */ williamr@2: williamr@2: if ( no_nslines != 0) williamr@2: /* more than one source line */ williamr@2: { err_no = EN9; goto error; } williamr@2: williamr@2: no_nslines = 1; williamr@2: src = verts[i]; williamr@2: break; williamr@2: williamr@2: case 't': /* sink line */ williamr@2: williamr@2: if ( no_nklines != 0) williamr@2: /* more than one sink line */ williamr@2: { err_no = EN9; goto error; } williamr@2: williamr@2: no_nklines = 1; williamr@2: sink = verts[i]; williamr@2: break; williamr@2: williamr@2: default: williamr@2: /* wrong type of node-line */ williamr@2: err_no = EN12; goto error; williamr@2: } williamr@2: break; williamr@2: williamr@2: case 'a': /* arc description */ williamr@2: if ( no_nslines == 0 || no_nklines == 0 ) williamr@2: /* there was not source and sink description above */ williamr@2: { err_no = EN14; goto error; } williamr@2: williamr@2: if ( no_alines >= m ) williamr@2: /*too many arcs on input*/ williamr@2: { err_no = EN16; goto error; } williamr@2: williamr@2: if ( williamr@2: /* reading an arc description */ williamr@2: sscanf ( in_line.c_str(),"%*c %ld %ld %ld", williamr@2: &tail, &head, &cap ) williamr@2: != ARC_FIELDS williamr@2: ) williamr@2: /* arc description is not correct */ williamr@2: { err_no = EN15; goto error; } williamr@2: williamr@2: --tail; // index from 0, not 1 williamr@2: --head; williamr@2: if ( tail < 0 || tail > n || williamr@2: head < 0 || head > n williamr@2: ) williamr@2: /* wrong value of nodes */ williamr@2: { err_no = EN17; goto error; } williamr@2: williamr@2: { williamr@2: edge_descriptor e1, e2; williamr@2: bool in1, in2; williamr@2: tie(e1, in1) = add_edge(verts[tail], verts[head], g); williamr@2: tie(e2, in2) = add_edge(verts[head], verts[tail], g); williamr@2: if (!in1 || !in2) { williamr@2: std::cerr << "unable to add edge (" << head << "," << tail << ")" williamr@2: << std::endl; williamr@2: return -1; williamr@2: } williamr@2: capacity[e1] = cap; williamr@2: capacity[e2] = 0; williamr@2: reverse_edge[e1] = e2; williamr@2: reverse_edge[e2] = e1; williamr@2: } williamr@2: ++no_alines; williamr@2: break; williamr@2: williamr@2: default: williamr@2: /* unknown type of line */ williamr@2: err_no = EN18; goto error; williamr@2: williamr@2: } /* end of switch */ williamr@2: } /* end of input loop */ williamr@2: williamr@2: /* ----- all is red or error while reading ----- */ williamr@2: williamr@2: if ( feof (stdin) == 0 ) /* reading error */ williamr@2: { err_no=EN21; goto error; } williamr@2: williamr@2: if ( no_lines == 0 ) /* empty input */ williamr@2: { err_no = EN22; goto error; } williamr@2: williamr@2: if ( no_alines < m ) /* not enough arcs */ williamr@2: { err_no = EN19; goto error; } williamr@2: williamr@2: if ( out_degree(src, g) == 0 || out_degree(sink, g) == 0 ) williamr@2: /* no arc goes out of the source */ williamr@2: { err_no = EN20; goto error; } williamr@2: williamr@2: /* Thanks God! all is done */ williamr@2: return (0); williamr@2: williamr@2: /* ---------------------------------- */ williamr@2: error: /* error found reading input */ williamr@2: williamr@2: printf ( "\nline %ld of input - %s\n", williamr@2: no_lines, err_message[err_no] ); williamr@2: williamr@2: exit (1); williamr@2: return (0); /* to avoid warning */ williamr@2: } williamr@2: /* -------------------- end of parser -------------------*/ williamr@2: williamr@2: } // namespace boost