RhodeCode

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_CIRCULATION_H

#define LEMON_CIRCULATION_H

#include <lemon/tolerance.h>

#include <lemon/elevator.h>

///\ingroup max_flow

///\file

///\brief Push-relabel algorithm for finding a feasible circulation.

///

namespace lemon {

  /// \brief Default traits class of Circulation class.

  ///

  /// Default traits class of Circulation class.

  template <typename GR, typename LM,

  struct CirculationDefaultTraits {

    /// \brief The type of the digraph the algorithm runs on.

    typedef GR Digraph;

    ///

    ///

    ///

    /// \brief The type of the flow values.

    /// \brief The type of the map that stores the flow values.

    ///

    /// The type of the map that stores the flow values.

    /// \brief Instantiates a FlowMap.

    ///

    /// This function instantiates a \ref FlowMap.

    /// the flow map.

    static FlowMap* createFlowMap(const Digraph& digraph) {

      return new FlowMap(digraph);

    }

    /// \brief The elevator type used by the algorithm.

    ///

    /// The elevator type used by the algorithm.

    ///

    /// \sa Elevator

    /// \sa LinkedElevator

    typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;

    /// \brief Instantiates an Elevator.

    ///

    /// This function instantiates an \ref Elevator.

    /// the elevator.

    /// \param max_level The maximum level of the elevator.

    static Elevator* createElevator(const Digraph& digraph, int max_level) {

      return new Elevator(digraph, max_level);

    }

    /// \brief The tolerance used by the algorithm

    ///

    /// The tolerance used by the algorithm to handle inexact computation.

  };

  /**

     \brief Push-relabel algorithm for the network circulation problem.

     \ingroup max_flow

     It is to find a feasible circulation when lower and upper bounds

     The exact formulation of this problem is the following.

     Let \f$G=(V,A)\f$ be a digraph,

     \tparam GR The type of the digraph the algorithm runs on.

     map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".

     \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".

  */

#ifdef DOXYGEN

template< typename GR,

          typename LM,

          typename UM,

          typename TR >

#else

template< typename GR,

          typename LM = typename GR::template ArcMap<int>,

          typename UM = LM,

#endif

  class Circulation {

  public:

    ///The \ref CirculationDefaultTraits "traits class" of the algorithm.

    typedef TR Traits;

    ///The type of the digraph the algorithm runs on.

    typedef typename Traits::Digraph Digraph;

    ///The type of the flow values.

    ///The type of the flow map.

    typedef typename Traits::FlowMap FlowMap;

    ///The type of the elevator.

    typedef typename Traits::Elevator Elevator;

    ///The type of the tolerance.

    typedef typename Traits::Tolerance Tolerance;

  private:

    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

    const Digraph &_g;

    int _node_num;

    FlowMap *_flow;

    bool _local_flow;

    Elevator* _level;

    bool _local_level;

    ExcessMap* _excess;

    Tolerance _tol;

    int _el;

  public:

    typedef Circulation Create;

    ///\name Named Template Parameters

    ///@{

    template <typename _FlowMap>

    struct SetFlowMapTraits : public Traits {

      typedef _FlowMap FlowMap;

      static FlowMap *createFlowMap(const Digraph&) {

        LEMON_ASSERT(false, "FlowMap is not initialized");

        return 0; // ignore warnings

      }

    };

    /// \brief \ref named-templ-param "Named parameter" for setting

    /// FlowMap type

    ///

    /// \ref named-templ-param "Named parameter" for setting FlowMap

    /// type.

    template <typename _FlowMap>

    struct SetFlowMap

                           SetFlowMapTraits<_FlowMap> > {

                          SetFlowMapTraits<_FlowMap> > Create;

    };

    template <typename _Elevator>

    struct SetElevatorTraits : public Traits {

      typedef _Elevator Elevator;

