123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263 |
- //=======================================================================
- // Copyright 2013 University of Warsaw.
- // Authors: Piotr Wygocki
- //
- // 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_GRAPH_AUGMENT_HPP
- #define BOOST_GRAPH_AUGMENT_HPP
- #include <boost/graph/filtered_graph.hpp>
- namespace boost {
- namespace detail {
- template <class Graph, class ResCapMap>
- filtered_graph<const Graph, is_residual_edge<ResCapMap> >
- residual_graph(const Graph& g, ResCapMap residual_capacity) {
- return filtered_graph<const Graph, is_residual_edge<ResCapMap> >
- (g, is_residual_edge<ResCapMap>(residual_capacity));
- }
- template <class Graph, class PredEdgeMap, class ResCapMap,
- class RevEdgeMap>
- inline void
- augment(const Graph& g,
- typename graph_traits<Graph>::vertex_descriptor src,
- typename graph_traits<Graph>::vertex_descriptor sink,
- PredEdgeMap p,
- ResCapMap residual_capacity,
- RevEdgeMap reverse_edge)
- {
- typename graph_traits<Graph>::edge_descriptor e;
- typename graph_traits<Graph>::vertex_descriptor u;
- typedef typename property_traits<ResCapMap>::value_type FlowValue;
- // find minimum residual capacity along the augmenting path
- FlowValue delta = (std::numeric_limits<FlowValue>::max)();
- e = get(p, sink);
- do {
- BOOST_USING_STD_MIN();
- delta = min BOOST_PREVENT_MACRO_SUBSTITUTION(delta, get(residual_capacity, e));
- u = source(e, g);
- e = get(p, u);
- } while (u != src);
- // push delta units of flow along the augmenting path
- e = get(p, sink);
- do {
- put(residual_capacity, e, get(residual_capacity, e) - delta);
- put(residual_capacity, get(reverse_edge, e), get(residual_capacity, get(reverse_edge, e)) + delta);
- u = source(e, g);
- e = get(p, u);
- } while (u != src);
- }
- } // namespace detail
- } //namespace boost
- #endif /* BOOST_GRAPH_AUGMENT_HPP */
|