lemon/adaptors.h
changeset 477 e6ae4999cf22
parent 455 5a1e9fdcfd3a
child 488 9b9ffe7d9b75
equal deleted inserted replaced
11:523748220451 12:3a8698450852
  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> > >
  2728     typedef FM FlowMap;
  2728     typedef FM FlowMap;
  2729     /// The tolerance type.
  2729     /// The tolerance type.
  2730     typedef TL Tolerance;
  2730     typedef TL Tolerance;
  2731 
  2731 
  2732     typedef typename CapacityMap::Value Value;
  2732     typedef typename CapacityMap::Value Value;
  2733     typedef Residual Adaptor;
  2733     typedef ResidualDigraph Adaptor;
  2734 
  2734 
  2735   protected:
  2735   protected:
  2736 
  2736 
  2737     typedef Undirector<const Digraph> Undirected;
  2737     typedef Undirector<const Digraph> Undirected;
  2738 
  2738 
  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 {