      static Elevator *createElevator(const Digraph&, int) {

        LEMON_ASSERT(false, "Elevator is not initialized");

        return 0; // ignore warnings

      }

    };

    /// \brief \ref named-templ-param "Named parameter" for setting

    /// Elevator type

    ///

    /// \ref named-templ-param "Named parameter" for setting Elevator

    /// type. If this named parameter is used, then an external

    /// elevator object must be passed to the algorithm using the

    /// \ref elevator(Elevator&) "elevator()" function before calling

    /// \ref run() or \ref init().

    /// \sa SetStandardElevator

    template <typename _Elevator>

    struct SetElevator

                           SetElevatorTraits<_Elevator> > {

                          SetElevatorTraits<_Elevator> > Create;

    };

    template <typename _Elevator>

    struct SetStandardElevatorTraits : public Traits {

      typedef _Elevator Elevator;

      static Elevator *createElevator(const Digraph& digraph, int max_level) {

        return new Elevator(digraph, max_level);

      }

    };

    /// \brief \ref named-templ-param "Named parameter" for setting

    /// Elevator type with automatic allocation

    ///

    /// \ref named-templ-param "Named parameter" for setting Elevator

    /// type with automatic allocation.

    /// The Elevator should have standard constructor interface to be

    /// able to automatically created by the algorithm (i.e. the

    /// digraph and the maximum level should be passed to it).

    /// However an external elevator object could also be passed to the

    /// algorithm with the \ref elevator(Elevator&) "elevator()" function

    /// before calling \ref run() or \ref init().

    /// \sa SetElevator

    template <typename _Elevator>

    struct SetStandardElevator

                       SetStandardElevatorTraits<_Elevator> > {

                      SetStandardElevatorTraits<_Elevator> > Create;

    };

    /// @}

  protected:

    Circulation() {}

  public:

    /// The constructor of the class.

    /// Destructor.

    ~Circulation() {

      destroyStructures();

    }

  private:

    void createStructures() {

      _node_num = _el = countNodes(_g);

      if (!_flow) {

        _flow = Traits::createFlowMap(_g);

        _local_flow = true;

      }

      if (!_level) {

        _level = Traits::createElevator(_g, _node_num);

        _local_level = true;

      }

      if (!_excess) {

        _excess = new ExcessMap(_g);

      }

    }

    void destroyStructures() {

      if (_local_flow) {

        delete _flow;

      }

      if (_local_level) {

        delete _level;

      }

      if (_excess) {

        delete _excess;

      }

    }

  public:

    /// \return <tt>(*this)</tt>

      _lo = ↦

      return *this;

    }

    /// \return <tt>(*this)</tt>

      _up = ↦

