--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/ossrv_pub/boost_apis/boost/graph/read_dimacs.hpp Tue Feb 02 02:01:42 2010 +0200
@@ -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 <vector>
+#include <stdio.h>
+
+namespace boost {
+
+template <class Graph, class CapacityMap, class ReverseEdgeMap>
+int read_dimacs_max_flow(Graph& g,
+ CapacityMap capacity,
+ ReverseEdgeMap reverse_edge,
+ typename graph_traits<Graph>::vertex_descriptor& src,
+ typename graph_traits<Graph>::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<Graph>::vertices_size_type vertices_size_type;
+ typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
+ typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
+
+ std::vector<vertex_descriptor> 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