2664 /// \ingroup graph_adaptors |
2664 /// \ingroup graph_adaptors |
2665 /// |
2665 /// |
2666 /// \brief Adaptor class for composing the residual digraph for directed |
2666 /// \brief Adaptor class for composing the residual digraph for directed |
2667 /// flow and circulation problems. |
2667 /// flow and circulation problems. |
2668 /// |
2668 /// |
2669 /// Residual can be used for composing the \e residual digraph for directed |
2669 /// ResidualDigraph can be used for composing the \e residual digraph |
2670 /// flow and circulation problems. Let \f$ G=(V, A) \f$ be a directed graph |
2670 /// for directed flow and circulation problems. Let \f$ G=(V, A) \f$ |
2671 /// and let \f$ F \f$ be a number type. Let \f$ flow, cap: A\to F \f$ be |
2671 /// be a directed graph and let \f$ F \f$ be a number type. |
2672 /// functions on the arcs. |
2672 /// Let \f$ flow, cap: A\to F \f$ be functions on the arcs. |
2673 /// This adaptor implements a digraph structure with node set \f$ V \f$ |
2673 /// This adaptor implements a digraph structure with node set \f$ V \f$ |
2674 /// and arc set \f$ A_{forward}\cup A_{backward} \f$, |
2674 /// and arc set \f$ A_{forward}\cup A_{backward} \f$, |
2675 /// where \f$ A_{forward}=\{uv : uv\in A, flow(uv)<cap(uv)\} \f$ and |
2675 /// where \f$ A_{forward}=\{uv : uv\in A, flow(uv)<cap(uv)\} \f$ and |
2676 /// \f$ A_{backward}=\{vu : uv\in A, flow(uv)>0\} \f$, i.e. the so |
2676 /// \f$ A_{backward}=\{vu : uv\in A, flow(uv)>0\} \f$, i.e. the so |
2677 /// called residual digraph. |
2677 /// called residual digraph. |
2702 /// \note The \c Node type of this adaptor and the adapted digraph are |
2702 /// \note The \c Node type of this adaptor and the adapted digraph are |
2703 /// convertible to each other, moreover the \c Arc type of the adaptor |
2703 /// convertible to each other, moreover the \c Arc type of the adaptor |
2704 /// is convertible to the \c Arc type of the adapted digraph. |
2704 /// is convertible to the \c Arc type of the adapted digraph. |
2705 #ifdef DOXYGEN |
2705 #ifdef DOXYGEN |
2706 template<typename GR, typename CM, typename FM, typename TL> |
2706 template<typename GR, typename CM, typename FM, typename TL> |
2707 class Residual |
2707 class ResidualDigraph |
2708 #else |
2708 #else |
2709 template<typename GR, |
2709 template<typename GR, |
2710 typename CM = typename GR::template ArcMap<int>, |
2710 typename CM = typename GR::template ArcMap<int>, |
2711 typename FM = CM, |
2711 typename FM = CM, |
2712 typename TL = Tolerance<typename CM::Value> > |
2712 typename TL = Tolerance<typename CM::Value> > |
2713 class Residual : |
2713 class ResidualDigraph : |
2714 public FilterArcs< |
2714 public FilterArcs< |
2715 Undirector<const GR>, |
2715 Undirector<const GR>, |
2716 typename Undirector<const GR>::template CombinedArcMap< |
2716 typename Undirector<const GR>::template CombinedArcMap< |
2717 _adaptor_bits::ResForwardFilter<const GR, CM, FM, TL>, |
2717 _adaptor_bits::ResForwardFilter<const GR, CM, FM, TL>, |
2718 _adaptor_bits::ResBackwardFilter<const GR, CM, FM, TL> > > |
2718 _adaptor_bits::ResBackwardFilter<const GR, CM, FM, TL> > > |
2759 |
2759 |
2760 /// \brief Constructor |
2760 /// \brief Constructor |
2761 /// |
2761 /// |
2762 /// Constructor of the residual digraph adaptor. The parameters are the |
2762 /// Constructor of the residual digraph adaptor. The parameters are the |
2763 /// digraph, the capacity map, the flow map, and a tolerance object. |
2763 /// digraph, the capacity map, the flow map, and a tolerance object. |
2764 Residual(const Digraph& digraph, const CapacityMap& capacity, |
2764 ResidualDigraph(const Digraph& digraph, const CapacityMap& capacity, |
2765 FlowMap& flow, const Tolerance& tolerance = Tolerance()) |
2765 FlowMap& flow, const Tolerance& tolerance = Tolerance()) |
2766 : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph), |
2766 : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph), |
2767 _forward_filter(capacity, flow, tolerance), |
2767 _forward_filter(capacity, flow, tolerance), |
2768 _backward_filter(capacity, flow, tolerance), |
2768 _backward_filter(capacity, flow, tolerance), |
2769 _arc_filter(_forward_filter, _backward_filter) |
2769 _arc_filter(_forward_filter, _backward_filter) |
2770 { |
2770 { |
2867 /// |
2867 /// |
2868 /// This function just returns a (read-only) \ref Residual adaptor. |
2868 /// This function just returns a (read-only) \ref Residual adaptor. |
2869 /// \ingroup graph_adaptors |
2869 /// \ingroup graph_adaptors |
2870 /// \relates Residual |
2870 /// \relates Residual |
2871 template<typename GR, typename CM, typename FM> |
2871 template<typename GR, typename CM, typename FM> |
2872 Residual<GR, CM, FM> residual(const GR& digraph, |
2872 ResidualDigraph<GR, CM, FM> |
2873 const CM& capacity_map, |
2873 residualDigraph(const GR& digraph, const CM& capacity_map, FM& flow_map) { |
2874 FM& flow_map) { |
2874 return ResidualDigraph<GR, CM, FM> (digraph, capacity_map, flow_map); |
2875 return Residual<GR, CM, FM> (digraph, capacity_map, flow_map); |
|
2876 } |
2875 } |
2877 |
2876 |
2878 |
2877 |
2879 template <typename _Digraph> |
2878 template <typename _Digraph> |
2880 class SplitNodesBase { |
2879 class SplitNodesBase { |