RhodeCode

    /// \brief Instantiates a FlowMap.

    ///

    /// This function instantiates a \ref FlowMap.

    /// \param digraph The digraph, to which we would like to define

    /// the flow map.

    static FlowMap* createFlowMap(const Digraph& digraph) {

      return new FlowMap(digraph);

    }

    /// \brief The eleavator type used by Circulation algorithm.

    ///

    /// The elevator type used by Circulation algorithm.

    ///

    /// \sa Elevator

    /// \sa LinkedElevator

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

    /// \brief Instantiates an Elevator.

    ///

    /// This function instantiates a \ref Elevator.

    /// \param digraph The digraph, to which we would like to define

    /// 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.

    typedef lemon::Tolerance<Value> Tolerance;

  };

  ///Push-relabel algorithm for the Network Circulation Problem.

  /**

     \ingroup max_flow

     This class implements a push-relabel algorithm

     or the Network Circulation Problem.

     The exact formulation of this problem is the following.

     \f[\sum_{e\in\rho(v)}x(e)-\sum_{e\in\delta(v)}x(e)\leq

     -delta(v)\quad \forall v\in V \f]

     \f[ lo(e)\leq x(e) \leq up(e) \quad \forall e\in E \f]

  */

  template<class _Graph,

           class _LCapMap=typename _Graph::template ArcMap<int>,

           class _UCapMap=_LCapMap,

           class _DeltaMap=typename _Graph::template NodeMap<

             typename _UCapMap::Value>,

           class _Traits=CirculationDefaultTraits<_Graph, _LCapMap,

                                                  _UCapMap, _DeltaMap> >

  class Circulation {

    typedef _Traits Traits;

    typedef typename Traits::Digraph Digraph;

    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

    typedef typename Traits::Value Value;

    typedef typename Traits::LCapMap LCapMap;

    typedef typename Traits::UCapMap UCapMap;

    typedef typename Traits::DeltaMap DeltaMap;

    typedef typename Traits::FlowMap FlowMap;

    typedef typename Traits::Elevator Elevator;

    typedef typename Traits::Tolerance Tolerance;

    typedef typename Digraph::template NodeMap<Value> ExcessMap;

    const Digraph &_g;

    int _node_num;

    const LCapMap *_lo;

    const UCapMap *_up;

    const DeltaMap *_delta;

    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>

      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>

      : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,

      typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,

    };

    template <typename _Elevator>

      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

    template <typename _Elevator>

      : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,

      typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,

    };

    template <typename _Elevator>

      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

    ///

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

    /// type. The Elevator should be standard constructor interface, ie.

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

    template <typename _Elevator>

      : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,

      typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,

    };

    /// @}

  protected:

    Circulation() {}

  public:

    /// The constructor of the class.

    /// The constructor of the class.

    /// \param g The digraph the algorithm runs on.

    /// \param lo The lower bound capacity of the arcs.

    /// \param up The upper bound capacity of the arcs.

    /// \param delta The lower bound on node excess.

    Circulation(const Digraph &g,const LCapMap &lo,

                const UCapMap &up,const DeltaMap &delta)

      : _g(g), _node_num(),

        _lo(&lo),_up(&up),_delta(&delta),_flow(0),_local_flow(false),

        _level(0), _local_level(false), _excess(0), _el() {}

    /// Destrcutor.

    ~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:

    /// Sets the lower bound capacity map.

    /// Sets the lower bound capacity map.

    /// \return \c (*this)

    Circulation& lowerCapMap(const LCapMap& map) {

      _lo = ↦

      return *this;

    }

    /// Sets the upper bound capacity map.

    /// Sets the upper bound capacity map.

    /// \return \c (*this)

    Circulation& upperCapMap(const LCapMap& map) {

      _up = ↦

      return *this;

    }

    /// Sets the lower bound map on excess.

    /// Sets the lower bound map on excess.

    /// \return \c (*this)

    Circulation& deltaMap(const DeltaMap& map) {

      _delta = ↦

      return *this;

    }

    /// Sets the flow map.

    /// Sets the flow map.

    /// \return \c (*this)

    Circulation& flowMap(FlowMap& map) {

      if (_local_flow) {

        delete _flow;

        _local_flow = false;

      }