      return *this;

    }

    /// \return <tt>(*this)</tt>

      return *this;

    }

    /// \brief Sets the flow map.

    ///

    /// Sets the flow map.

    /// If you don't use this function before calling \ref run() or

    /// \ref init(), an instance will be allocated automatically.

    /// The destructor deallocates this automatically allocated map,

    /// of course.

    /// \return <tt>(*this)</tt>

    Circulation& flowMap(FlowMap& map) {

      if (_local_flow) {

        delete _flow;

        _local_flow = false;

      }

      _flow = ↦

      return *this;

    }

    /// \brief Sets the elevator used by algorithm.

    ///

    /// Sets the elevator used by algorithm.

    /// If you don't use this function before calling \ref run() or

    /// \brief Returns a const reference to the tolerance.

    ///

    /// Returns a const reference to the tolerance.

    const Tolerance& tolerance() const {

      return tolerance;

    }

    /// \name Execution Control

    /// The simplest way to execute the algorithm is to call \ref run().\n

    /// If you need more control on the initial solution or the execution,

    /// first you have to call one of the \ref init() functions, then

    /// the \ref start() function.

    ///@{

    /// Initializes the internal data structures.

    /// Initializes the internal data structures and sets all flow values

    /// to the lower bound.

    void init()

    {

      createStructures();

      for(NodeIt n(_g);n!=INVALID;++n) {

      }

      for (ArcIt e(_g);e!=INVALID;++e) {

        _flow->set(e, (*_lo)[e]);

        _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_flow)[e]);

        _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_flow)[e]);

      }

      // global relabeling tested, but in general case it provides

      // worse performance for random digraphs

      _level->initStart();

      for(NodeIt n(_g);n!=INVALID;++n)

        _level->initAddItem(n);

      _level->initFinish();

      for(NodeIt n(_g);n!=INVALID;++n)

        if(_tol.positive((*_excess)[n]))

          _level->activate(n);

    }

    /// Initializes the internal data structures using a greedy approach.

    /// Initializes the internal data structures using a greedy approach

    /// to construct the initial solution.

    void greedyInit()

    {

      createStructures();

      for(NodeIt n(_g);n!=INVALID;++n) {

      }

      for (ArcIt e(_g);e!=INVALID;++e) {

        if (!_tol.positive((*_excess)[_g.target(e)] + (*_up)[e])) {

          _flow->set(e, (*_up)[e]);

          _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_up)[e]);

          _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_up)[e]);

        } else if (_tol.positive((*_excess)[_g.target(e)] + (*_lo)[e])) {

          _flow->set(e, (*_lo)[e]);

          _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_lo)[e]);

          _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_lo)[e]);

        } else {

          _flow->set(e, fc);

          _excess->set(_g.target(e), 0);

          _excess->set(_g.source(e), (*_excess)[_g.source(e)] - fc);

        }

      }

      _level->initStart();

      for(NodeIt n(_g);n!=INVALID;++n)

        _level->initAddItem(n);

      _level->initFinish();

      for(NodeIt n(_g);n!=INVALID;++n)

        if(_tol.positive((*_excess)[n]))

          _level->activate(n);

    }

    ///Executes the algorithm

    ///This function executes the algorithm.

    ///

    ///\return \c true if a feasible circulation is found.

    ///

    ///\sa barrier()

    ///\sa barrierMap()

    bool start()

    {

      Node act;

      Node bact=INVALID;

      Node last_activated=INVALID;

      while((act=_level->highestActive())!=INVALID) {

        int actlevel=(*_level)[act];

        int mlevel=_node_num;

        for(OutArcIt e(_g,act);e!=INVALID; ++e) {

          Node v = _g.target(e);

          if(!_tol.positive(fc)) continue;

          if((*_level)[v]<actlevel) {

            if(!_tol.less(fc, exc)) {

              _flow->set(e, (*_flow)[e] + exc);

              _excess->set(v, (*_excess)[v] + exc);

              if(!_level->active(v) && _tol.positive((*_excess)[v]))

                _level->activate(v);

              _excess->set(act,0);

              _level->deactivate(act);

              goto next_l;

            }

            else {

              _flow->set(e, (*_up)[e]);

              _excess->set(v, (*_excess)[v] + fc);

              if(!_level->active(v) && _tol.positive((*_excess)[v]))

                _level->activate(v);

              exc-=fc;

            }

          }

          else if((*_level)[v]<mlevel) mlevel=(*_level)[v];

        }

        for(InArcIt e(_g,act);e!=INVALID; ++e) {

          Node v = _g.source(e);

          if(!_tol.positive(fc)) continue;

          if((*_level)[v]<actlevel) {

            if(!_tol.less(fc, exc)) {

              _flow->set(e, (*_flow)[e] - exc);

              _excess->set(v, (*_excess)[v] + exc);

              if(!_level->active(v) && _tol.positive((*_excess)[v]))

                _level->activate(v);

              _excess->set(act,0);

              _level->deactivate(act);

              goto next_l;

            }

            else {

              _flow->set(e, (*_lo)[e]);

              _excess->set(v, (*_excess)[v] + fc);

              if(!_level->active(v) && _tol.positive((*_excess)[v]))

                _level->activate(v);

              exc-=fc;

            }

          }

          else if((*_level)[v]<mlevel) mlevel=(*_level)[v];

        }

        _excess->set(act, exc);

        if(!_tol.positive(exc)) _level->deactivate(act);

    ///   c.greedyInit();

    ///   c.start();

    /// \endcode

    bool run() {

      greedyInit();

      return start();

    }

    /// @}

    /// \name Query Functions

    /// The results of the circulation algorithm can be obtained using

    /// these functions.\n

    /// Either \ref run() or \ref start() should be called before

    /// using them.

    ///@{

    /// \brief Returns the flow on the given arc.

    ///

    /// Returns the flow on the given arc.

    ///

    /// \pre Either \ref run() or \ref init() must be called before

    /// using this function.

      return (*_flow)[arc];

    }

    /// \brief Returns a const reference to the flow map.

    ///

    /// Returns a const reference to the arc map storing the found flow.

    ///

    /// \pre Either \ref run() or \ref init() must be called before

    /// using this function.

    const FlowMap& flowMap() const {

      return *_flow;

    }

    /**

       \brief Returns \c true if the given node is in a barrier.

       Barrier is a set \e B of nodes for which

       holds. The existence of a set with this property prooves that a

       feasible circualtion cannot exist.

       This function returns \c true if the given node is in the found

       barrier. If a feasible circulation is found, the function

       gives back \c false for every node.

       \pre Either \ref run() or \ref init() must be called before

       using this function.

       \sa barrierMap()

       \sa checkBarrier()

    */

    bool barrier(const Node& node) const

    {

      return (*_level)[node] >= _el;

    }

    /// \brief Gives back a barrier.

    ///

    /// This function sets \c bar to the characteristic vector of the

    /// found barrier. \c bar should be a \ref concepts::WriteMap "writable"

    /// node map with \c bool (or convertible) value type.

    {

      for(NodeIt n(_g);n!=INVALID;++n)

        bar.set(n, (*_level)[n] >= _el);

    }

    /// @}

    /// \name Checker Functions

    /// The feasibility of the results can be checked using

    /// these functions.\n

    /// Either \ref run() or \ref start() should be called before

    /// using them.

    ///@{

    ///Check if the found flow is a feasible circulation

    ///Check if the found flow is a feasible circulation,

    ///

    bool checkFlow() const {

      for(ArcIt e(_g);e!=INVALID;++e)

        if((*_flow)[e]<(*_lo)[e]||(*_flow)[e]>(*_up)[e]) return false;

      for(NodeIt n(_g);n!=INVALID;++n)

        {

          for(InArcIt e(_g,n);e!=INVALID;++e) dif-=(*_flow)[e];

          for(OutArcIt e(_g,n);e!=INVALID;++e) dif+=(*_flow)[e];

          if(_tol.negative(dif)) return false;

        }

      return true;

    }

    ///Check whether or not the last execution provides a barrier

    ///Check whether or not the last execution provides a barrier.

    ///\sa barrier()

    ///\sa barrierMap()

    bool checkBarrier() const

    {

      for(NodeIt n(_g);n!=INVALID;++n)

        if(barrier(n))

      for(ArcIt e(_g);e!=INVALID;++e)

        {

          Node s=_g.source(e);

          Node t=_g.target(e);

          if(barrier(s)&&!barrier(t)) delta+=(*_up)[e];

          else if(barrier(t)&&!barrier(s)) delta-=(*_lo)[e];

        }

      return _tol.negative(delta);

    }

    /// @}

  };

}

