EIC code displayed by LXR master/​include/​boost/​graph/​push_relabel_max_flow.hpp	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2025-01-30 09:43:06

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

This page was automatically generated by the 2.3.7 LXR engine. The LXR team