//======================================================================= | |
// 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[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[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[u] = tos; | |
tos = u; | |
} | |
} | |
if (u != r) { | |
u = parent[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[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; | |
ai = out_edges(u, g).first; | |
while (get(excess_flow, u) > 0) { | |
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 | |