|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r49563 - in trunk: boost/graph libs/graph/test
From: asutton_at_[hidden]
Date: 2008-11-03 10:50:29
Author: asutton
Date: 2008-11-03 10:50:29 EST (Mon, 03 Nov 2008)
New Revision: 49563
URL: http://svn.boost.org/trac/boost/changeset/49563
Log:
Include correct headers for read_dimacs.hpp, fixing #2460. Added a compile
test (just a stub for now) to ensuer that the file will compile without
any additional includes.
Added:
trunk/libs/graph/test/dimacs.cpp (contents, props changed)
Text files modified:
trunk/boost/graph/read_dimacs.hpp | 111 ++++++++++++++++++++-------------------
trunk/libs/graph/test/Jamfile.v2 | 1
2 files changed, 58 insertions(+), 54 deletions(-)
Modified: trunk/boost/graph/read_dimacs.hpp
==============================================================================
--- trunk/boost/graph/read_dimacs.hpp (original)
+++ trunk/boost/graph/read_dimacs.hpp 2008-11-03 10:50:29 EST (Mon, 03 Nov 2008)
@@ -9,24 +9,27 @@
/*
Reads maximal flow problem in extended DIMACS format.
- This works, but could use some polishing.
+ This works, but could use some polishing.
*/
/* ----------------------------------------------------------------- */
#include <vector>
-#include <istream>
-#include <stdio.h>
+#include <iostream>
+#include <cstdio>
+#include <cstring>
+
+#include <boost/graph/graph_traits.hpp>
namespace boost {
template <class Graph, class CapacityMap, class ReverseEdgeMap>
int read_dimacs_max_flow(Graph& g,
- CapacityMap capacity,
+ CapacityMap capacity,
ReverseEdgeMap reverse_edge,
typename graph_traits<Graph>::vertex_descriptor& src,
typename graph_traits<Graph>::vertex_descriptor& sink,
- std::istream& in=std::cin)
+ std::istream& in = std::cin)
{
// const int MAXLINE = 100; /* max line length in the input file */
const int ARC_FIELDS = 3; /* no of fields in arc line */
@@ -37,7 +40,7 @@
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 */
@@ -48,11 +51,11 @@
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 */
@@ -78,9 +81,9 @@
const int EN19 = 18;
const int EN20 = 19;
const int EN22 = 20;
-
- static char *err_message[] =
- {
+
+ 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.",
@@ -121,14 +124,14 @@
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 )
@@ -136,11 +139,11 @@
)
/*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; }
@@ -150,83 +153,83 @@
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 */
+ /* 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;
+ err_no = EN12; goto error;
}
break;
-
+
case 'a': /* arc description */
- if ( no_nslines == 0 || no_nklines == 0 )
+ 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
+ head < 0 || head > n
)
/* wrong value of nodes */
{ err_no = EN17; goto error; }
- {
- edge_descriptor e1, e2;
+ {
+ 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::cerr << "unable to add edge (" << head << "," << tail << ")"
<< std::endl;
return -1;
}
@@ -237,38 +240,38 @@
}
++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 ----- */
-
+
+ /* ----- all is red or error while reading ----- */
+
if ( feof (stdin) == 0 ) /* reading error */
- { err_no=EN21; goto error; }
-
+ { err_no=EN21; goto error; }
+
if ( no_lines == 0 ) /* empty input */
- { err_no = EN22; goto error; }
-
+ { 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 )
+ { 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",
+
+ printf ( "\nline %ld of input - %s\n",
no_lines, err_message[err_no] );
-
+
exit (1);
return (0); /* to avoid warning */
}
Modified: trunk/libs/graph/test/Jamfile.v2
==============================================================================
--- trunk/libs/graph/test/Jamfile.v2 (original)
+++ trunk/libs/graph/test/Jamfile.v2 2008-11-03 10:50:29 EST (Mon, 03 Nov 2008)
@@ -116,6 +116,7 @@
[ run r_c_shortest_paths_test.cpp ]
[ run is_straight_line_draw_test.cpp ]
[ run metric_tsp_approx.cpp : metric_tsp_approx.txt ]
+ [ compile dimacs.cpp ]
$(optional_tests)
;
Added: trunk/libs/graph/test/dimacs.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/test/dimacs.cpp 2008-11-03 10:50:29 EST (Mon, 03 Nov 2008)
@@ -0,0 +1,11 @@
+
+#include <boost/graph/read_dimacs.hpp>
+#include <boost/graph/write_dimacs.hpp>
+
+// This is obviously just a stub test. It's currently only used as a compile
+// check to make sure that the includes are appropriate.
+
+int main()
+{
+ return 0;
+}
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk