push_relabel_max_flow.hpp

来自「CGAL is a collaborative effort of severa」· HPP 代码 · 共 743 行 · 第 1/2 页

//=======================================================================
// Copyright 2000 University of Notre Dame.
// Authors: Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee
//
// This file is part of the Boost Graph Library
//
// You should have received a copy of the License Agreement for the
// Boost Graph Library along with the software; see the file LICENSE.
// If not, contact Office of Research, University of Notre Dame, Notre
// Dame, IN 46556.
//
// Permission to modify the code and to distribute modified code is
// granted, provided the text of this NOTICE is retained, a notice that
// the code was modified is included with the above COPYRIGHT NOTICE and
// with the COPYRIGHT NOTICE in the LICENSE file, and that the LICENSE
// file is distributed with the modified code.
//
// LICENSOR MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED.
// By way of example, but not limitation, Licensor MAKES NO
// REPRESENTATIONS OR WARRANTIES OF MERCHANTABILITY OR FITNESS FOR ANY
// PARTICULAR PURPOSE OR THAT THE USE OF THE LICENSED SOFTWARE COMPONENTS
// OR DOCUMENTATION WILL NOT INFRINGE ANY PATENTS, COPYRIGHTS, TRADEMARKS
// OR OTHER RIGHTS.
//=======================================================================

#ifndef BOOST_PUSH_RELABEL_MAX_FLOW_HPP
#define BOOST_PUSH_RELABEL_MAX_FLOW_HPP

#include <boost/config.hpp>
#include <cassert>
#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 distance[u] == distance[v] + 1;
      }
      inline bool is_residual_edge(edge_descriptor a) {
        return 0 < residual_capacity[a];
      }
      inline bool is_saturated(edge_descriptor a) {
        return 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(distance[u], max_active);
        min_active = min BOOST_PREVENT_MACRO_SUBSTITUTION(distance[u], min_active);
        layer_list_ptr[u] = layer.active_vertices.begin();
      }
      void remove_from_active_list(vertex_descriptor u) {
        layers[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[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(num_vertices(g_)),
          layer_list_ptr(num_vertices(g_)),
          current(num_vertices(g_)),
          distance(num_vertices(g_)),
          color(num_vertices(g_)),
          reverse_edge(rev),
          residual_capacity(res),
          layers(num_vertices(g_)),
          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 (tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
          for (tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei) {
            residual_capacity[*ei] = capacity[*ei];
          }

        for (tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) {
          vertex_descriptor u = *u_iter;
          excess_flow[u] = 0;
          current[u] = out_edges(u, g).first;
        }

        bool overflow_detected = false;
        FlowValue test_excess = 0;

        out_edge_iterator a_iter, a_end;
        for (tie(a_iter, a_end) = out_edges(src, g); a_iter != a_end; ++a_iter)
          if (target(*a_iter, g) != src)
            test_excess += residual_capacity[*a_iter];
        if (test_excess > (std::numeric_limits<FlowValue>::max)())
          overflow_detected = true;

        if (overflow_detected)
          excess_flow[src] = (std::numeric_limits<FlowValue>::max)();
        else {
          excess_flow[src] = 0;
          for (tie(a_iter, a_end) = out_edges(src, g); 
               a_iter != a_end; ++a_iter) {
            edge_descriptor a = *a_iter;
            if (target(a, g) != src) {
              ++push_count;
              FlowValue delta = residual_capacity[a];
              residual_capacity[a] -= delta;
              residual_capacity[reverse_edge[a]] += delta;
              excess_flow[target(a, g)] += delta;
            }
          }
        }
        max_distance = num_vertices(g) - 1;
        max_active = 0;
        min_active = n;

        for (tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) {
          vertex_descriptor u = *u_iter;
          if (u == sink) {
            distance[u] = 0;
            continue;
          } else if (u == src && !overflow_detected)
            distance[u] = n;
          else
            distance[u] = 1;

          if (excess_flow[u] > 0)
            add_to_active_list(u, layers[1]);
          else if (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 (tie(u_iter,u_end) = vertices(g); u_iter != u_end; ++u_iter) {
          color[*u_iter] = ColorTraits::white();
          distance[*u_iter] = n;
        }
        color[sink] = ColorTraits::gray();
        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 = distance[u] + 1;

          out_edge_iterator ai, a_end;
          for (tie(ai, a_end) = out_edges(u, g); ai != a_end; ++ai) {
            edge_descriptor a = *ai;
            vertex_descriptor v = target(a, g);
            if (color[v] == ColorTraits::white()
                && is_residual_edge(reverse_edge[a])) {
              distance[v] = d_v;
              color[v] = ColorTraits::gray();
              current[v] = out_edges(v, g).first;
              max_distance = max BOOST_PREVENT_MACRO_SUBSTITUTION(d_v, max_distance);

              if (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)
      {
        assert(excess_flow[u] > 0);
        while (1) {
          out_edge_iterator ai, ai_end;
          for (ai = current[u], ai_end = out_edges(u, g).second;
               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 && excess_flow[v] == 0) {
                  remove_from_inactive_list(v);
                  add_to_active_list(v, layers[distance[v]]);
                }
                push_flow(a);
                if (excess_flow[u] == 0)
                  break;
              } 
            } 
          } // for out_edges of i starting from current

          Layer& layer = layers[distance[u]];
          distance_size_type du = 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 (distance[u] == n)
              break;
          } else {              // i is no longer active
            current[u] = 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(excess_flow[u], residual_capacity[u_v]);

        residual_capacity[u_v] -= flow_delta;
        residual_capacity[reverse_edge[u_v]] += flow_delta;

        excess_flow[u] -= flow_delta;
        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);
        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 (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) && distance[v] < min_distance) {
            min_distance = distance[v];
            min_edge_iter = ai;
          }
        }
        ++min_distance;
        if (min_distance < n) {
          distance[u] = min_distance;     // this is the main action
          current[u] = min_edge_iter;
          max_distance = max BOOST_PREVENT_MACRO_SUBSTITUTION(min_distance, max_distance);
        }
        return min_distance;
      } // relabel_distance()