RhodeCode

#include <lemon/tolerance.h>

#include <lemon/elevator.h>

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

  struct PreflowDefaultTraits {

    /// \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 _CapacityMap CapacityMap;

    typedef typename CapacityMap::Value Value;

    ///

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

    typedef typename Digraph::template ArcMap<Value> FlowMap;

    /// \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);

    }

    ///

    /// The elevator type used by Preflow algorithm.

    ///

    /// \sa Elevator

    /// \sa LinkedElevator

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

    /// \brief Instantiates an 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;

  };

  /// \ingroup max_flow

  ///

  ///

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

  ///

  ///

#ifdef DOXYGEN

#else

#endif

  class Preflow {

  public:

    typedef _Traits Traits;

    typedef typename Traits::Digraph Digraph;

    typedef typename Traits::CapacityMap CapacityMap;

    typedef typename Traits::Value Value;

    typedef typename Traits::FlowMap FlowMap;

    typedef typename Traits::Elevator Elevator;

    typedef typename Traits::Tolerance Tolerance;

  private:

    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

    const Digraph& _graph;

    const CapacityMap* _capacity;

    int _node_num;

    Node _source, _target;

      if (_local_level) {

        delete _level;

      }

      if (_excess) {

        delete _excess;

      }

    }

  public:

    typedef Preflow Create;

    ///@{

    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

    template <typename _FlowMap>

    struct SetFlowMap

      : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<_FlowMap> > {

      typedef Preflow<Digraph, CapacityMap,

                      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

    template <typename _Elevator>

    struct SetElevator

      : public Preflow<Digraph, CapacityMap, SetElevatorTraits<_Elevator> > {

      typedef Preflow<Digraph, CapacityMap,

                      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

    ///

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

    template <typename _Elevator>

    struct SetStandardElevator

      : public Preflow<Digraph, CapacityMap,

                       SetStandardElevatorTraits<_Elevator> > {

      typedef Preflow<Digraph, CapacityMap,

                      SetStandardElevatorTraits<_Elevator> > Create;

    };

    /// @}

  protected:

  public:

    /// \brief The constructor of the class.

    ///

    /// The constructor of the class.

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

    /// \param capacity The capacity of the arcs.

    /// \param source The source node.

    /// \param target The target node.

    Preflow(const Digraph& digraph, const CapacityMap& capacity,

      : _graph(digraph), _capacity(&capacity),

        _node_num(0), _source(source), _target(target),

        _flow(0), _local_flow(false),

        _level(0), _local_level(false),

        _excess(0), _tolerance(), _phase() {}

    ///

    /// Destructor.

    ~Preflow() {

      destroyStructures();

    }

    /// \brief Sets the capacity map.

    ///

    /// Sets the capacity map.

    Preflow& capacityMap(const CapacityMap& map) {

      _capacity = ↦

      return *this;

    }

    /// \brief Sets the flow map.

    ///

    /// Sets the flow map.

    Preflow& flowMap(FlowMap& map) {

      if (_local_flow) {

        delete _flow;

        _local_flow = false;

      }

      _flow = ↦

      return *this;

    }

    ///

    }

    ///

    Preflow& elevator(Elevator& elevator) {

      if (_local_level) {

        delete _level;

        _local_level = false;

      }

      _level = &elevator;

      return *this;

    }

    ///

    const Elevator& elevator() {

      return *_level;

    }

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

    ///

    /// Sets the tolerance used by algorithm.

    Preflow& tolerance(const Tolerance& tolerance) const {

      _tolerance = tolerance;

      return *this;

    }

    ///

    const Tolerance& tolerance() const {

      return tolerance;

    }

    ///@{

    /// \brief Initializes the internal data structures.

    ///

    void init() {

      createStructures();

      _phase = true;

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

        _excess->set(n, 0);

      }

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

        _flow->set(e, 0);

      }

        if (_tolerance.positive((*_capacity)[e])) {

          Node u = _graph.target(e);

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

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

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

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

            _level->activate(u);

          }

        }

      }

    }

    ///

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

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

    /// outgoing flow.

    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) {

        Value excess = 0;

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

          excess += (*_flow)[e];

      }

      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.

    void startFirstPhase() {

      _phase = true;

      Node n = _level->highestActive();

      int level = _level->highestActiveLevel();

      while (n != INVALID) {

        int num = _node_num;

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

          Value excess = (*_excess)[n];

          int new_level = _level->maxLevel();

            level = _level->highestActiveLevel();

          } else {

            n = _level->activeOn(level);

          }

          --num;

        }

      }

    }

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

    ///

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

    /// value of a maximum flow, \ref minCut() returns a minimum cut

    void startSecondPhase() {

      _phase = false;

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

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

        reached.set(n, (*_level)[n] < _level->maxLevel());

      }

      _level->initStart();

      _level->initAddItem(_source);

      std::vector<Node> queue;

    /// \code

    ///   pf.init();

    ///   pf.startFirstPhase();

    /// \endcode

    void runMinCut() {

      init();

      startFirstPhase();

    }

    /// @}

    /// \name Query Functions

    /// functions.\n

    ///@{

    /// \brief Returns the value of the maximum flow.

    ///

    /// Returns the value of the maximum flow by returning the excess

    Value flowValue() const {

      return (*_excess)[_target];

    }

    ///

    /// startFirstPhase() and \ref startSecondPhase().

    bool minCut(const Node& node) const {

      return ((*_level)[node] == _level->maxLevel()) == _phase;

    }

    ///

    template <typename CutMap>

    void minCutMap(CutMap& cutMap) const {

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

        cutMap.set(n, minCut(n));

      }

    }

    /// @}

  };

}

#endif