371 lines
12 KiB
C++
371 lines
12 KiB
C++
|
//=======================================================================
|
||
|
|
// 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.
|
||
|
|
This works, but could use some polishing.
|
||
|
|
*/
|
||
|
|
|
||
|
|
/* ----------------------------------------------------------------- */
|
||
|
|
|
||
|
|
#ifndef BOOST_GRAPH_READ_DIMACS_HPP
|
||
|
|
#define BOOST_GRAPH_READ_DIMACS_HPP
|
||
|
|
|
||
|
|
#include <vector>
|
||
|
|
#include <iostream>
|
||
|
|
#include <string>
|
||
|
|
#include <cstdio>
|
||
|
|
#include <cstring>
|
||
|
|
#include <cstdlib>
|
||
|
|
|
||
|
|
#include <boost/graph/graph_traits.hpp>
|
||
|
|
|
||
|
|
namespace boost
|
||
|
|
{
|
||
|
|
|
||
|
|
namespace detail
|
||
|
|
{
|
||
|
|
|
||
|
|
template < class Graph, class CapacityMap, class ReverseEdgeMap >
|
||
|
|
int read_dimacs_max_flow_internal(Graph& g, CapacityMap capacity,
|
||
|
|
ReverseEdgeMap reverse_edge,
|
||
|
|
typename graph_traits< Graph >::vertex_descriptor& src,
|
||
|
|
typename graph_traits< Graph >::vertex_descriptor& sink,
|
||
|
|
std::istream& in, bool require_source_and_sink,
|
||
|
|
const std::string& problem_type)
|
||
|
|
{
|
||
|
|
// 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 */
|
||
|
|
|
||
|
|
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[4]; /* 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 const 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(in, 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 */
|
||
|
|
std::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 (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 = std::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 (require_source_and_sink
|
||
|
|
&& (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 */
|
||
|
|
std::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;
|
||
|
|
boost::tie(e1, in1) = add_edge(verts[tail], verts[head], g);
|
||
|
|
boost::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 (in.eof() == 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 (require_source_and_sink
|
||
|
|
&& (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 */
|
||
|
|
|
||
|
|
std::printf(
|
||
|
|
"\nline %ld of input - %s\n", no_lines, err_message[err_no]);
|
||
|
|
|
||
|
|
return -1;
|
||
|
|
}
|
||
|
|
/* -------------------- end of parser -------------------*/
|
||
|
|
|
||
|
|
} // namespace detail
|
||
|
|
|
||
|
|
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,
|
||
|
|
std::istream& in = std::cin)
|
||
|
|
{
|
||
|
|
return detail::read_dimacs_max_flow_internal(
|
||
|
|
g, capacity, reverse_edge, src, sink, in, true, "max");
|
||
|
|
}
|
||
|
|
|
||
|
|
template < class Graph, class CapacityMap, class ReverseEdgeMap >
|
||
|
|
int read_dimacs_min_cut(Graph& g, CapacityMap capacity,
|
||
|
|
ReverseEdgeMap reverse_edge, std::istream& in = std::cin)
|
||
|
|
{
|
||
|
|
typename graph_traits< Graph >::vertex_descriptor dummy_src,
|
||
|
|
dummy_sink; // Not filled in
|
||
|
|
return detail::read_dimacs_max_flow_internal(
|
||
|
|
g, capacity, reverse_edge, dummy_src, dummy_sink, in, false, "cut");
|
||
|
|
}
|
||
|
|
|
||
|
|
} // namespace boost
|
||
|
|
|
||
|
|
#endif // BOOST_GRAPH_READ_DIMACS_HPP
|