lemon/preflow.h
changeset 576 745e182d0139
parent 492 9605e051942f
child 581 aa1804409f29
equal deleted inserted replaced
7:98068a26173e 8:8d3d731b597a
    30 
    30 
    31   /// \brief Default traits class of Preflow class.
    31   /// \brief Default traits class of Preflow class.
    32   ///
    32   ///
    33   /// Default traits class of Preflow class.
    33   /// Default traits class of Preflow class.
    34   /// \tparam GR Digraph type.
    34   /// \tparam GR Digraph type.
    35   /// \tparam CM Capacity map type.
    35   /// \tparam CAP Capacity map type.
    36   template <typename GR, typename CM>
    36   template <typename GR, typename CAP>
    37   struct PreflowDefaultTraits {
    37   struct PreflowDefaultTraits {
    38 
    38 
    39     /// \brief The type of the digraph the algorithm runs on.
    39     /// \brief The type of the digraph the algorithm runs on.
    40     typedef GR Digraph;
    40     typedef GR Digraph;
    41 
    41 
    42     /// \brief The type of the map that stores the arc capacities.
    42     /// \brief The type of the map that stores the arc capacities.
    43     ///
    43     ///
    44     /// The type of the map that stores the arc capacities.
    44     /// The type of the map that stores the arc capacities.
    45     /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    45     /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    46     typedef CM CapacityMap;
    46     typedef CAP CapacityMap;
    47 
    47 
    48     /// \brief The type of the flow values.
    48     /// \brief The type of the flow values.
    49     typedef typename CapacityMap::Value Value;
    49     typedef typename CapacityMap::Value Value;
    50 
    50 
    51     /// \brief The type of the map that stores the flow values.
    51     /// \brief The type of the map that stores the flow values.
    92   /// \ingroup max_flow
    92   /// \ingroup max_flow
    93   ///
    93   ///
    94   /// \brief %Preflow algorithm class.
    94   /// \brief %Preflow algorithm class.
    95   ///
    95   ///
    96   /// This class provides an implementation of Goldberg-Tarjan's \e preflow
    96   /// This class provides an implementation of Goldberg-Tarjan's \e preflow
    97   /// \e push-relabel algorithm producing a flow of maximum value in a
    97   /// \e push-relabel algorithm producing a \ref max_flow
    98   /// digraph. The preflow algorithms are the fastest known maximum
    98   /// "flow of maximum value" in a digraph.
       
    99   /// The preflow algorithms are the fastest known maximum
    99   /// flow algorithms. The current implementation use a mixture of the
   100   /// flow algorithms. The current implementation use a mixture of the
   100   /// \e "highest label" and the \e "bound decrease" heuristics.
   101   /// \e "highest label" and the \e "bound decrease" heuristics.
   101   /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
   102   /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
   102   ///
   103   ///
   103   /// The algorithm consists of two phases. After the first phase
   104   /// The algorithm consists of two phases. After the first phase
   104   /// the maximum flow value and the minimum cut is obtained. The
   105   /// the maximum flow value and the minimum cut is obtained. The
   105   /// second phase constructs a feasible maximum flow on each arc.
   106   /// second phase constructs a feasible maximum flow on each arc.
   106   ///
   107   ///
   107   /// \tparam GR The type of the digraph the algorithm runs on.
   108   /// \tparam GR The type of the digraph the algorithm runs on.
   108   /// \tparam CM The type of the capacity map. The default map
   109   /// \tparam CAP The type of the capacity map. The default map
   109   /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
   110   /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
   110 #ifdef DOXYGEN
   111 #ifdef DOXYGEN
   111   template <typename GR, typename CM, typename TR>
   112   template <typename GR, typename CAP, typename TR>
   112 #else
   113 #else
   113   template <typename GR,
   114   template <typename GR,
   114             typename CM = typename GR::template ArcMap<int>,
   115             typename CAP = typename GR::template ArcMap<int>,
   115             typename TR = PreflowDefaultTraits<GR, CM> >
   116             typename TR = PreflowDefaultTraits<GR, CAP> >
   116 #endif
   117 #endif
   117   class Preflow {
   118   class Preflow {
   118   public:
   119   public:
   119 
   120 
   120     ///The \ref PreflowDefaultTraits "traits class" of the algorithm.
   121     ///The \ref PreflowDefaultTraits "traits class" of the algorithm.
   192 
   193 
   193     ///\name Named Template Parameters
   194     ///\name Named Template Parameters
   194 
   195 
   195     ///@{
   196     ///@{
   196 
   197 
   197     template <typename _FlowMap>
   198     template <typename T>
   198     struct SetFlowMapTraits : public Traits {
   199     struct SetFlowMapTraits : public Traits {
   199       typedef _FlowMap FlowMap;
   200       typedef T FlowMap;
   200       static FlowMap *createFlowMap(const Digraph&) {
   201       static FlowMap *createFlowMap(const Digraph&) {
   201         LEMON_ASSERT(false, "FlowMap is not initialized");
   202         LEMON_ASSERT(false, "FlowMap is not initialized");
   202         return 0; // ignore warnings
   203         return 0; // ignore warnings
   203       }
   204       }
   204     };
   205     };
   206     /// \brief \ref named-templ-param "Named parameter" for setting
   207     /// \brief \ref named-templ-param "Named parameter" for setting
   207     /// FlowMap type
   208     /// FlowMap type
   208     ///
   209     ///
   209     /// \ref named-templ-param "Named parameter" for setting FlowMap
   210     /// \ref named-templ-param "Named parameter" for setting FlowMap
   210     /// type.
   211     /// type.
   211     template <typename _FlowMap>
   212     template <typename T>
   212     struct SetFlowMap
   213     struct SetFlowMap
   213       : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<_FlowMap> > {
   214       : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<T> > {
   214       typedef Preflow<Digraph, CapacityMap,
   215       typedef Preflow<Digraph, CapacityMap,
   215                       SetFlowMapTraits<_FlowMap> > Create;
   216                       SetFlowMapTraits<T> > Create;
   216     };
   217     };
   217 
   218 
   218     template <typename _Elevator>
   219     template <typename T>
   219     struct SetElevatorTraits : public Traits {
   220     struct SetElevatorTraits : public Traits {
   220       typedef _Elevator Elevator;
   221       typedef T Elevator;
   221       static Elevator *createElevator(const Digraph&, int) {
   222       static Elevator *createElevator(const Digraph&, int) {
   222         LEMON_ASSERT(false, "Elevator is not initialized");
   223         LEMON_ASSERT(false, "Elevator is not initialized");
   223         return 0; // ignore warnings
   224         return 0; // ignore warnings
   224       }
   225       }
   225     };
   226     };
   231     /// type. If this named parameter is used, then an external
   232     /// type. If this named parameter is used, then an external
   232     /// elevator object must be passed to the algorithm using the
   233     /// elevator object must be passed to the algorithm using the
   233     /// \ref elevator(Elevator&) "elevator()" function before calling
   234     /// \ref elevator(Elevator&) "elevator()" function before calling
   234     /// \ref run() or \ref init().
   235     /// \ref run() or \ref init().
   235     /// \sa SetStandardElevator
   236     /// \sa SetStandardElevator
   236     template <typename _Elevator>
   237     template <typename T>
   237     struct SetElevator
   238     struct SetElevator
   238       : public Preflow<Digraph, CapacityMap, SetElevatorTraits<_Elevator> > {
   239       : public Preflow<Digraph, CapacityMap, SetElevatorTraits<T> > {
   239       typedef Preflow<Digraph, CapacityMap,
   240       typedef Preflow<Digraph, CapacityMap,
   240                       SetElevatorTraits<_Elevator> > Create;
   241                       SetElevatorTraits<T> > Create;
   241     };
   242     };
   242 
   243 
   243     template <typename _Elevator>
   244     template <typename T>
   244     struct SetStandardElevatorTraits : public Traits {
   245     struct SetStandardElevatorTraits : public Traits {
   245       typedef _Elevator Elevator;
   246       typedef T Elevator;
   246       static Elevator *createElevator(const Digraph& digraph, int max_level) {
   247       static Elevator *createElevator(const Digraph& digraph, int max_level) {
   247         return new Elevator(digraph, max_level);
   248         return new Elevator(digraph, max_level);
   248       }
   249       }
   249     };
   250     };
   250 
   251 
   258     /// digraph and the maximum level should be passed to it).
   259     /// digraph and the maximum level should be passed to it).
   259     /// However an external elevator object could also be passed to the
   260     /// However an external elevator object could also be passed to the
   260     /// algorithm with the \ref elevator(Elevator&) "elevator()" function
   261     /// algorithm with the \ref elevator(Elevator&) "elevator()" function
   261     /// before calling \ref run() or \ref init().
   262     /// before calling \ref run() or \ref init().
   262     /// \sa SetElevator
   263     /// \sa SetElevator
   263     template <typename _Elevator>
   264     template <typename T>
   264     struct SetStandardElevator
   265     struct SetStandardElevator
   265       : public Preflow<Digraph, CapacityMap,
   266       : public Preflow<Digraph, CapacityMap,
   266                        SetStandardElevatorTraits<_Elevator> > {
   267                        SetStandardElevatorTraits<T> > {
   267       typedef Preflow<Digraph, CapacityMap,
   268       typedef Preflow<Digraph, CapacityMap,
   268                       SetStandardElevatorTraits<_Elevator> > Create;
   269                       SetStandardElevatorTraits<T> > Create;
   269     };
   270     };
   270 
   271 
   271     /// @}
   272     /// @}
   272 
   273 
   273   protected:
   274   protected:
   944     /// This method can be called both after running \ref startFirstPhase()
   945     /// This method can be called both after running \ref startFirstPhase()
   945     /// and \ref startSecondPhase(). The result after the second phase
   946     /// and \ref startSecondPhase(). The result after the second phase
   946     /// could be slightly different if inexact computation is used.
   947     /// could be slightly different if inexact computation is used.
   947     ///
   948     ///
   948     /// \note This function calls \ref minCut() for each node, so it runs in
   949     /// \note This function calls \ref minCut() for each node, so it runs in
   949     /// \f$O(n)\f$ time.
   950     /// O(n) time.
   950     ///
   951     ///
   951     /// \pre Either \ref run() or \ref init() must be called before
   952     /// \pre Either \ref run() or \ref init() must be called before
   952     /// using this function.
   953     /// using this function.
   953     template <typename CutMap>
   954     template <typename CutMap>
   954     void minCutMap(CutMap& cutMap) const {
   955     void minCutMap(CutMap& cutMap) const {