townforge/graph
1
0
Fork 0
Code Issues Pull Requests Releases Wiki Activity
cc
graph/include/boost/graph/push_relabel_max_flow.hpp
Jeremiah Willcock 2b2f2d464e Qualified more calls to tie; fixes #6112 
[SVN r75431]
2011-11-10 15:04:27 +00:00

747 lines
28 KiB
C++
Raw Permalink Blame History

//=======================================================================
// Copyright 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)
//=======================================================================
#ifndef BOOST_PUSH_RELABEL_MAX_FLOW_HPP
#define BOOST_PUSH_RELABEL_MAX_FLOW_HPP
#include <boost/config.hpp>
#include <boost/assert.hpp>
#include <vector>
#include <list>
#include <iosfwd>
#include <algorithm> // for std::min and std::max
#include <boost/pending/queue.hpp>
#include <boost/limits.hpp>
#include <boost/graph/graph_concepts.hpp>
#include <boost/graph/named_function_params.hpp>
namespace boost {
namespace detail {
// This implementation is based on Goldberg's
// "On Implementing Push-Relabel Method for the Maximum Flow Problem"
// by B.V. Cherkassky and A.V. Goldberg, IPCO '95, pp. 157--171
// and on the h_prf.c and hi_pr.c code written by the above authors.
// This implements the highest-label version of the push-relabel method
// with the global relabeling and gap relabeling heuristics.
// The terms "rank", "distance", "height" are synonyms in
// Goldberg's implementation, paper and in the CLR. A "layer" is a
// group of vertices with the same distance. The vertices in each
// layer are categorized as active or inactive. An active vertex
// has positive excess flow and its distance is less than n (it is
// not blocked).
template <class Vertex>
struct preflow_layer {
std::list<Vertex> active_vertices;
std::list<Vertex> inactive_vertices;
};
template <class Graph,
class EdgeCapacityMap, // integer value type
class ResidualCapacityEdgeMap,
class ReverseEdgeMap,
class VertexIndexMap, // vertex_descriptor -> integer
class FlowValue>
class push_relabel
{
public:
typedef graph_traits<Graph> Traits;
typedef typename Traits::vertex_descriptor vertex_descriptor;
typedef typename Traits::edge_descriptor edge_descriptor;
typedef typename Traits::vertex_iterator vertex_iterator;
typedef typename Traits::out_edge_iterator out_edge_iterator;
typedef typename Traits::vertices_size_type vertices_size_type;
typedef typename Traits::edges_size_type edges_size_type;
typedef preflow_layer<vertex_descriptor> Layer;
typedef std::vector< Layer > LayerArray;
typedef typename LayerArray::iterator layer_iterator;
typedef typename LayerArray::size_type distance_size_type;
typedef color_traits<default_color_type> ColorTraits;
//=======================================================================
// Some helper predicates
inline bool is_admissible(vertex_descriptor u, vertex_descriptor v) {
return get(distance, u) == get(distance, v) + 1;
}
inline bool is_residual_edge(edge_descriptor a) {
return 0 < get(residual_capacity, a);
}
inline bool is_saturated(edge_descriptor a) {
return get(residual_capacity, a) == 0;
}
//=======================================================================
// Layer List Management Functions
typedef typename std::list<vertex_descriptor>::iterator list_iterator;
void add_to_active_list(vertex_descriptor u, Layer& layer) {
BOOST_USING_STD_MIN();
BOOST_USING_STD_MAX();
layer.active_vertices.push_front(u);
max_active = max BOOST_PREVENT_MACRO_SUBSTITUTION(get(distance, u), max_active);
min_active = min BOOST_PREVENT_MACRO_SUBSTITUTION(get(distance, u), min_active);
layer_list_ptr[u] = layer.active_vertices.begin();
}
void remove_from_active_list(vertex_descriptor u) {
layers[get(distance, u)].active_vertices.erase(layer_list_ptr[u]);
}
void add_to_inactive_list(vertex_descriptor u, Layer& layer) {
layer.inactive_vertices.push_front(u);
layer_list_ptr[u] = layer.inactive_vertices.begin();
}
void remove_from_inactive_list(vertex_descriptor u) {
layers[get(distance, u)].inactive_vertices.erase(layer_list_ptr[u]);
}
//=======================================================================
// initialization
push_relabel(Graph& g_,
EdgeCapacityMap cap,
ResidualCapacityEdgeMap res,
ReverseEdgeMap rev,
vertex_descriptor src_,
vertex_descriptor sink_,
VertexIndexMap idx)
: g(g_), n(num_vertices(g_)), capacity(cap), src(src_), sink(sink_),
index(idx),
excess_flow_data(num_vertices(g_)),
excess_flow(excess_flow_data.begin(), idx),
current_data(num_vertices(g_), out_edges(*vertices(g_).first, g_)),
current(current_data.begin(), idx),
distance_data(num_vertices(g_)),
distance(distance_data.begin(), idx),
color_data(num_vertices(g_)),
color(color_data.begin(), idx),
reverse_edge(rev),
residual_capacity(res),
layers(num_vertices(g_)),
layer_list_ptr_data(num_vertices(g_),
layers.front().inactive_vertices.end()),
layer_list_ptr(layer_list_ptr_data.begin(), idx),
push_count(0), update_count(0), relabel_count(0),
gap_count(0), gap_node_count(0),
work_since_last_update(0)
{
vertex_iterator u_iter, u_end;
// Don't count the reverse edges
edges_size_type m = num_edges(g) / 2;
nm = alpha() * n + m;
// Initialize flow to zero which means initializing
// the residual capacity to equal the capacity.
out_edge_iterator ei, e_end;
for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
for (boost::tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei) {
put(residual_capacity, *ei, get(capacity, *ei));
}
for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) {
vertex_descriptor u = *u_iter;
put(excess_flow, u, 0);
current[u] = out_edges(u, g);
}
bool overflow_detected = false;
FlowValue test_excess = 0;
out_edge_iterator a_iter, a_end;
for (boost::tie(a_iter, a_end) = out_edges(src, g); a_iter != a_end; ++a_iter)
if (target(*a_iter, g) != src)
test_excess += get(residual_capacity, *a_iter);
if (test_excess > (std::numeric_limits<FlowValue>::max)())
overflow_detected = true;
if (overflow_detected)
put(excess_flow, src, (std::numeric_limits<FlowValue>::max)());
else {
put(excess_flow, src, 0);
for (boost::tie(a_iter, a_end) = out_edges(src, g);
a_iter != a_end; ++a_iter) {
edge_descriptor a = *a_iter;
vertex_descriptor tgt = target(a, g);
if (tgt != src) {
++push_count;
FlowValue delta = get(residual_capacity, a);
put(residual_capacity, a, get(residual_capacity, a) - delta);
edge_descriptor rev = get(reverse_edge, a);
put(residual_capacity, rev, get(residual_capacity, rev) + delta);
put(excess_flow, tgt, get(excess_flow, tgt) + delta);
}
}
}
max_distance = num_vertices(g) - 1;
max_active = 0;
min_active = n;
for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) {
vertex_descriptor u = *u_iter;
if (u == sink) {
put(distance, u, 0);
continue;
} else if (u == src && !overflow_detected)
put(distance, u, n);
else
put(distance, u, 1);
if (get(excess_flow, u) > 0)
add_to_active_list(u, layers[1]);
else if (get(distance, u) < n)
add_to_inactive_list(u, layers[1]);
}
} // push_relabel constructor
//=======================================================================
// This is a breadth-first search over the residual graph
// (well, actually the reverse of the residual graph).
// Would be cool to have a graph view adaptor for hiding certain
// edges, like the saturated (non-residual) edges in this case.
// Goldberg's implementation abused "distance" for the coloring.
void global_distance_update()
{
BOOST_USING_STD_MAX();
++update_count;
vertex_iterator u_iter, u_end;
for (boost::tie(u_iter,u_end) = vertices(g); u_iter != u_end; ++u_iter) {
put(color, *u_iter, ColorTraits::white());
put(distance, *u_iter, n);
}
put(color, sink, ColorTraits::gray());
put(distance, sink, 0);
for (distance_size_type l = 0; l <= max_distance; ++l) {
layers[l].active_vertices.clear();
layers[l].inactive_vertices.clear();
}
max_distance = max_active = 0;
min_active = n;
Q.push(sink);
while (! Q.empty()) {
vertex_descriptor u = Q.top();
Q.pop();
distance_size_type d_v = get(distance, u) + 1;
out_edge_iterator ai, a_end;
for (boost::tie(ai, a_end) = out_edges(u, g); ai != a_end; ++ai) {
edge_descriptor a = *ai;
vertex_descriptor v = target(a, g);
if (get(color, v) == ColorTraits::white()
&& is_residual_edge(get(reverse_edge, a))) {
put(distance, v, d_v);
put(color, v, ColorTraits::gray());
current[v] = out_edges(v, g);
max_distance = max BOOST_PREVENT_MACRO_SUBSTITUTION(d_v, max_distance);
if (get(excess_flow, v) > 0)
add_to_active_list(v, layers[d_v]);
else
add_to_inactive_list(v, layers[d_v]);
Q.push(v);
}
}
}
} // global_distance_update()
//=======================================================================
// This function is called "push" in Goldberg's h_prf implementation,
// but it is called "discharge" in the paper and in hi_pr.c.
void discharge(vertex_descriptor u)
{
BOOST_ASSERT(get(excess_flow, u) > 0);
while (1) {
out_edge_iterator ai, ai_end;
for (boost::tie(ai, ai_end) = current[u]; ai != ai_end; ++ai) {
edge_descriptor a = *ai;
if (is_residual_edge(a)) {
vertex_descriptor v = target(a, g);
if (is_admissible(u, v)) {
++push_count;
if (v != sink && get(excess_flow, v) == 0) {
remove_from_inactive_list(v);
add_to_active_list(v, layers[get(distance, v)]);
}
push_flow(a);
if (get(excess_flow, u) == 0)
break;
}
}
} // for out_edges of i starting from current
Layer& layer = layers[get(distance, u)];
distance_size_type du = get(distance, u);
if (ai == ai_end) { // i must be relabeled
relabel_distance(u);
if (layer.active_vertices.empty()
&& layer.inactive_vertices.empty())
gap(du);
if (get(distance, u) == n)
break;
} else { // i is no longer active
current[u].first = ai;
add_to_inactive_list(u, layer);
break;
}
} // while (1)
} // discharge()
//=======================================================================
// This corresponds to the "push" update operation of the paper,
// not the "push" function in Goldberg's h_prf.c implementation.
// The idea is to push the excess flow from from vertex u to v.
void push_flow(edge_descriptor u_v)
{
vertex_descriptor
u = source(u_v, g),
v = target(u_v, g);
BOOST_USING_STD_MIN();
FlowValue flow_delta
= min BOOST_PREVENT_MACRO_SUBSTITUTION(get(excess_flow, u), get(residual_capacity, u_v));
put(residual_capacity, u_v, get(residual_capacity, u_v) - flow_delta);
edge_descriptor rev = get(reverse_edge, u_v);
put(residual_capacity, rev, get(residual_capacity, rev) + flow_delta);
put(excess_flow, u, get(excess_flow, u) - flow_delta);
put(excess_flow, v, get(excess_flow, v) + flow_delta);
} // push_flow()
//=======================================================================
// The main purpose of this routine is to set distance[v]
// to the smallest value allowed by the valid labeling constraints,
// which are:
// distance[t] = 0
// distance[u] <= distance[v] + 1 for every residual edge (u,v)
//
distance_size_type relabel_distance(vertex_descriptor u)
{
BOOST_USING_STD_MAX();
++relabel_count;
work_since_last_update += beta();
distance_size_type min_distance = num_vertices(g);
put(distance, u, min_distance);
// Examine the residual out-edges of vertex i, choosing the
// edge whose target vertex has the minimal distance.
out_edge_iterator ai, a_end, min_edge_iter;
for (boost::tie(ai, a_end) = out_edges(u, g); ai != a_end; ++ai) {
++work_since_last_update;
edge_descriptor a = *ai;
vertex_descriptor v = target(a, g);
if (is_residual_edge(a) && get(distance, v) < min_distance) {
min_distance = get(distance, v);
min_edge_iter = ai;
}
}
++min_distance;
if (min_distance < n) {
put(distance, u, min_distance); // this is the main action
current[u].first = min_edge_iter;
max_distance = max BOOST_PREVENT_MACRO_SUBSTITUTION(min_distance, max_distance);
}
return min_distance;
} // relabel_distance()
//=======================================================================
// cleanup beyond the gap
void gap(distance_size_type empty_distance)
{
++gap_count;
distance_size_type r; // distance of layer before the current layer
r = empty_distance - 1;
// Set the distance for the vertices beyond the gap to "infinity".
for (layer_iterator l = layers.begin() + empty_distance + 1;
l < layers.begin() + max_distance; ++l) {
list_iterator i;
for (i = l->inactive_vertices.begin();
i != l->inactive_vertices.end(); ++i) {
put(distance, *i, n);
++gap_node_count;
}
l->inactive_vertices.clear();
}
max_distance = r;
max_active = r;
}
//=======================================================================
// This is the core part of the algorithm, "phase one".
FlowValue maximum_preflow()
{
work_since_last_update = 0;
while (max_active >= min_active) { // "main" loop
Layer& layer = layers[max_active];
list_iterator u_iter = layer.active_vertices.begin();
if (u_iter == layer.active_vertices.end())
--max_active;
else {
vertex_descriptor u = *u_iter;
remove_from_active_list(u);
discharge(u);
if (work_since_last_update * global_update_frequency() > nm) {
global_distance_update();
work_since_last_update = 0;
}
}
} // while (max_active >= min_active)
return get(excess_flow, sink);
} // maximum_preflow()
//=======================================================================
// remove excess flow, the "second phase"
// This does a DFS on the reverse flow graph of nodes with excess flow.
// If a cycle is found, cancel it.
// Return the nodes with excess flow in topological order.
//
// Unlike the prefl_to_flow() implementation, we use
// "color" instead of "distance" for the DFS labels
// "parent" instead of nl_prev for the DFS tree
// "topo_next" instead of nl_next for the topological ordering
void convert_preflow_to_flow()
{
vertex_iterator u_iter, u_end;
out_edge_iterator ai, a_end;
vertex_descriptor r, restart, u;
std::vector<vertex_descriptor> parent(n);
std::vector<vertex_descriptor> topo_next(n);
vertex_descriptor tos(parent[0]),
bos(parent[0]); // bogus initialization, just to avoid warning
bool bos_null = true;
// handle self-loops
for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
for (boost::tie(ai, a_end) = out_edges(*u_iter, g); ai != a_end; ++ai)
if (target(*ai, g) == *u_iter)
put(residual_capacity, *ai, get(capacity, *ai));
// initialize
for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) {
u = *u_iter;
put(color, u, ColorTraits::white());
parent[get(index, u)] = u;
current[u] = out_edges(u, g);
}
// eliminate flow cycles and topologically order the vertices
for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) {
u = *u_iter;
if (get(color, u) == ColorTraits::white()
&& get(excess_flow, u) > 0
&& u != src && u != sink ) {
r = u;
put(color, r, ColorTraits::gray());
while (1) {
for (; current[u].first != current[u].second; ++current[u].first) {
edge_descriptor a = *current[u].first;
if (get(capacity, a) == 0 && is_residual_edge(a)) {
vertex_descriptor v = target(a, g);
if (get(color, v) == ColorTraits::white()) {
put(color, v, ColorTraits::gray());
parent[get(index, v)] = u;
u = v;
break;
} else if (get(color, v) == ColorTraits::gray()) {
// find minimum flow on the cycle
FlowValue delta = get(residual_capacity, a);
while (1) {
BOOST_USING_STD_MIN();
delta = min BOOST_PREVENT_MACRO_SUBSTITUTION(delta, get(residual_capacity, *current[v].first));
if (v == u)
break;
else
v = target(*current[v].first, g);
}
// remove delta flow units
v = u;
while (1) {
a = *current[v].first;
put(residual_capacity, a, get(residual_capacity, a) - delta);
edge_descriptor rev = get(reverse_edge, a);
put(residual_capacity, rev, get(residual_capacity, rev) + delta);
v = target(a, g);
if (v == u)
break;
}
// back-out of DFS to the first saturated edge
restart = u;
for (v = target(*current[u].first, g); v != u; v = target(a, g)){
a = *current[v].first;
if (get(color, v) == ColorTraits::white()
|| is_saturated(a)) {
put(color, target(*current[v].first, g), ColorTraits::white());
if (get(color, v) != ColorTraits::white())
restart = v;
}
}
if (restart != u) {
u = restart;
++current[u].first;
break;
}
} // else if (color[v] == ColorTraits::gray())
} // if (get(capacity, a) == 0 ...
} // for out_edges(u, g) (though "u" changes during loop)
if ( current[u].first == current[u].second ) {
// scan of i is complete
put(color, u, ColorTraits::black());
if (u != src) {
if (bos_null) {
bos = u;
bos_null = false;
tos = u;
} else {
topo_next[get(index, u)] = tos;
tos = u;
}
}
if (u != r) {
u = parent[get(index, u)];
++current[u].first;
} else
break;
}
} // while (1)
} // if (color[u] == white && excess_flow[u] > 0 & ...)
} // for all vertices in g
// return excess flows
// note that the sink is not on the stack
if (! bos_null) {
for (u = tos; u != bos; u = topo_next[get(index, u)]) {
boost::tie(ai, a_end) = out_edges(u, g);
while (get(excess_flow, u) > 0 && ai != a_end) {
if (get(capacity, *ai) == 0 && is_residual_edge(*ai))
push_flow(*ai);
++ai;
}
}
// do the bottom
u = bos;
boost::tie(ai, a_end) = out_edges(u, g);
while (get(excess_flow, u) > 0 && ai != a_end) {
if (get(capacity, *ai) == 0 && is_residual_edge(*ai))
push_flow(*ai);
++ai;
}
}
} // convert_preflow_to_flow()
//=======================================================================
inline bool is_flow()
{
vertex_iterator u_iter, u_end;
out_edge_iterator ai, a_end;
// check edge flow values
for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) {
for (boost::tie(ai, a_end) = out_edges(*u_iter, g); ai != a_end; ++ai) {
edge_descriptor a = *ai;
if (get(capacity, a) > 0)
if ((get(residual_capacity, a) + get(residual_capacity, get(reverse_edge, a))
!= get(capacity, a) + get(capacity, get(reverse_edge, a)))
|| (get(residual_capacity, a) < 0)
|| (get(residual_capacity, get(reverse_edge, a)) < 0))
return false;
}
}
// check conservation
FlowValue sum;
for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) {
vertex_descriptor u = *u_iter;
if (u != src && u != sink) {
if (get(excess_flow, u) != 0)
return false;
sum = 0;
for (boost::tie(ai, a_end) = out_edges(u, g); ai != a_end; ++ai)
if (get(capacity, *ai) > 0)
sum -= get(capacity, *ai) - get(residual_capacity, *ai);
else
sum += get(residual_capacity, *ai);
if (get(excess_flow, u) != sum)
return false;
}
}
return true;
} // is_flow()
bool is_optimal() {
// check if mincut is saturated...
global_distance_update();
return get(distance, src) >= n;
}
void print_statistics(std::ostream& os) const {
os << "pushes: " << push_count << std::endl
<< "relabels: " << relabel_count << std::endl
<< "updates: " << update_count << std::endl
<< "gaps: " << gap_count << std::endl
<< "gap nodes: " << gap_node_count << std::endl
<< std::endl;
}
void print_flow_values(std::ostream& os) const {
os << "flow values" << std::endl;
vertex_iterator u_iter, u_end;
out_edge_iterator ei, e_end;
for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
for (boost::tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)
if (get(capacity, *ei) > 0)
os << *u_iter << " " << target(*ei, g) << " "
<< (get(capacity, *ei) - get(residual_capacity, *ei)) << std::endl;
os << std::endl;
}
//=======================================================================
Graph& g;
vertices_size_type n;
vertices_size_type nm;
EdgeCapacityMap capacity;
vertex_descriptor src;
vertex_descriptor sink;
VertexIndexMap index;
// will need to use random_access_property_map with these
std::vector< FlowValue > excess_flow_data;
iterator_property_map<typename std::vector<FlowValue>::iterator, VertexIndexMap> excess_flow;
std::vector< std::pair<out_edge_iterator, out_edge_iterator> > current_data;
iterator_property_map<
typename std::vector< std::pair<out_edge_iterator, out_edge_iterator> >::iterator,
VertexIndexMap> current;
std::vector< distance_size_type > distance_data;
iterator_property_map<
typename std::vector< distance_size_type >::iterator,
VertexIndexMap> distance;
std::vector< default_color_type > color_data;
iterator_property_map<
std::vector< default_color_type >::iterator,
VertexIndexMap> color;
// Edge Property Maps that must be interior to the graph
ReverseEdgeMap reverse_edge;
ResidualCapacityEdgeMap residual_capacity;
LayerArray layers;
std::vector< list_iterator > layer_list_ptr_data;
iterator_property_map<typename std::vector< list_iterator >::iterator, VertexIndexMap> layer_list_ptr;
distance_size_type max_distance; // maximal distance
distance_size_type max_active; // maximal distance with active node
distance_size_type min_active; // minimal distance with active node
boost::queue<vertex_descriptor> Q;
// Statistics counters
long push_count;
long update_count;
long relabel_count;
long gap_count;
long gap_node_count;
inline double global_update_frequency() { return 0.5; }
inline vertices_size_type alpha() { return 6; }
inline long beta() { return 12; }
long work_since_last_update;
};
} // namespace detail
template <class Graph,
class CapacityEdgeMap, class ResidualCapacityEdgeMap,
class ReverseEdgeMap, class VertexIndexMap>
typename property_traits<CapacityEdgeMap>::value_type
push_relabel_max_flow
(Graph& g,
typename graph_traits<Graph>::vertex_descriptor src,
typename graph_traits<Graph>::vertex_descriptor sink,
CapacityEdgeMap cap, ResidualCapacityEdgeMap res,
ReverseEdgeMap rev, VertexIndexMap index_map)
{
typedef typename property_traits<CapacityEdgeMap>::value_type FlowValue;
detail::push_relabel<Graph, CapacityEdgeMap, ResidualCapacityEdgeMap,
ReverseEdgeMap, VertexIndexMap, FlowValue>
algo(g, cap, res, rev, src, sink, index_map);
FlowValue flow = algo.maximum_preflow();
algo.convert_preflow_to_flow();
BOOST_ASSERT(algo.is_flow());
BOOST_ASSERT(algo.is_optimal());
return flow;
} // push_relabel_max_flow()
template <class Graph, class P, class T, class R>
typename detail::edge_capacity_value<Graph, P, T, R>::type
push_relabel_max_flow
(Graph& g,
typename graph_traits<Graph>::vertex_descriptor src,
typename graph_traits<Graph>::vertex_descriptor sink,
const bgl_named_params<P, T, R>& params)
{
return push_relabel_max_flow
(g, src, sink,
choose_const_pmap(get_param(params, edge_capacity), g, edge_capacity),
choose_pmap(get_param(params, edge_residual_capacity),
g, edge_residual_capacity),
choose_const_pmap(get_param(params, edge_reverse), g, edge_reverse),
choose_const_pmap(get_param(params, vertex_index), g, vertex_index)
);
}
template <class Graph>
typename property_traits<
typename property_map<Graph, edge_capacity_t>::const_type
>::value_type
push_relabel_max_flow
(Graph& g,
typename graph_traits<Graph>::vertex_descriptor src,
typename graph_traits<Graph>::vertex_descriptor sink)
{
bgl_named_params<int, buffer_param_t> params(0); // bogus empty param
return push_relabel_max_flow(g, src, sink, params);
}
} // namespace boost
#endif // BOOST_PUSH_RELABEL_MAX_FLOW_HPP
Reference in New Issue View Git Blame Copy Permalink