#endif

/// \file

/// \ingroup max_flow

/// \brief Implementation of the preflow algorithm.

namespace lemon {

  /// \brief Default traits class of Preflow class.

  ///

  /// Default traits class of Preflow class.

  /// \tparam GR Digraph type.

  /// \tparam CM Capacity map type.

  template <typename GR, typename CM>

  struct PreflowDefaultTraits {

    /// \brief The type of the digraph the algorithm runs on.

    typedef GR Digraph;

    /// \brief The type of the map that stores the arc capacities.

    ///

    /// The type of the map that stores the arc capacities.

    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.

    typedef CM CapacityMap;

    /// \brief The type of the flow values.

    /// \brief The type of the map that stores the flow values.

    ///

    /// The type of the map that stores the flow values.

    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.

    /// \brief Instantiates a FlowMap.

    ///

    /// This function instantiates a \ref FlowMap.

    /// the flow map.

    static FlowMap* createFlowMap(const Digraph& digraph) {

      return new FlowMap(digraph);

    }

    /// \brief The elevator type used by Preflow algorithm.

    ///

    /// The elevator type used by Preflow algorithm.

    ///

    /// \sa Elevator

    /// \sa LinkedElevator

    typedef LinkedElevator<Digraph, typename Digraph::Node> Elevator;

