1 //======================================================================= 2 // Copyright 2013 University of Warsaw. 3 // Authors: Piotr Wygocki 4 // 5 // Distributed under the Boost Software License, Version 1.0. (See 6 // accompanying file LICENSE_1_0.txt or copy at 7 // http://www.boost.org/LICENSE_1_0.txt) 8 //======================================================================= 9 10 #ifndef BOOST_GRAPH_AUGMENT_HPP 11 #define BOOST_GRAPH_AUGMENT_HPP 12 13 #include <boost/graph/filtered_graph.hpp> 14 15 namespace boost 16 { 17 namespace detail 18 { 19 20 template < class Graph, class ResCapMap > residual_graph(const Graph & g,ResCapMap residual_capacity)21 filtered_graph< const Graph, is_residual_edge< ResCapMap > > residual_graph( 22 const Graph& g, ResCapMap residual_capacity) 23 { 24 return filtered_graph< const Graph, is_residual_edge< ResCapMap > >( 25 g, is_residual_edge< ResCapMap >(residual_capacity)); 26 } 27 28 template < class Graph, class PredEdgeMap, class ResCapMap, 29 class RevEdgeMap > 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)30 inline void augment(const Graph& g, 31 typename graph_traits< Graph >::vertex_descriptor src, 32 typename graph_traits< Graph >::vertex_descriptor sink, PredEdgeMap p, 33 ResCapMap residual_capacity, RevEdgeMap reverse_edge) 34 { 35 typename graph_traits< Graph >::edge_descriptor e; 36 typename graph_traits< Graph >::vertex_descriptor u; 37 typedef typename property_traits< ResCapMap >::value_type FlowValue; 38 39 // find minimum residual capacity along the augmenting path 40 FlowValue delta = (std::numeric_limits< FlowValue >::max)(); 41 e = get(p, sink); 42 do 43 { 44 BOOST_USING_STD_MIN(); 45 delta = min BOOST_PREVENT_MACRO_SUBSTITUTION( 46 delta, get(residual_capacity, e)); 47 u = source(e, g); 48 e = get(p, u); 49 } while (u != src); 50 51 // push delta units of flow along the augmenting path 52 e = get(p, sink); 53 do 54 { 55 put(residual_capacity, e, get(residual_capacity, e) - delta); 56 put(residual_capacity, get(reverse_edge, e), 57 get(residual_capacity, get(reverse_edge, e)) + delta); 58 u = source(e, g); 59 e = get(p, u); 60 } while (u != src); 61 } 62 63 } // namespace detail 64 } // namespace boost 65 66 #endif /* BOOST_GRAPH_AUGMENT_HPP */ 67