lemon/preflow.h
changeset 395 0c5dd7ceda03
parent 392 db3251947eba
child 420 6a2a33ad261b
equal deleted inserted replaced
3:b30313fcaa5f 4:492580ed5f8a
    29 namespace lemon {
    29 namespace lemon {
    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   /// \param _Graph Digraph type.
    34   /// \tparam _Digraph Digraph type.
    35   /// \param _CapacityMap Type of capacity map.
    35   /// \tparam _CapacityMap Capacity map type.
    36   template <typename _Graph, typename _CapacityMap>
    36   template <typename _Digraph, typename _CapacityMap>
    37   struct PreflowDefaultTraits {
    37   struct PreflowDefaultTraits {
    38 
    38 
    39     /// \brief The digraph type the algorithm runs on.
    39     /// \brief The type of the digraph the algorithm runs on.
    40     typedef _Graph Digraph;
    40     typedef _Digraph 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 _CapacityMap CapacityMap;
    46     typedef _CapacityMap CapacityMap;
    47 
    47 
    48     /// \brief The type of the length of the arcs.
    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 map type that stores the flow values.
    51     /// \brief The type of the map that stores the flow values.
    52     ///
    52     ///
    53     /// The map type that stores the flow values.
    53     /// The type of the map that stores the flow values.
    54     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    54     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    55     typedef typename Digraph::template ArcMap<Value> FlowMap;
    55     typedef typename Digraph::template ArcMap<Value> FlowMap;
    56 
    56 
    57     /// \brief Instantiates a FlowMap.
    57     /// \brief Instantiates a FlowMap.
    58     ///
    58     ///
    61     /// the flow map.
    61     /// the flow map.
    62     static FlowMap* createFlowMap(const Digraph& digraph) {
    62     static FlowMap* createFlowMap(const Digraph& digraph) {
    63       return new FlowMap(digraph);
    63       return new FlowMap(digraph);
    64     }
    64     }
    65 
    65 
    66     /// \brief The eleavator type used by Preflow algorithm.
    66     /// \brief The elevator type used by Preflow algorithm.
    67     ///
    67     ///
    68     /// The elevator type used by Preflow algorithm.
    68     /// The elevator type used by Preflow algorithm.
    69     ///
    69     ///
    70     /// \sa Elevator
    70     /// \sa Elevator
    71     /// \sa LinkedElevator
    71     /// \sa LinkedElevator
    72     typedef LinkedElevator<Digraph, typename Digraph::Node> Elevator;
    72     typedef LinkedElevator<Digraph, typename Digraph::Node> Elevator;
    73 
    73 
    74     /// \brief Instantiates an Elevator.
    74     /// \brief Instantiates an Elevator.
    75     ///
    75     ///
    76     /// This function instantiates a \ref Elevator.
    76     /// This function instantiates an \ref Elevator.
    77     /// \param digraph The digraph, to which we would like to define
    77     /// \param digraph The digraph, to which we would like to define
    78     /// the elevator.
    78     /// the elevator.
    79     /// \param max_level The maximum level of the elevator.
    79     /// \param max_level The maximum level of the elevator.
    80     static Elevator* createElevator(const Digraph& digraph, int max_level) {
    80     static Elevator* createElevator(const Digraph& digraph, int max_level) {
    81       return new Elevator(digraph, max_level);
    81       return new Elevator(digraph, max_level);
    89   };
    89   };
    90 
    90 
    91 
    91 
    92   /// \ingroup max_flow
    92   /// \ingroup max_flow
    93   ///
    93   ///
    94   /// \brief %Preflow algorithms class.
    94   /// \brief %Preflow algorithm class.
    95   ///
    95   ///
    96   /// This class provides an implementation of the Goldberg's \e
    96   /// This class provides an implementation of Goldberg-Tarjan's \e preflow
    97   /// preflow \e algorithm producing a flow of maximum value in a
    97   /// \e push-relabel algorithm producing a flow of maximum value in a
    98   /// digraph. The preflow algorithms are the fastest known max
    98   /// digraph. The preflow algorithms are the fastest known maximum
    99   /// flow algorithms. The current implementation use a mixture of the
    99   /// flow algorithms. The current implementation use a mixture of the
   100   /// \e "highest label" and the \e "bound decrease" heuristics.
   100   /// \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$.
   101   /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
   102   ///
   102   ///
   103   /// The algorithm consists from two phases. After the first phase
   103   /// The algorithm consists of two phases. After the first phase
   104   /// the maximal flow value and the minimum cut can be obtained. The
   104   /// the maximum flow value and the minimum cut is obtained. The
   105   /// second phase constructs the feasible maximum flow on each arc.
   105   /// second phase constructs a feasible maximum flow on each arc.
   106   ///
   106   ///
   107   /// \param _Graph The digraph type the algorithm runs on.
   107   /// \tparam _Digraph The type of the digraph the algorithm runs on.
   108   /// \param _CapacityMap The flow map type.
   108   /// \tparam _CapacityMap The type of the capacity map. The default map
   109   /// \param _Traits Traits class to set various data types used by
   109   /// type is \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<int>".
   110   /// the algorithm.  The default traits class is \ref
       
   111   /// PreflowDefaultTraits.  See \ref PreflowDefaultTraits for the
       
   112   /// documentation of a %Preflow traits class.
       
   113   ///
       
   114   ///\author Jacint Szabo and Balazs Dezso
       
   115 #ifdef DOXYGEN
   110 #ifdef DOXYGEN
   116   template <typename _Graph, typename _CapacityMap, typename _Traits>
   111   template <typename _Digraph, typename _CapacityMap, typename _Traits>
   117 #else
   112 #else
   118   template <typename _Graph,
   113   template <typename _Digraph,
   119             typename _CapacityMap = typename _Graph::template ArcMap<int>,
   114             typename _CapacityMap = typename _Digraph::template ArcMap<int>,
   120             typename _Traits = PreflowDefaultTraits<_Graph, _CapacityMap> >
   115             typename _Traits = PreflowDefaultTraits<_Digraph, _CapacityMap> >
   121 #endif
   116 #endif
   122   class Preflow {
   117   class Preflow {
   123   public:
   118   public:
   124 
   119 
       
   120     ///The \ref PreflowDefaultTraits "traits class" of the algorithm.
   125     typedef _Traits Traits;
   121     typedef _Traits Traits;
       
   122     ///The type of the digraph the algorithm runs on.
   126     typedef typename Traits::Digraph Digraph;
   123     typedef typename Traits::Digraph Digraph;
       
   124     ///The type of the capacity map.
   127     typedef typename Traits::CapacityMap CapacityMap;
   125     typedef typename Traits::CapacityMap CapacityMap;
       
   126     ///The type of the flow values.
   128     typedef typename Traits::Value Value;
   127     typedef typename Traits::Value Value;
   129 
   128 
       
   129     ///The type of the flow map.
   130     typedef typename Traits::FlowMap FlowMap;
   130     typedef typename Traits::FlowMap FlowMap;
       
   131     ///The type of the elevator.
   131     typedef typename Traits::Elevator Elevator;
   132     typedef typename Traits::Elevator Elevator;
       
   133     ///The type of the tolerance.
   132     typedef typename Traits::Tolerance Tolerance;
   134     typedef typename Traits::Tolerance Tolerance;
   133 
   135 
   134   private:
   136   private:
   135 
   137 
   136     TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   138     TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   186 
   188 
   187   public:
   189   public:
   188 
   190 
   189     typedef Preflow Create;
   191     typedef Preflow Create;
   190 
   192 
   191     ///\name Named template parameters
   193     ///\name Named Template Parameters
   192 
   194 
   193     ///@{
   195     ///@{
   194 
   196 
   195     template <typename _FlowMap>
   197     template <typename _FlowMap>
   196     struct SetFlowMapTraits : public Traits {
   198     struct SetFlowMapTraits : public Traits {
   203 
   205 
   204     /// \brief \ref named-templ-param "Named parameter" for setting
   206     /// \brief \ref named-templ-param "Named parameter" for setting
   205     /// FlowMap type
   207     /// FlowMap type
   206     ///
   208     ///
   207     /// \ref named-templ-param "Named parameter" for setting FlowMap
   209     /// \ref named-templ-param "Named parameter" for setting FlowMap
   208     /// type
   210     /// type.
   209     template <typename _FlowMap>
   211     template <typename _FlowMap>
   210     struct SetFlowMap
   212     struct SetFlowMap
   211       : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<_FlowMap> > {
   213       : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<_FlowMap> > {
   212       typedef Preflow<Digraph, CapacityMap,
   214       typedef Preflow<Digraph, CapacityMap,
   213                       SetFlowMapTraits<_FlowMap> > Create;
   215                       SetFlowMapTraits<_FlowMap> > Create;
   224 
   226 
   225     /// \brief \ref named-templ-param "Named parameter" for setting
   227     /// \brief \ref named-templ-param "Named parameter" for setting
   226     /// Elevator type
   228     /// Elevator type
   227     ///
   229     ///
   228     /// \ref named-templ-param "Named parameter" for setting Elevator
   230     /// \ref named-templ-param "Named parameter" for setting Elevator
   229     /// type
   231     /// type. If this named parameter is used, then an external
       
   232     /// elevator object must be passed to the algorithm using the
       
   233     /// \ref elevator(Elevator&) "elevator()" function before calling
       
   234     /// \ref run() or \ref init().
       
   235     /// \sa SetStandardElevator
   230     template <typename _Elevator>
   236     template <typename _Elevator>
   231     struct SetElevator
   237     struct SetElevator
   232       : public Preflow<Digraph, CapacityMap, SetElevatorTraits<_Elevator> > {
   238       : public Preflow<Digraph, CapacityMap, SetElevatorTraits<_Elevator> > {
   233       typedef Preflow<Digraph, CapacityMap,
   239       typedef Preflow<Digraph, CapacityMap,
   234                       SetElevatorTraits<_Elevator> > Create;
   240                       SetElevatorTraits<_Elevator> > Create;
   241         return new Elevator(digraph, max_level);
   247         return new Elevator(digraph, max_level);
   242       }
   248       }
   243     };
   249     };
   244 
   250 
   245     /// \brief \ref named-templ-param "Named parameter" for setting
   251     /// \brief \ref named-templ-param "Named parameter" for setting
   246     /// Elevator type
   252     /// Elevator type with automatic allocation
   247     ///
   253     ///
   248     /// \ref named-templ-param "Named parameter" for setting Elevator
   254     /// \ref named-templ-param "Named parameter" for setting Elevator
   249     /// type. The Elevator should be standard constructor interface, ie.
   255     /// type with automatic allocation.
   250     /// the digraph and the maximum level should be passed to it.
   256     /// The Elevator should have standard constructor interface to be
       
   257     /// able to automatically created by the algorithm (i.e. the
       
   258     /// digraph and the maximum level should be passed to it).
       
   259     /// However an external elevator object could also be passed to the
       
   260     /// algorithm with the \ref elevator(Elevator&) "elevator()" function
       
   261     /// before calling \ref run() or \ref init().
       
   262     /// \sa SetElevator
   251     template <typename _Elevator>
   263     template <typename _Elevator>
   252     struct SetStandardElevator
   264     struct SetStandardElevator
   253       : public Preflow<Digraph, CapacityMap,
   265       : public Preflow<Digraph, CapacityMap,
   254                        SetStandardElevatorTraits<_Elevator> > {
   266                        SetStandardElevatorTraits<_Elevator> > {
   255       typedef Preflow<Digraph, CapacityMap,
   267       typedef Preflow<Digraph, CapacityMap,
   271     /// \param digraph The digraph the algorithm runs on.
   283     /// \param digraph The digraph the algorithm runs on.
   272     /// \param capacity The capacity of the arcs.
   284     /// \param capacity The capacity of the arcs.
   273     /// \param source The source node.
   285     /// \param source The source node.
   274     /// \param target The target node.
   286     /// \param target The target node.
   275     Preflow(const Digraph& digraph, const CapacityMap& capacity,
   287     Preflow(const Digraph& digraph, const CapacityMap& capacity,
   276                Node source, Node target)
   288             Node source, Node target)
   277       : _graph(digraph), _capacity(&capacity),
   289       : _graph(digraph), _capacity(&capacity),
   278         _node_num(0), _source(source), _target(target),
   290         _node_num(0), _source(source), _target(target),
   279         _flow(0), _local_flow(false),
   291         _flow(0), _local_flow(false),
   280         _level(0), _local_level(false),
   292         _level(0), _local_level(false),
   281         _excess(0), _tolerance(), _phase() {}
   293         _excess(0), _tolerance(), _phase() {}
   282 
   294 
   283     /// \brief Destrcutor.
   295     /// \brief Destructor.
   284     ///
   296     ///
   285     /// Destructor.
   297     /// Destructor.
   286     ~Preflow() {
   298     ~Preflow() {
   287       destroyStructures();
   299       destroyStructures();
   288     }
   300     }
   289 
   301 
   290     /// \brief Sets the capacity map.
   302     /// \brief Sets the capacity map.
   291     ///
   303     ///
   292     /// Sets the capacity map.
   304     /// Sets the capacity map.
   293     /// \return \c (*this)
   305     /// \return <tt>(*this)</tt>
   294     Preflow& capacityMap(const CapacityMap& map) {
   306     Preflow& capacityMap(const CapacityMap& map) {
   295       _capacity = &map;
   307       _capacity = &map;
   296       return *this;
   308       return *this;
   297     }
   309     }
   298 
   310 
   299     /// \brief Sets the flow map.
   311     /// \brief Sets the flow map.
   300     ///
   312     ///
   301     /// Sets the flow map.
   313     /// Sets the flow map.
   302     /// \return \c (*this)
   314     /// If you don't use this function before calling \ref run() or
       
   315     /// \ref init(), an instance will be allocated automatically.
       
   316     /// The destructor deallocates this automatically allocated map,
       
   317     /// of course.
       
   318     /// \return <tt>(*this)</tt>
   303     Preflow& flowMap(FlowMap& map) {
   319     Preflow& flowMap(FlowMap& map) {
   304       if (_local_flow) {
   320       if (_local_flow) {
   305         delete _flow;
   321         delete _flow;
   306         _local_flow = false;
   322         _local_flow = false;
   307       }
   323       }
   308       _flow = &map;
   324       _flow = &map;
   309       return *this;
   325       return *this;
   310     }
   326     }
   311 
   327 
   312     /// \brief Returns the flow map.
   328     /// \brief Sets the source node.
   313     ///
   329     ///
   314     /// \return The flow map.
   330     /// Sets the source node.
   315     const FlowMap& flowMap() {
   331     /// \return <tt>(*this)</tt>
   316       return *_flow;
   332     Preflow& source(const Node& node) {
   317     }
   333       _source = node;
   318 
   334       return *this;
   319     /// \brief Sets the elevator.
   335     }
   320     ///
   336 
   321     /// Sets the elevator.
   337     /// \brief Sets the target node.
   322     /// \return \c (*this)
   338     ///
       
   339     /// Sets the target node.
       
   340     /// \return <tt>(*this)</tt>
       
   341     Preflow& target(const Node& node) {
       
   342       _target = node;
       
   343       return *this;
       
   344     }
       
   345 
       
   346     /// \brief Sets the elevator used by algorithm.
       
   347     ///
       
   348     /// Sets the elevator used by algorithm.
       
   349     /// If you don't use this function before calling \ref run() or
       
   350     /// \ref init(), an instance will be allocated automatically.
       
   351     /// The destructor deallocates this automatically allocated elevator,
       
   352     /// of course.
       
   353     /// \return <tt>(*this)</tt>
   323     Preflow& elevator(Elevator& elevator) {
   354     Preflow& elevator(Elevator& elevator) {
   324       if (_local_level) {
   355       if (_local_level) {
   325         delete _level;
   356         delete _level;
   326         _local_level = false;
   357         _local_level = false;
   327       }
   358       }
   328       _level = &elevator;
   359       _level = &elevator;
   329       return *this;
   360       return *this;
   330     }
   361     }
   331 
   362 
   332     /// \brief Returns the elevator.
   363     /// \brief Returns a const reference to the elevator.
   333     ///
   364     ///
   334     /// \return The elevator.
   365     /// Returns a const reference to the elevator.
       
   366     ///
       
   367     /// \pre Either \ref run() or \ref init() must be called before
       
   368     /// using this function.
   335     const Elevator& elevator() {
   369     const Elevator& elevator() {
   336       return *_level;
   370       return *_level;
   337     }
       
   338 
       
   339     /// \brief Sets the source node.
       
   340     ///
       
   341     /// Sets the source node.
       
   342     /// \return \c (*this)
       
   343     Preflow& source(const Node& node) {
       
   344       _source = node;
       
   345       return *this;
       
   346     }
       
   347 
       
   348     /// \brief Sets the target node.
       
   349     ///
       
   350     /// Sets the target node.
       
   351     /// \return \c (*this)
       
   352     Preflow& target(const Node& node) {
       
   353       _target = node;
       
   354       return *this;
       
   355     }
   371     }
   356 
   372 
   357     /// \brief Sets the tolerance used by algorithm.
   373     /// \brief Sets the tolerance used by algorithm.
   358     ///
   374     ///
   359     /// Sets the tolerance used by algorithm.
   375     /// Sets the tolerance used by algorithm.
   360     Preflow& tolerance(const Tolerance& tolerance) const {
   376     Preflow& tolerance(const Tolerance& tolerance) const {
   361       _tolerance = tolerance;
   377       _tolerance = tolerance;
   362       return *this;
   378       return *this;
   363     }
   379     }
   364 
   380 
   365     /// \brief Returns the tolerance used by algorithm.
   381     /// \brief Returns a const reference to the tolerance.
   366     ///
   382     ///
   367     /// Returns the tolerance used by algorithm.
   383     /// Returns a const reference to the tolerance.
   368     const Tolerance& tolerance() const {
   384     const Tolerance& tolerance() const {
   369       return tolerance;
   385       return tolerance;
   370     }
   386     }
   371 
   387 
   372     /// \name Execution control The simplest way to execute the
   388     /// \name Execution Control
   373     /// algorithm is to use one of the member functions called \c
   389     /// The simplest way to execute the preflow algorithm is to use
   374     /// run().
   390     /// \ref run() or \ref runMinCut().\n
   375     /// \n
   391     /// If you need more control on the initial solution or the execution,
   376     /// If you need more control on initial solution or
   392     /// first you have to call one of the \ref init() functions, then
   377     /// execution then you have to call one \ref init() function and then
   393     /// \ref startFirstPhase() and if you need it \ref startSecondPhase().
   378     /// the startFirstPhase() and if you need the startSecondPhase().
       
   379 
   394 
   380     ///@{
   395     ///@{
   381 
   396 
   382     /// \brief Initializes the internal data structures.
   397     /// \brief Initializes the internal data structures.
   383     ///
   398     ///
   384     /// Initializes the internal data structures.
   399     /// Initializes the internal data structures and sets the initial
   385     ///
   400     /// flow to zero on each arc.
   386     void init() {
   401     void init() {
   387       createStructures();
   402       createStructures();
   388 
   403 
   389       _phase = true;
   404       _phase = true;
   390       for (NodeIt n(_graph); n != INVALID; ++n) {
   405       for (NodeIt n(_graph); n != INVALID; ++n) {
   434           }
   449           }
   435         }
   450         }
   436       }
   451       }
   437     }
   452     }
   438 
   453 
   439     /// \brief Initializes the internal data structures.
   454     /// \brief Initializes the internal data structures using the
       
   455     /// given flow map.
   440     ///
   456     ///
   441     /// Initializes the internal data structures and sets the initial
   457     /// Initializes the internal data structures and sets the initial
   442     /// flow to the given \c flowMap. The \c flowMap should contain a
   458     /// flow to the given \c flowMap. The \c flowMap should contain a
   443     /// flow or at least a preflow, ie. in each node excluding the
   459     /// flow or at least a preflow, i.e. at each node excluding the
   444     /// target the incoming flow should greater or equal to the
   460     /// source node the incoming flow should greater or equal to the
   445     /// outgoing flow.
   461     /// outgoing flow.
   446     /// \return %False when the given \c flowMap is not a preflow.
   462     /// \return \c false if the given \c flowMap is not a preflow.
   447     template <typename FlowMap>
   463     template <typename FlowMap>
   448     bool init(const FlowMap& flowMap) {
   464     bool init(const FlowMap& flowMap) {
   449       createStructures();
   465       createStructures();
   450 
   466 
   451       for (ArcIt e(_graph); e != INVALID; ++e) {
   467       for (ArcIt e(_graph); e != INVALID; ++e) {
   534     /// the first phase. After the first phase the maximum flow value
   550     /// the first phase. After the first phase the maximum flow value
   535     /// and a minimum value cut can already be computed, although a
   551     /// and a minimum value cut can already be computed, although a
   536     /// maximum flow is not yet obtained. So after calling this method
   552     /// maximum flow is not yet obtained. So after calling this method
   537     /// \ref flowValue() returns the value of a maximum flow and \ref
   553     /// \ref flowValue() returns the value of a maximum flow and \ref
   538     /// minCut() returns a minimum cut.
   554     /// minCut() returns a minimum cut.
   539     /// \pre One of the \ref init() functions should be called.
   555     /// \pre One of the \ref init() functions must be called before
       
   556     /// using this function.
   540     void startFirstPhase() {
   557     void startFirstPhase() {
   541       _phase = true;
   558       _phase = true;
   542 
   559 
   543       Node n = _level->highestActive();
   560       Node n = _level->highestActive();
   544       int level = _level->highestActiveLevel();
   561       int level = _level->highestActiveLevel();
   700     }
   717     }
   701 
   718 
   702     /// \brief Starts the second phase of the preflow algorithm.
   719     /// \brief Starts the second phase of the preflow algorithm.
   703     ///
   720     ///
   704     /// The preflow algorithm consists of two phases, this method runs
   721     /// The preflow algorithm consists of two phases, this method runs
   705     /// the second phase. After calling \ref init() and \ref
   722     /// the second phase. After calling one of the \ref init() functions
   706     /// startFirstPhase() and then \ref startSecondPhase(), \ref
   723     /// and \ref startFirstPhase() and then \ref startSecondPhase(),
   707     /// flowMap() return a maximum flow, \ref flowValue() returns the
   724     /// \ref flowMap() returns a maximum flow, \ref flowValue() returns the
   708     /// value of a maximum flow, \ref minCut() returns a minimum cut
   725     /// value of a maximum flow, \ref minCut() returns a minimum cut
   709     /// \pre The \ref init() and startFirstPhase() functions should be
   726     /// \pre One of the \ref init() functions and \ref startFirstPhase()
   710     /// called before.
   727     /// must be called before using this function.
   711     void startSecondPhase() {
   728     void startSecondPhase() {
   712       _phase = false;
   729       _phase = false;
   713 
   730 
   714       typename Digraph::template NodeMap<bool> reached(_graph);
   731       typename Digraph::template NodeMap<bool> reached(_graph);
   715       for (NodeIt n(_graph); n != INVALID; ++n) {
   732       for (NodeIt n(_graph); n != INVALID; ++n) {
   861     }
   878     }
   862 
   879 
   863     /// @}
   880     /// @}
   864 
   881 
   865     /// \name Query Functions
   882     /// \name Query Functions
   866     /// The result of the %Preflow algorithm can be obtained using these
   883     /// The results of the preflow algorithm can be obtained using these
   867     /// functions.\n
   884     /// functions.\n
   868     /// Before the use of these functions,
   885     /// Either one of the \ref run() "run*()" functions or one of the
   869     /// either run() or start() must be called.
   886     /// \ref startFirstPhase() "start*()" functions should be called
       
   887     /// before using them.
   870 
   888 
   871     ///@{
   889     ///@{
   872 
   890 
   873     /// \brief Returns the value of the maximum flow.
   891     /// \brief Returns the value of the maximum flow.
   874     ///
   892     ///
   875     /// Returns the value of the maximum flow by returning the excess
   893     /// Returns the value of the maximum flow by returning the excess
   876     /// of the target node \c t. This value equals to the value of
   894     /// of the target node. This value equals to the value of
   877     /// the maximum flow already after the first phase.
   895     /// the maximum flow already after the first phase of the algorithm.
       
   896     ///
       
   897     /// \pre Either \ref run() or \ref init() must be called before
       
   898     /// using this function.
   878     Value flowValue() const {
   899     Value flowValue() const {
   879       return (*_excess)[_target];
   900       return (*_excess)[_target];
   880     }
   901     }
   881 
   902 
   882     /// \brief Returns true when the node is on the source side of minimum cut.
   903     /// \brief Returns the flow on the given arc.
   883     ///
   904     ///
   884     /// Returns true when the node is on the source side of minimum
   905     /// Returns the flow on the given arc. This method can
   885     /// cut. This method can be called both after running \ref
   906     /// be called after the second phase of the algorithm.
       
   907     ///
       
   908     /// \pre Either \ref run() or \ref init() must be called before
       
   909     /// using this function.
       
   910     Value flow(const Arc& arc) const {
       
   911       return (*_flow)[arc];
       
   912     }
       
   913 
       
   914     /// \brief Returns a const reference to the flow map.
       
   915     ///
       
   916     /// Returns a const reference to the arc map storing the found flow.
       
   917     /// This method can be called after the second phase of the algorithm.
       
   918     ///
       
   919     /// \pre Either \ref run() or \ref init() must be called before
       
   920     /// using this function.
       
   921     const FlowMap& flowMap() {
       
   922       return *_flow;
       
   923     }
       
   924 
       
   925     /// \brief Returns \c true when the node is on the source side of the
       
   926     /// minimum cut.
       
   927     ///
       
   928     /// Returns true when the node is on the source side of the found
       
   929     /// minimum cut. This method can be called both after running \ref
   886     /// startFirstPhase() and \ref startSecondPhase().
   930     /// startFirstPhase() and \ref startSecondPhase().
       
   931     ///
       
   932     /// \pre Either \ref run() or \ref init() must be called before
       
   933     /// using this function.
   887     bool minCut(const Node& node) const {
   934     bool minCut(const Node& node) const {
   888       return ((*_level)[node] == _level->maxLevel()) == _phase;
   935       return ((*_level)[node] == _level->maxLevel()) == _phase;
   889     }
   936     }
   890 
   937 
   891     /// \brief Returns a minimum value cut.
   938     /// \brief Gives back a minimum value cut.
   892     ///
   939     ///
   893     /// Sets the \c cutMap to the characteristic vector of a minimum value
   940     /// Sets \c cutMap to the characteristic vector of a minimum value
   894     /// cut. This method can be called both after running \ref
   941     /// cut. \c cutMap should be a \ref concepts::WriteMap "writable"
   895     /// startFirstPhase() and \ref startSecondPhase(). The result after second
   942     /// node map with \c bool (or convertible) value type.
   896     /// phase could be changed slightly if inexact computation is used.
   943     ///
   897     /// \pre The \c cutMap should be a bool-valued node-map.
   944     /// This method can be called both after running \ref startFirstPhase()
       
   945     /// and \ref startSecondPhase(). The result after the second phase
       
   946     /// could be slightly different if inexact computation is used.
       
   947     ///
       
   948     /// \note This function calls \ref minCut() for each node, so it runs in
       
   949     /// \f$O(n)\f$ time.
       
   950     ///
       
   951     /// \pre Either \ref run() or \ref init() must be called before
       
   952     /// using this function.
   898     template <typename CutMap>
   953     template <typename CutMap>
   899     void minCutMap(CutMap& cutMap) const {
   954     void minCutMap(CutMap& cutMap) const {
   900       for (NodeIt n(_graph); n != INVALID; ++n) {
   955       for (NodeIt n(_graph); n != INVALID; ++n) {
   901         cutMap.set(n, minCut(n));
   956         cutMap.set(n, minCut(n));
   902       }
   957       }
   903     }
   958     }
   904 
   959 
   905     /// \brief Returns the flow on the arc.
       
   906     ///
       
   907     /// Sets the \c flowMap to the flow on the arcs. This method can
       
   908     /// be called after the second phase of algorithm.
       
   909     Value flow(const Arc& arc) const {
       
   910       return (*_flow)[arc];
       
   911     }
       
   912 
       
   913     /// @}
   960     /// @}
   914   };
   961   };
   915 }
   962 }
   916 
   963 
   917 #endif
   964 #endif