    /// \brief Instantiates an Elevator.

    ///

    /// This function instantiates an \ref Elevator.

    /// the elevator.

    /// \param max_level The maximum level of the elevator.

    static Elevator* createElevator(const Digraph& digraph, int max_level) {

      return new Elevator(digraph, max_level);

    }

    /// \brief The tolerance used by the algorithm

    ///

    /// The tolerance used by the algorithm to handle inexact computation.

  };

  /// \ingroup max_flow

  ///

  /// \brief %Preflow algorithm class.

  ///

  /// This class provides an implementation of Goldberg-Tarjan's \e preflow

  /// \e push-relabel algorithm producing a flow of maximum value in a

  /// digraph. The preflow algorithms are the fastest known maximum

  /// flow algorithms. The current implementation use a mixture of the

  /// \e "highest label" and the \e "bound decrease" heuristics.

  /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.

  ///

  /// The algorithm consists of two phases. After the first phase

  /// the maximum flow value and the minimum cut is obtained. The

  /// second phase constructs a feasible maximum flow on each arc.

  ///

  /// \tparam GR The type of the digraph the algorithm runs on.

  /// \tparam CM The type of the capacity map. The default map

  /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".

#ifdef DOXYGEN

  template <typename GR, typename CM, typename TR>

#else

  template <typename GR,

            typename CM = typename GR::template ArcMap<int>,

            typename TR = PreflowDefaultTraits<GR, CM> >

#endif

  class Preflow {

  public:

    ///The \ref PreflowDefaultTraits "traits class" of the algorithm.

    typedef TR Traits;

    ///The type of the digraph the algorithm runs on.

    typedef typename Traits::Digraph Digraph;

    ///The type of the capacity map.

    typedef typename Traits::CapacityMap CapacityMap;

    ///The type of the flow values.

    ///The type of the flow map.

    typedef typename Traits::FlowMap FlowMap;

    ///The type of the elevator.

    typedef typename Traits::Elevator Elevator;

    ///The type of the tolerance.

    typedef typename Traits::Tolerance Tolerance;

  private:

    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

    const Digraph& _graph;

    const CapacityMap* _capacity;

    int _node_num;

    Node _source, _target;

    FlowMap* _flow;

    bool _local_flow;

    Elevator* _level;

    bool _local_level;

    ExcessMap* _excess;

    Tolerance _tolerance;

    bool _phase;

    void createStructures() {

      _node_num = countNodes(_graph);

      if (!_flow) {

        _flow = Traits::createFlowMap(_graph);

        _local_flow = true;

      }

      if (!_level) {

        _level = Traits::createElevator(_graph, _node_num);

        _local_level = true;

      }

      if (!_excess) {

        _excess = new ExcessMap(_graph);

      }

    }

