RhodeCode

      }

      _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

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

    /// The destructor deallocates this automatically allocated elevator,

    /// of course.

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

    Circulation& elevator(Elevator& elevator) {

      if (_local_level) {

        delete _level;

        _local_level = false;

      }

      _level = &elevator;

      return *this;

    }

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

    ///

    /// Returns a const reference to the elevator.

    ///

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

    /// using this function.

    const Elevator& elevator() const {

      return *_level;

    }

    ///

    Circulation& tolerance(const Tolerance& tolerance) {

      _tol = tolerance;

      return *this;

    }

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

    ///

    const Tolerance& tolerance() const {

      return _tol;

    }

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

    {

      LEMON_DEBUG(checkBoundMaps(),

        "Upper bounds must be greater or equal to the lower bounds");

      createStructures();

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

        (*_excess)[n] = (*_supply)[n];

      }

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

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

        (*_excess)[_g.target(e)] += (*_flow)[e];

        (*_excess)[_g.source(e)] -= (*_flow)[e];

      }

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

    /// \param digraph The digraph for 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

  ///

  /// \brief %Preflow algorithm class.

  ///

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

  /// \e push-relabel algorithm producing a \ref max_flow

  /// "flow of maximum value" in a digraph.

  /// The preflow algorithms are the fastest known maximum

  /// \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 CAP The type of the capacity map. The default map

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

#ifdef DOXYGEN

  template <typename GR, typename CAP, typename TR>

#else

  template <typename GR,

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

            typename TR = PreflowDefaultTraits<GR, CAP> >

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

    typedef typename Traits::Value Value;

    ///The type of the flow map.

    typedef typename Traits::FlowMap FlowMap;

    ///The type of the elevator.

    Preflow& target(const Node& node) {

      _target = node;

      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

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

    /// The destructor deallocates this automatically allocated elevator,

    /// of course.

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

    Preflow& elevator(Elevator& elevator) {

      if (_local_level) {

        delete _level;

        _local_level = false;

      }

      _level = &elevator;

      return *this;

    }

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

    ///

    /// Returns a const reference to the elevator.

    ///

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

    /// using this function.

    const Elevator& elevator() const {

      return *_level;

    }

    ///

    Preflow& tolerance(const Tolerance& tolerance) {

      _tolerance = tolerance;

      return *this;

    }

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

    ///

    const Tolerance& tolerance() const {

      return _tolerance;

    }

    /// \name Execution Control

    /// The simplest way to execute the preflow algorithm is to use

    /// \ref run() or \ref runMinCut().\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

    /// \ref startFirstPhase() and if you need it \ref startSecondPhase().

    ///@{

    /// \brief Initializes the internal data structures.

    ///

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

    /// flow to zero on each arc.

    void init() {

      createStructures();

      _phase = true;

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

        (*_excess)[n] = 0;

      }

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

        _flow->set(e, 0);

      }

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

      _level->initStart();

  typedef concepts::ReadMap<Arc,VType> CapMap;

  typedef concepts::ReadMap<Node,VType> SupplyMap;

  typedef concepts::ReadWriteMap<Arc,VType> FlowMap;

  typedef concepts::WriteMap<Node,bool> BarrierMap;

  typedef Elevator<Digraph, Digraph::Node> Elev;

  typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;

  Digraph g;

  Node n;

  Arc a;

  CapMap lcap, ucap;

  SupplyMap supply;

  FlowMap flow;

  BarrierMap bar;

  VType v;

  bool b;

  typedef Circulation<Digraph, CapMap, CapMap, SupplyMap>

            ::SetFlowMap<FlowMap>

            ::SetElevator<Elev>

            ::SetStandardElevator<LinkedElev>

            ::Create CirculationType;

  CirculationType circ_test(g, lcap, ucap, supply);

  const CirculationType& const_circ_test = circ_test;

  circ_test

    .lowerMap(lcap)

    .upperMap(ucap)

    .supplyMap(supply)

    .flowMap(flow);

  circ_test.init();

  circ_test.greedyInit();

  circ_test.start();

  circ_test.run();

  v = const_circ_test.flow(a);

  const FlowMap& fm = const_circ_test.flowMap();

  b = const_circ_test.barrier(n);

  const_circ_test.barrierMap(bar);

  ignore_unused_variable_warning(fm);

}

template <class G, class LM, class UM, class DM>

void checkCirculation(const G& g, const LM& lm, const UM& um,

                      const DM& dm, bool find)

{

  Circulation<G, LM, UM, DM> circ(g, lm, um, dm);

  bool ret = circ.run();

  if (find) {

    check(ret, "A feasible solution should have been found.");

    check(circ.checkFlow(), "The found flow is corrupt.");

    check(!circ.checkBarrier(), "A barrier should not have been found.");

  } else {

    check(!ret, "A feasible solution should not have been found.");

    check(circ.checkBarrier(), "The found barrier is corrupt.");

  }

}

int main (int, char*[])

{

  typedef ListDigraph Digraph;

void checkPreflowCompile()

{

  typedef int VType;

  typedef concepts::Digraph Digraph;

  typedef Digraph::Node Node;

  typedef Digraph::Arc Arc;

  typedef concepts::ReadMap<Arc,VType> CapMap;

  typedef concepts::ReadWriteMap<Arc,VType> FlowMap;

  typedef concepts::WriteMap<Node,bool> CutMap;

  typedef Elevator<Digraph, Digraph::Node> Elev;

  typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;

  Digraph g;

  Node n;

  Arc e;

  CapMap cap;

  FlowMap flow;

  CutMap cut;

  VType v;

  bool b;

  typedef Preflow<Digraph, CapMap>

            ::SetFlowMap<FlowMap>

            ::SetElevator<Elev>

            ::SetStandardElevator<LinkedElev>

            ::Create PreflowType;

  PreflowType preflow_test(g, cap, n, n);

  const PreflowType& const_preflow_test = preflow_test;

  preflow_test

    .capacityMap(cap)

    .flowMap(flow)

    .source(n)

    .target(n);

  preflow_test.init();

  preflow_test.init(cap);

  preflow_test.startFirstPhase();

  preflow_test.startSecondPhase();

  preflow_test.run();

  preflow_test.runMinCut();

  v = const_preflow_test.flowValue();

  v = const_preflow_test.flow(e);

  const FlowMap& fm = const_preflow_test.flowMap();

  b = const_preflow_test.minCut(n);

  const_preflow_test.minCutMap(cut);

  ignore_unused_variable_warning(fm);

}

int cutValue (const SmartDigraph& g,

              const SmartDigraph::NodeMap<bool>& cut,

              const SmartDigraph::ArcMap<int>& cap) {

  int c=0;

  for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) {

    if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e];

  }

  return c;

}