annotate DEPENDENCIES/generic/include/boost/graph/push_relabel_max_flow.hpp @ 125:34e428693f5d vext

Vext -> Repoint

//=======================================================================
// 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