    void destroyStructures() {

            _level->activate(u);

          }

        }

      }

    }

    /// \brief Initializes the internal data structures using the

    /// given flow map.

    ///

    /// Initializes the internal data structures and sets the initial

    /// flow to the given \c flowMap. The \c flowMap should contain a

    /// flow or at least a preflow, i.e. at each node excluding the

    /// source node the incoming flow should greater or equal to the

    /// outgoing flow.

    /// \return \c false if the given \c flowMap is not a preflow.

    template <typename FlowMap>

    bool init(const FlowMap& flowMap) {

      createStructures();

      for (ArcIt e(_graph); e != INVALID; ++e) {

        _flow->set(e, flowMap[e]);

      }

      for (NodeIt n(_graph); n != INVALID; ++n) {

        for (InArcIt e(_graph, n); e != INVALID; ++e) {

          excess += (*_flow)[e];

        }

        for (OutArcIt e(_graph, n); e != INVALID; ++e) {

          excess -= (*_flow)[e];

        }

        if (excess < 0 && n != _source) return false;

        _excess->set(n, excess);

      }

      typename Digraph::template NodeMap<bool> reached(_graph, false);

      _level->initStart();

      _level->initAddItem(_target);

      std::vector<Node> queue;

      reached.set(_source, true);

      queue.push_back(_target);

      reached.set(_target, true);

      while (!queue.empty()) {

        _level->initNewLevel();

        std::vector<Node> nqueue;

        for (int i = 0; i < int(queue.size()); ++i) {

          Node n = queue[i];

          for (InArcIt e(_graph, n); e != INVALID; ++e) {

            Node u = _graph.source(e);

            if (!reached[u] &&

                _tolerance.positive((*_capacity)[e] - (*_flow)[e])) {

              reached.set(u, true);

              _level->initAddItem(u);

              nqueue.push_back(u);

            }

          }

          for (OutArcIt e(_graph, n); e != INVALID; ++e) {

            Node v = _graph.target(e);

            if (!reached[v] && _tolerance.positive((*_flow)[e])) {

              reached.set(v, true);

              _level->initAddItem(v);

              nqueue.push_back(v);

            }

          }

        }

        queue.swap(nqueue);

      }

      _level->initFinish();

      for (OutArcIt e(_graph, _source); e != INVALID; ++e) {

        if (_tolerance.positive(rem)) {

          Node u = _graph.target(e);

          if ((*_level)[u] == _level->maxLevel()) continue;

          _flow->set(e, (*_capacity)[e]);

          _excess->set(u, (*_excess)[u] + rem);

          if (u != _target && !_level->active(u)) {

            _level->activate(u);

          }

        }

      }

      for (InArcIt e(_graph, _source); e != INVALID; ++e) {

        if (_tolerance.positive(rem)) {

          Node v = _graph.source(e);

          if ((*_level)[v] == _level->maxLevel()) continue;

          _flow->set(e, 0);

          _excess->set(v, (*_excess)[v] + rem);

          if (v != _target && !_level->active(v)) {

            _level->activate(v);

          }

        }

      }

      return true;

    }

    /// \brief Starts the first phase of the preflow algorithm.

    ///

    /// The preflow algorithm consists of two phases, this method runs

    /// the first phase. After the first phase the maximum flow value

    /// and a minimum value cut can already be computed, although a

    /// maximum flow is not yet obtained. So after calling this method

    /// \ref flowValue() returns the value of a maximum flow and \ref

    /// minCut() returns a minimum cut.

    /// \pre One of the \ref init() functions must be called before

    /// using this function.

    void startFirstPhase() {

      _phase = true;

      Node n = _level->highestActive();

      int level = _level->highestActiveLevel();

      while (n != INVALID) {

        int num = _node_num;

        while (num > 0 && n != INVALID) {

          int new_level = _level->maxLevel();

          for (OutArcIt e(_graph, n); e != INVALID; ++e) {

            if (!_tolerance.positive(rem)) continue;

            Node v = _graph.target(e);