FM / graph

/usr/include/boost/graph

Name	Size	Mode	Actions
detail/	-	0755	rm
distributed/	-	0755	rm
parallel/	-	0755	rm
planar_detail/	-	0755	rm
property_maps/	-	0755	rm
accounting.hpp	876	0644	edit dl rm
adjacency_iterator.hpp	2899	0644	edit dl rm
adjacency_list.hpp	13692	0644	edit dl rm
adjacency_list_io.hpp	11849	0644	edit dl rm
adjacency_matrix.hpp	45743	0644	edit dl rm
adj_list_serialize.hpp	4523	0644	edit dl rm
astar_search.hpp	26736	0644	edit dl rm
bandwidth.hpp	2992	0644	edit dl rm
bc_clustering.hpp	5937	0644	edit dl rm
bellman_ford_shortest_paths.hpp	8229	0644	edit dl rm
betweenness_centrality.hpp	26290	0644	edit dl rm
biconnected_components.hpp	16701	0644	edit dl rm
bipartite.hpp	13492	0644	edit dl rm
boyer_myrvold_planar_test.hpp	9849	0644	edit dl rm
boykov_kolmogorov_max_flow.hpp	47342	0644	edit dl rm
breadth_first_search.hpp	14751	0644	edit dl rm
bron_kerbosch_all_cliques.hpp	11736	0644	edit dl rm
buffer_concepts.hpp	2429	0644	edit dl rm
chrobak_payne_drawing.hpp	8641	0644	edit dl rm
circle_layout.hpp	1924	0644	edit dl rm
closeness_centrality.hpp	6057	0644	edit dl rm
clustering_coefficient.hpp	5726	0644	edit dl rm
compressed_sparse_row_graph.hpp	69887	0644	edit dl rm
connected_components.hpp	4134	0644	edit dl rm
copy.hpp	21225	0644	edit dl rm
core_numbers.hpp	13663	0644	edit dl rm
create_condensation_graph.hpp	3159	0644	edit dl rm
cuthill_mckee_ordering.hpp	5992	0644	edit dl rm
cycle_canceling.hpp	6645	0644	edit dl rm
dag_shortest_paths.hpp	6064	0644	edit dl rm
degree_centrality.hpp	4236	0644	edit dl rm
depth_first_search.hpp	15430	0644	edit dl rm
dijkstra_shortest_paths.hpp	23687	0644	edit dl rm
dijkstra_shortest_paths_no_color_map.hpp	9620	0644	edit dl rm
dimacs.hpp	10448	0644	edit dl rm
directed_graph.hpp	24214	0644	edit dl rm
dll_import_export.hpp	892	0644	edit dl rm
dominator_tree.hpp	17553	0644	edit dl rm
eccentricity.hpp	4611	0644	edit dl rm
edge_coloring.hpp	6809	0644	edit dl rm
edge_connectivity.hpp	6796	0644	edit dl rm
edge_list.hpp	9948	0644	edit dl rm
edmonds_karp_max_flow.hpp	10177	0644	edit dl rm
edmunds_karp_max_flow.hpp	982	0644	edit dl rm
erdos_renyi_generator.hpp	7257	0644	edit dl rm
exception.hpp	1466	0644	edit dl rm
exterior_property.hpp	4289	0644	edit dl rm
filtered_graph.hpp	20098	0644	edit dl rm
find_flow_cost.hpp	1859	0644	edit dl rm
floyd_warshall_shortest.hpp	8510	0644	edit dl rm
fruchterman_reingold.hpp	17325	0644	edit dl rm
geodesic_distance.hpp	8015	0644	edit dl rm
graphml.hpp	13460	0644	edit dl rm
graphviz.hpp	33503	0644	edit dl rm
graph_archetypes.hpp	11008	0644	edit dl rm
graph_as_tree.hpp	4532	0644	edit dl rm
graph_concepts.hpp	19785	0644	edit dl rm
graph_mutability_traits.hpp	4995	0644	edit dl rm
graph_selectors.hpp	1274	0644	edit dl rm
graph_stats.hpp	4394	0644	edit dl rm
graph_traits.hpp	13065	0644	edit dl rm
graph_utility.hpp	16182	0644	edit dl rm
grid_graph.hpp	33830	0644	edit dl rm
gursoy_atun_layout.hpp	13248	0644	edit dl rm
hawick_circuits.hpp	14593	0644	edit dl rm
howard_cycle_ratio.hpp	23107	0644	edit dl rm
incremental_components.hpp	8224	0644	edit dl rm
isomorphism.hpp	26308	0644	edit dl rm
is_kuratowski_subgraph.hpp	10260	0644	edit dl rm
is_straight_line_drawing.hpp	7230	0644	edit dl rm
iteration_macros.hpp	11659	0644	edit dl rm
iteration_macros_undef.hpp	673	0644	edit dl rm
johnson_all_pairs_shortest.hpp	7646	0644	edit dl rm
kamada_kawai_spring_layout.hpp	28048	0644	edit dl rm
king_ordering.hpp	12101	0644	edit dl rm
kruskal_min_spanning_tree.hpp	5743	0644	edit dl rm
labeled_graph.hpp	30914	0644	edit dl rm
leda_graph.hpp	28789	0644	edit dl rm
lookup_edge.hpp	1894	0644	edit dl rm
loop_erased_random_walk.hpp	4436	0644	edit dl rm
make_biconnected_planar.hpp	3513	0644	edit dl rm
make_connected.hpp	2645	0644	edit dl rm
make_maximal_planar.hpp	7578	0644	edit dl rm
matrix_as_graph.hpp	7227	0644	edit dl rm
maximum_adjacency_search.hpp	15125	0644	edit dl rm
maximum_weighted_matching.hpp	49722	0644	edit dl rm
max_cardinality_matching.hpp	31000	0644	edit dl rm
mcgregor_common_subgraphs.hpp	43470	0644	edit dl rm
mesh_graph_generator.hpp	5616	0644	edit dl rm
metis.hpp	10982	0644	edit dl rm
metric_tsp_approx.hpp	10809	0644	edit dl rm
minimum_degree_ordering.hpp	27087	0644	edit dl rm
named_function_params.hpp	39639	0644	edit dl rm
named_graph.hpp	20614	0644	edit dl rm
neighbor_bfs.hpp	11763	0644	edit dl rm
numeric_values.hpp	1814	0644	edit dl rm
one_bit_color_map.hpp	3277	0644	edit dl rm
overloading.hpp	1584	0644	edit dl rm
page_rank.hpp	6164	0644	edit dl rm
planar_canonical_ordering.hpp	7203	0644	edit dl rm
planar_face_traversal.hpp	6020	0644	edit dl rm
plod_generator.hpp	7708	0644	edit dl rm
point_traits.hpp	782	0644	edit dl rm
prim_minimum_spanning_tree.hpp	2960	0644	edit dl rm
profile.hpp	1327	0644	edit dl rm
properties.hpp	12417	0644	edit dl rm
property_iter_range.hpp	4345	0644	edit dl rm
push_relabel_max_flow.hpp	34737	0644	edit dl rm
random.hpp	9672	0644	edit dl rm
random_layout.hpp	988	0644	edit dl rm
random_spanning_tree.hpp	5775	0644	edit dl rm
read_dimacs.hpp	12080	0644	edit dl rm
relax.hpp	4400	0644	edit dl rm
reverse_graph.hpp	22402	0644	edit dl rm
rmat_graph_generator.hpp	19291	0644	edit dl rm
r_c_shortest_paths.hpp	30673	0644	edit dl rm
sequential_vertex_coloring.hpp	4562	0644	edit dl rm
simple_point.hpp	628	0644	edit dl rm
sloan_ordering.hpp	15540	0644	edit dl rm
smallest_last_ordering.hpp	5458	0644	edit dl rm
small_world_generator.hpp	3670	0644	edit dl rm
ssca_graph_generator.hpp	6564	0644	edit dl rm
stanford_graph.hpp	20126	0644	edit dl rm
stoer_wagner_min_cut.hpp	12415	0644	edit dl rm
strong_components.hpp	13009	0644	edit dl rm
st_connected.hpp	2852	0644	edit dl rm
subgraph.hpp	39996	0644	edit dl rm
successive_shortest_path_nonnegative_weights.hpp	10413	0644	edit dl rm
tiernan_all_cycles.hpp	12547	0644	edit dl rm
topological_sort.hpp	2611	0644	edit dl rm
topology.hpp	20389	0644	edit dl rm
transitive_closure.hpp	14260	0644	edit dl rm
transitive_reduction.hpp	5326	0644	edit dl rm
transpose_graph.hpp	1198	0644	edit dl rm
tree_traits.hpp	1338	0644	edit dl rm
two_bit_color_map.hpp	3510	0644	edit dl rm
two_graphs_common_spanning_trees.hpp	34996	0644	edit dl rm
undirected_dfs.hpp	10672	0644	edit dl rm
undirected_graph.hpp	25276	0644	edit dl rm
use_mpi.hpp	437	0644	edit dl rm
vector_as_graph.hpp	10474	0644	edit dl rm
vertex_and_edge_range.hpp	5528	0644	edit dl rm
vf2_sub_graph_iso.hpp	48585	0644	edit dl rm
visitors.hpp	11318	0644	edit dl rm
wavefront.hpp	3932	0644	edit dl rm
write_dimacs.hpp	2889	0644	edit dl rm

Edit: /usr/include/boost/graph/push_relabel_max_flow.hpp (34737B)

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

cmd: